樹形數據結構

簡介

在計算機科學中，樹（tree）是一種抽象數據類型（ADT）或是實作這種抽象數據類型的數據結構，用來模擬具有樹狀結構性質的數據集合。它是由n（n>0）個有限節點組成一個具有層次關係的集合。把它叫做“樹”是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。它具有以下的特點：

每個節點有零個或多個子節點；

沒有父節點的節點稱為根節點；

每一個非根節點有且只有一個父節點；

除了根節點外，每個子節點可以分為多個不相交的子樹；

樹形數據結構是一類重要的非線性數據結構。樹形數據結構在計算機領域中有著廣泛套用，如在編譯程式中，可用樹來表示源程式的語法結構。又如在資料庫系統中，樹形數據結構也是信息的重要組織形式之一。以及在檔案管理中，多級目錄結構就採用樹形數據結構。

1、結點(Node)：表示樹中的數據元素，由數據項和數據元素之間的關係組成。在圖1中，共有10個結點。

2、結點的度(Degree of Node)：結點所擁有的子樹的個數，在圖1中，結點A的度為3。

3、樹的度(Degree of Tree)：樹中各結點度的最大值。在圖1中，樹的度為3。

4、葉子結點(Leaf Node)：度為0的結點，也叫終端結點。在圖1中，結點E、F、G、H、I、J都是葉子結點。

5、分支結點(Branch Node)：度不為0的結點，也叫非終端結點或內部結點。在圖1中，結點A、B、C、D是分支結點。

6、孩子(Child)：結點子樹的根。在圖1中，結點B、C、D是結點A的孩子。

7、雙親(Parent)：結點的上層結點叫該結點的雙親。在圖1中，結點B、C、D的雙親是結點A。

8、祖先(Ancestor)：從根到該結點所經分支上的所有結點。在圖1中，結點E的祖先是A和B。

9、子孫(Descendant)：以某結點為根的子樹中的任一結點。在圖1中，除A之外的所有結點都是A的子孫。

10、兄弟(Brother)：同一雙親的孩子。在圖1中，結點B、C、D互為兄弟。

11、結點的層次(Level of Node)：從根結點到樹中某結點所經路徑上的分支數稱為該結點的層次。根結點的層次規定為1，其餘結點的層次等於其雙親結點的層次加1。

12、堂兄弟(Sibling)：同一層的雙親不同的結點。在圖1中，G和H互為堂兄弟。

13、樹的深度(Depth of Tree)：樹中結點的最大層次數。在圖1中，樹的深度為3。

14、無序樹(Unordered Tree)：樹中任意一個結點的各孩子結點之間的次序構成無關緊要的樹。通常樹指無序樹。