樹形結構

樹形結構指的是數據元素之間存在著“一對多”的樹形關係的數據結構，是一類重要的非線性數據結構。

在樹形結構中，樹根結點沒有前驅結點，其餘每個結點有且只有一個前驅結點。葉子結點沒有後續結點，其餘每個結點的後續節點數可以是一個也可以是多個。

另外，數學統計中的樹形結構可表示層次關係。

樹形結構在其他許多方面也有應用。可表示從屬關係、並列關係。

在根目錄下形成很多個頻道、目錄，每個頻道目錄里都有屬於這個頻道的網頁。

1、樹是n（n>=0)個結點的有限集。

2、在任意一個空樹中。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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