樹(shù)的基本概念

定義：樹(shù)是n個(gè)結(jié)點(diǎn)的有限集。n=0時(shí)稱(chēng)為空樹(shù)，n>=1時(shí)為非空樹(shù)。
在任意一顆非空樹(shù)中：

• 有且僅有一個(gè)特定的稱(chēng)為根的結(jié)點(diǎn)。
• 當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m（m>0）個(gè)互不相交的有限集T1,T2……Tm。
  其中每一個(gè)集合本身又是一棵樹(shù)，并且稱(chēng)為根的子樹(shù)。
• 用到了遞歸的概念。也即樹(shù)中還有樹(shù)的概念。

樹(shù)圖.png

• n>0時(shí)根結(jié)點(diǎn)是唯一的，不可能存在多個(gè)根結(jié)點(diǎn)。
• m>0時(shí)子樹(shù)的個(gè)數(shù)沒(méi)有限制，但他們一定互不相交。

結(jié)點(diǎn)分類(lèi)：

結(jié)點(diǎn)包含：1）一個(gè)數(shù)據(jù)元素 2）若干指向其子樹(shù)的分支
結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的子樹(shù)數(shù)。度為0的結(jié)點(diǎn)稱(chēng)為葉結(jié)點(diǎn)或終端結(jié)點(diǎn)（即樹(shù)的最下方），度不為0的稱(chēng)為分支結(jié)點(diǎn)或內(nèi)部結(jié)點(diǎn)。
樹(shù)的度：樹(shù)內(nèi)各結(jié)點(diǎn)度的最大值。

結(jié)點(diǎn)間關(guān)系：

孩子（child）：結(jié)點(diǎn)的子樹(shù)的根（也即下方第一個(gè)）稱(chēng)為該結(jié)點(diǎn)的孩子。
雙親（parent）:上面的那個(gè)結(jié)點(diǎn)稱(chēng)為孩子的雙親。
兄弟（Sibling）：同一個(gè)雙親的孩子，如上圖D和E。
堂兄弟：雙親在同一層的結(jié)點(diǎn)。

樹(shù)的其他相關(guān)概念：

結(jié)點(diǎn)的層次：從根開(kāi)始定義起，根為第一層，根的孩子為第二層。上圖所示樹(shù)圖就有三層。
樹(shù)的深度或高度：樹(shù)種結(jié)點(diǎn)的最大層次。
有序樹(shù)無(wú)序樹(shù)：樹(shù)中結(jié)點(diǎn)的各子樹(shù)從左至右，如若有次序不能互換，則稱(chēng)為有序樹(shù)，否則稱(chēng)為無(wú)序樹(shù)。
森林：是m顆（m>0）互不相交的樹(shù)的集合。對(duì)樹(shù)中每個(gè)結(jié)點(diǎn)而言，其子樹(shù)的集合就是森林。（不包括根，因?yàn)樗闵细椭挥幸豢脴?shù)了。）