樹形數據結構

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

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

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

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

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

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

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)：樹中任意一個結點的各孩子結點之間的次序構成無關緊要的樹。通常樹指無序樹。

15、有序樹(Ordered Tree)：樹中任意一個結點的各孩子結點有嚴格排列次序的樹。二叉樹是有序樹，因為二叉樹中每個孩子結點都確切定義為是該結點的左孩子結點還是右孩子結點。

16、森林(Forest)：m(m≥0)棵樹的集合。自然界中的樹和森林的概念差別很大，但在數據結構中樹和森林的概念差別很小。從定義可知，一棵樹有根結點和m個子樹構成，若把樹的根結點刪除，則樹變成了包含m棵樹的森林。當然，根據定義，一棵樹也可以稱為森林。

對於大型文件系統，通常採用三級或三級以上的目錄結構，以提高對目錄的檢索速度和文件系統的性能。多級目錄結構又稱為樹型目錄結構，主目錄在這裏被稱為根目錄，把數據文件稱為樹葉，其它的目錄均作為樹的結點。下圖1示出了多級目錄結構。圖1中，用方框代表目錄文件，圓圈代表數據文件。在該樹型目錄結構中，主(根)目錄中有三個用户的總目錄項 A、 B 和 C。 在 B 項所指出的 B 用户的總目錄 B 中， 又包括三個分目錄 F、 E 和

D，其中每個分目錄中又包含多個文件。如 B 目錄中的 F 分目錄中，包含 J 和 N 兩個文件。為了提高文件系統的靈活性，應允許在一個目錄文件中的目錄項既是作為目錄文件的 FCB，又是數據文件的 FCB，這一信息可用目錄項中的一位來指示。例如，在圖1中，用户 A的總目錄中，目錄項 A 是目錄文件的 FCB，而目錄項 B 和 D 則是數據文件的 FCB。 ^[2]