1.定義
樹(Tree)是n(n>=0)個結(jié)點(diǎn)的有限集。當(dāng)n=0時稱為空樹萨脑，在任意一棵非空樹中：
- 有且僅有一個特定的稱為根(Root)的結(jié)點(diǎn)隐轩；
-
當(dāng)n>1時，其余結(jié)點(diǎn)可分為m(m>0)個互不相交的有限集T1渤早、T2职车、……、Tm鹊杖，其中每一個集合本身又是一棵樹悴灵，并且稱為根的子樹(SubTree)
樹
注意：
- n>0時，根節(jié)點(diǎn)是唯一的骂蓖，堅(jiān)決不可能存在多個根結(jié)點(diǎn)
-
m>0時积瞒，子樹的個數(shù)是沒有限制的，但他們互相是一定不會相交的
根節(jié)點(diǎn)必須唯一
子樹不可相交
2.結(jié)點(diǎn)分類
在之前的圖片中登下，每一個圓圈我們就稱為樹的一個結(jié)點(diǎn)茫孔。結(jié)點(diǎn)擁有的子樹數(shù)量稱為結(jié)點(diǎn)的度(Degree)，樹的度取樹內(nèi)各結(jié)點(diǎn)的度的最大值被芳。
- 度為0的結(jié)點(diǎn)成為葉結(jié)點(diǎn)(Leaf)或終端結(jié)點(diǎn)
- 度不為0的結(jié)點(diǎn)成為分支結(jié)點(diǎn)或非終端結(jié)點(diǎn)缰贝，除根結(jié)點(diǎn)外，分支結(jié)點(diǎn)也成為內(nèi)部結(jié)點(diǎn)
度
3.結(jié)點(diǎn)間的關(guān)系
- 結(jié)點(diǎn)的子樹的根稱為結(jié)點(diǎn)的孩子(Child)畔濒，相應(yīng)的剩晴，該結(jié)點(diǎn)稱為孩子的雙親(Parent)，同一雙親的孩子之間互稱為兄弟(Sibling)侵状。
-
結(jié)點(diǎn)的祖先是從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)
結(jié)點(diǎn)間的關(guān)系
4.結(jié)點(diǎn)的層次
- 結(jié)點(diǎn)的層次(Level)從根開始定一起赞弥，根為第一層，根的孩子為第二層趣兄。
- 其雙親在同一層的結(jié)點(diǎn)互稱堂兄弟
-
樹中結(jié)點(diǎn)的最大層次稱為樹的深度(Depth)或高度
結(jié)點(diǎn)的層次
如圖绽左，D和G互稱堂兄弟，該樹的深度為3
5.其它概念
- 如果將樹中的各子樹看成從左至右是有次序的艇潭，不能互換的妇菱，則稱該樹為有序樹，否則稱為無序樹
- 森林(Forest)是m(m>0)棵互不相交的樹的集合暴区。對樹中每個結(jié)點(diǎn)而言闯团，其子樹的集合即為森林
