樹結(jié)構(gòu)的相關(guān)概念

節(jié)點(diǎn)：每一個(gè)數(shù)據(jù)元素；
父節(jié)點(diǎn)：如圖所示A是一個(gè)父節(jié)點(diǎn)；
子節(jié)點(diǎn)：如圖所示BCD都是A的子節(jié)點(diǎn)；
兄弟節(jié)點(diǎn)：擁有同一個(gè)父節(jié)點(diǎn)的節(jié)點(diǎn)；
根節(jié)點(diǎn)：樹結(jié)構(gòu)中沒(méi)有父節(jié)點(diǎn)的節(jié)點(diǎn)；
葉子結(jié)點(diǎn)：沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)；
空樹：集合本身為空的樹結(jié)構(gòu)，空樹中沒(méi)有節(jié)點(diǎn)；
子樹：如圖所示，單獨(dú)看BEFKL組成的部分也是一棵樹，這棵樹為子樹，單個(gè)節(jié)點(diǎn)也是一顆子樹；

樹結(jié)構(gòu)示意.png

節(jié)點(diǎn)的度：一個(gè)節(jié)點(diǎn)擁有的子樹數(shù)目為節(jié)點(diǎn)的度，一棵樹的節(jié)點(diǎn)是樹內(nèi)各節(jié)點(diǎn)的度的最大值；
節(jié)點(diǎn)的層次：從一棵樹的樹根開始，樹根所在層為第一層，根的孩子結(jié)點(diǎn)所在的層為第二層，依次類推。一棵樹的深度（高度）是樹中結(jié)點(diǎn)所在的最大的層次。圖 1（A）樹的深度為 4。

二叉樹

本身是有序樹且樹中包含的各個(gè)節(jié)點(diǎn)的度只能是0,1,2

二叉樹的性質(zhì)

1.二叉樹中第i層最多有個(gè)節(jié)點(diǎn)
2.二叉樹中葉子節(jié)點(diǎn)數(shù)為，則度為2的節(jié)點(diǎn)數(shù)，則 = +1

推導(dǎo)：性質(zhì) 3 的計(jì)算方法為：對(duì)于一個(gè)二叉樹來(lái)說(shuō)，除了度為 0 的葉子結(jié)點(diǎn)和度為 2 的結(jié)點(diǎn)，剩下的就是度為 1 的結(jié)點(diǎn)（設(shè)為 n1），那么總結(jié)點(diǎn) n=n0+n1+n2。同時(shí)，對(duì)于每一個(gè)結(jié)點(diǎn)來(lái)說(shuō)都是由其父結(jié)點(diǎn)分支表示的，假設(shè)樹中分枝數(shù)為 B，那么總結(jié)點(diǎn)數(shù) n=B+1。而分枝數(shù)是可以通過(guò) n1 和 n2 表示的，即 B=n1+2n2。所以，n 用另外一種方式表示為 n=n1+2n2+1。兩種方式得到的 n 值組成一個(gè)方程組，就可以得出 n0=n2+1。

二叉樹分類

滿二叉樹：除了葉子節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)的度都為2的二叉樹。具有n個(gè)節(jié)點(diǎn)的滿二叉樹的深度為(n+1)

滿二叉樹.png

a) 完全二叉樹 b)非完全二叉樹.png

二叉樹的順序儲(chǔ)存結(jié)構(gòu)

二叉樹的順序存儲(chǔ)，指的是使用數(shù)組存儲(chǔ)二叉樹。需要注意的是，順序存儲(chǔ)只適用于完全二叉樹。因此，如果我們想順序存儲(chǔ)普通二叉樹，需要提前將普通二叉樹轉(zhuǎn)化為完全二叉樹。

完全二叉樹的順序存儲(chǔ)，僅需從根節(jié)點(diǎn)開始，按照層次依次將樹中節(jié)點(diǎn)存儲(chǔ)到數(shù)組即可。

從順序表中還原完全二叉樹也很簡(jiǎn)單。我們知道，完全二叉樹具有這樣的性質(zhì)，將樹中節(jié)點(diǎn)按照層次并從左到右依次標(biāo)號(hào)（1,2,3,...），若節(jié)點(diǎn) i 有左右孩子，則其左孩子節(jié)點(diǎn)為 2i，右孩子節(jié)點(diǎn)為 2i+1。

http://data.biancheng.net/view/194.html

二叉樹的鏈?zhǔn)絻?chǔ)存結(jié)構(gòu)

采用鏈?zhǔn)酱鎯?chǔ)二叉樹時(shí)，其節(jié)點(diǎn)結(jié)構(gòu)由 3 部分構(gòu)成（如圖 3 所示）：
指向左孩子節(jié)點(diǎn)的指針（Lchild）；
節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)（data）；
指向右孩子節(jié)點(diǎn)的指針（Rchild）；

二叉樹節(jié)點(diǎn)結(jié)構(gòu).png