摘要：圖是構成網頁的超文本標記語言中的標簽相互關聯關系所構成的樹。節點節點是樹的基本構成部分。子樹子樹是一個父節點的某個子節點的所有邊和后代節點所構成的集合。高度樹的高度等于所有節點的層數的最大值。每個子樹的根節點和其父樹的根節點之間通過邊相連。

我們已經學過了像棧和隊列這樣的線性數據結構，同時我們對遞歸也有了一定的了解，現在讓我們來看看另一種常見的數據結構——樹（Tree）。樹在計算機科學里應用廣泛，包括操作系統，圖形學，數據庫和計算機網絡。樹和真正的樹有許多相似的地方，也包括根、樹枝和葉子，它們的不同在于計算機中的樹的根在頂層而它的葉子在底部。

在我們開始學習樹之前，讓我們先來看看幾個常見的關于樹的例子。首先讓我們看看生物學中的分類。圖 1 是一個動物分類的例子，從中我們可以看出樹的幾個特點。第一，這個例子說明樹是分級的，這里分級的意思是樹的頂層部分更加寬泛，而底部更加具體。在這個例子中，最上層的是“界”，它下面的一層（上層的子級）是“門”，然后是“綱”等等。但是，無論我們細分到多少層，這里面包含的生命體也都是動物。

圖 1：一些動物的分類樹

我們注意到可以從樹的頂層開始然后沿著圓圈和箭頭構成的一條路徑到達樹的底層。在樹的每一層我們都可以問自己一個問題，然后沿著相符的那條路徑繼續下去。比如我們可以問 “這個動物是脊椎動物還是無脊椎動物”，如果回答是“脊椎動物”我們就沿著脊椎動物這條路下去然后接著問“這個脊椎動物是哺乳動物嗎”，如果回答“不是哺乳動物”我們就卡在這里了（不過僅限于這個簡單的例子會有這種情況）。當我們到達哺乳動物這一層的時候我們問自己“這個哺乳動物是靈長類還是食肉動物”。我們可以沿著路徑一直走下去直到樹的最底層，這也就能看到動物的名稱了。

樹的第二個特點是一個節點（node）的所有子節點（children）和另一個節點的子節點是完全獨立的。比如“貓屬”有兩個子節點“家生”和“野生”，“蠅屬”中也有一個“家生”，但它和“貓屬”中的“家生”完全不同而且相互獨立。這意味著我們可以在不影響“貓屬” 的子節點的情況下更改“蠅屬”的子節點。

樹的第三個特點就是每個它的葉節點（leaf）都是不同的。對每一種動物，我們都可以從根節點（root）開始沿著一條特定的路徑找到它對應的葉節點，并把它和其他動物區分開，例如對于家貓，我們可以沿著動物界——脊索動物門——哺乳動物綱——食肉動物目——貓科——貓屬——家貓找到它。

另一個樹的例子就是你每天都會用到的文件系統。在文件系統中，磁盤的分支或者說子目錄都是運用了樹來構建的。圖 2 展示了Unix文件系統的部分的分層情況。

圖 2 ：Unix文件系統的部分的分層情況

這個樹的文件系統和真正的樹也非常相像。你可以從根節點出發沿著一條路徑到任意分支。這條路徑會把這個子分支（包括它里面的所有文件）和其他分支區別開。樹的另一重要特點，就是你可以將樹下層的所有部分（叫做子樹subtree）移動到樹的另一位置而不影響更下層的情況，這是由樹的分級方式決定的。例如，我們可以將所有標注/etc的子樹從根節點下移動到usr/下面。這樣做會將 httpd 的路徑從/etc/httpd改變成/usr/etc/httpd，但是對httpd的內容和子節點的內容不會有影響。

最后一個樹的例子是一個網頁。下圖是一個利用超文本標記語言（HTML）編寫的簡單網頁。圖 3 是構成網頁的超文本標記語言中的標簽相互關聯關系所構成的樹。

    
        
        
    
    
        
A simple web page
            

                
List item one
                
List item two
            
        
Luther CS 

    

圖 3 ：網頁的標記符之間的相互關聯所構成的樹

上面的超文本標記的代碼和它對應的樹說明了另一種分級方式。我們發現樹的每一層都對應超文本標記符的一層嵌套。代碼的第一個標記符是同時最后一個是。這一頁中所有其他的標記符也都是成對的。試一下你就會發現這種嵌套的特點在樹的每一層都是成立的。

現在我們已經看了幾個樹的例子了，現在正式定義樹以及構成它的要素。

節點（Node）
節點是樹的基本構成部分。它可能有其他專屬的名稱，我們稱之為“鍵（key）”。一個節點也可能有更多的信息，我們稱之為“負載”。雖然負載信息和樹的許多算法并不直接相關，但是它對于樹的應用至關重要。

邊（Edge）
邊也是樹的基本構成部分。邊連接兩個節點，并表示它們之間存在聯系。除了根節點外每個節點都有且只有一條與其他節點相連的入邊（指向該節點的邊），每個節點可能有許多條出邊（從該節點指向其他節點的邊）。

根節點（Root）
根節點是樹種中唯一一個沒有入邊的節點。在圖 2 中，“/”是樹的根節點。

路徑（Path）
路徑是由邊連接起來的節點的有序排列。例如：（動物界——脊索動物門——哺乳動物綱——食肉動物目——貓科——貓屬——家貓）就是一條路徑。

子節點集（Children）
當一個節點的入邊來自另一個節點時，我們稱前者是后者的子節點，同一個節點的所有子節點構成子節點集。在圖 2 中，節點log/,spool/,yp/構成節點var/的子節點集。

父節點（Parent）
一個節點是它出邊所連接的所有節點的父節點。在圖 2 中，節點var/是節點log/,spool/,yp/的父節點。

兄弟節點（Sibling）
同一個節點的所有子節點互為兄弟節點，在文件系統樹中節點etc/和節點usr/是兄弟節點。

子樹（Subtree）
子樹是一個父節點的某個子節點的所有邊和后代節點所構成的集合。

葉節點（Leaf Node）
沒有子節點的節點成為稱為葉節點。例如圖 1 中的“人”和“黑猩猩”就是葉節點。

層數（Level）
一個節點的層數是指從根節點到該節點的路徑中的邊的數目。例如，圖 1 中“貓屬”的層數是 5，定義根節點的層數為 0。

高度（Height）
樹的高度等于所有節點的層數的最大值。圖 2 中樹的高度為 2。

我們已經定義好所需的術語了，現在可以正式定義樹了。我們將用兩種方式定義，一種需要用到節點和邊，而另一種更為有效的定義方式是利用遞歸定義。

定義一：樹是節點和連接節點的邊的集合，它有以下特征：

有一個節點被設計為根節點。

除了根節點的每一個節點 n，都通過一條邊與它唯一的父節點相連。

可以沿著唯一的路徑從根節點到每個節點。

如果這個樹的每個節點都至多有兩個子節點，我們稱它為二叉樹。

圖 4 展示了一個符合定義一的樹。每條邊的箭頭指出了連接的方向。

圖 4 ：由節點和邊構成的樹

定義二：每個樹或者為空，或者包含一個根節點和 0 個或多個子樹，其中每個子樹也符合這樣的定義。每個子樹的根節點和其父樹的根節點之間通過邊相連。圖 5 描繪了這種遞歸定義的樹。通過這種樹的遞歸定義，我們知道圖 5 中的樹至少有 4 個節點，因為每個三角形所代表的子樹必須有根。它也可能有更多的節點，但我們需要更深入的了解這棵樹來得到答案。

圖 5 ：遞歸法定義的樹