什么是樹？

樹:
樹(Tree) 是n (n≥0)個結點的有限集。n=0時稱為空樹。在任意- -棵非空，
樹中: (1) 有且僅有一個特定的稱為根(Root) 的結點; (2)當n>1時，其
余結點可分為m (m>0)個互不相交的有限集TI. T2、..... Te,其中每一-個
集合本身又是- -棵樹，并且稱為根的子樹(SubTree)。

image.png

樹的概念：

1、節(jié)點與樹的度

度:結點擁有的子樹數(shù)稱為結點的度。
度為0的結點稱為葉子結點或終端結點，度不為0的結點稱為非終端結點或分支結點。除根結點以外，分支結點也稱為內(nèi)部結點。
樹的度:是樹內(nèi)各結點的度的最大值。

image.png

2 、層次和深度

結點的層次(Level) 從根開始定義起，根為第-層， 根的孩子為第二層。若某結
點在第1層，則其子樹的根就在第l+1層。其雙親在同一層的結點互為堂兄弟。顯然圖6-2-6中的D、E、F是堂兄弟，而G、H、1. I也是。樹中結點的最大層次稱為樹的深度(Depth)或高度，當前樹的深度為4。

image.png

3、森林

森林(Forest) 是m(m≥0)棵互不相交的樹的集合。

4、樹的存儲結構

（1）、雙親表示法

image.png

（2）、孩子表示法

image.png

（3）、雙親孩子表示法

把每個結點的孩子結點排列起來，以單鏈表作為存儲結構，則n個結點有n個孩子鏈表，如果是葉子結點則此單鏈表為空，然后n個頭指針又組成一個線性表，采用順序存儲結構，存放在一個一維數(shù)組中。

image.png

（4）、孩子兄弟表示法

孩子兄弟表示法為每個節(jié)點設計三個域：一個數(shù)據(jù)域，一個該節(jié)點的第一個孩子節(jié)點域，一個該節(jié)點的下一個節(jié)點的兄弟指針域。

image.png