本文是算法與數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)筆記第五篇，將持續(xù)更新，歡迎小伙伴們閱讀學(xué)習(xí)。有不懂的或錯(cuò)誤的地方，歡迎交流

引言

前面章節(jié)介紹的都是線(xiàn)性存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)，包括數(shù)組、鏈表、棧、隊(duì)列。本節(jié)帶大家學(xué)習(xí)一種非線(xiàn)性存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)，即樹(shù)（tree）。

不管是在面試時(shí)，還是日常開(kāi)發(fā)過(guò)程中，樹(shù)都是一種曝光率極高的數(shù)據(jù)結(jié)構(gòu)。可以說(shuō)樹(shù)是數(shù)據(jù)結(jié)構(gòu)最為承上啟下的部分，其可以轉(zhuǎn)化為線(xiàn)性表（通過(guò)二叉樹(shù)的線(xiàn)索化），也是學(xué)習(xí)圖的基礎(chǔ)。本文將介紹樹(shù)的基本概念、常見(jiàn)類(lèi)型和應(yīng)用、二叉樹(shù)以及 C 語(yǔ)言實(shí)現(xiàn)，幫助大家深入理解樹(shù)的本質(zhì)和用途。

樹(shù)的基本概念

樹(shù)的定義

樹(shù)是 n(n>=0) 個(gè)結(jié)點(diǎn)的有限集。當(dāng) n=0 時(shí)，稱(chēng)為空樹(shù)。在任意一棵非空樹(shù)中應(yīng)滿(mǎn)足：

1. 有且僅有一個(gè)特定的稱(chēng)為根的結(jié)點(diǎn)。
2. 當(dāng) n>1 時(shí)，其余節(jié)點(diǎn)可分為 m(m>0) 個(gè)互不相交的有限集 T1,T2,…,Tm，其中每個(gè)集合 Ti(1<=i<=m) 本身又是一棵樹(shù)，并且稱(chēng)為根的子樹(shù)。

顯然，樹(shù)的定義是遞歸的，即在樹(shù)的定義中又用到了自身，樹(shù)是一種遞歸的數(shù)據(jù)結(jié)構(gòu)。樹(shù)同時(shí)也是一種分層結(jié)構(gòu)，具有以下兩個(gè)特點(diǎn)：

1. 樹(shù)的根結(jié)點(diǎn)沒(méi)有前驅(qū)，除根結(jié)點(diǎn)外的所有結(jié)點(diǎn)有且只有一個(gè)前驅(qū)。
2. 樹(shù)中所有結(jié)點(diǎn)可以有零個(gè)或多個(gè)后繼。

因此 n 個(gè)結(jié)點(diǎn)的樹(shù)中有 n-1 條邊。

基本術(shù)語(yǔ)

下面結(jié)合圖示來(lái)說(shuō)明一下樹(shù)的一些基本術(shù)語(yǔ)和概念。

結(jié)點(diǎn)：和鏈表類(lèi)似，樹(shù)存儲(chǔ)結(jié)構(gòu)中也將存儲(chǔ)的各個(gè)元素稱(chēng)為結(jié)點(diǎn)。例如在上圖中，元素 A 就是一個(gè)結(jié)點(diǎn)。對(duì)于樹(shù)中某些特殊位置的結(jié)點(diǎn)，還可以進(jìn)行更細(xì)致的劃分，比如：
父結(jié)點(diǎn)（雙親結(jié)點(diǎn)）、孩子結(jié)點(diǎn)和兄弟結(jié)點(diǎn)：以上圖中的結(jié)點(diǎn) A、B、C、D 為例，A 是 B、C、D 結(jié)點(diǎn)的父結(jié)點(diǎn)（也稱(chēng)為雙親結(jié)點(diǎn)），而 B、C、D 都是 A 結(jié)點(diǎn)的孩子結(jié)點(diǎn)（也稱(chēng)“子結(jié)點(diǎn)”）。對(duì)于 B、C、D 來(lái)說(shuō)，它們都有相同的父結(jié)點(diǎn)，所以它們互為兄弟結(jié)點(diǎn)；
樹(shù)根結(jié)點(diǎn)（簡(jiǎn)稱(chēng)根結(jié)點(diǎn)）：特指樹(shù)中沒(méi)有雙親（父親）的結(jié)點(diǎn)，一棵樹(shù)有且僅有一個(gè)根結(jié)點(diǎn)。上圖中，結(jié)點(diǎn) A 就是整棵樹(shù)的根結(jié)點(diǎn)；
祖先、子孫：根 A 到結(jié)點(diǎn) K 的唯一路徑上的任意結(jié)點(diǎn),稱(chēng)為結(jié)點(diǎn) K 的祖先。如結(jié)點(diǎn) B 是結(jié)點(diǎn) K 的祖先,而結(jié)點(diǎn) K 是結(jié)點(diǎn) B 的子孫。

子樹(shù)：仍以上圖的樹(shù)為例，A 是整棵樹(shù)的根結(jié)點(diǎn)。但如果單看結(jié)點(diǎn) B、E、F、K、L 組成的部分來(lái)說(shuō)，它們也組成了一棵樹(shù)，結(jié)點(diǎn) B 是這棵樹(shù)的根結(jié)點(diǎn)。通常，我們將一棵樹(shù)中幾個(gè)結(jié)點(diǎn)構(gòu)成的“小樹(shù)”稱(chēng)為這棵樹(shù)的“子樹(shù)”。
知道了子樹(shù)的概念后，樹(shù)也可以這樣定義：樹(shù)是由根結(jié)點(diǎn)和若干棵子樹(shù)構(gòu)成的。例如，上圖這棵樹(shù)就是由根結(jié)點(diǎn) A 和分別以 B、C、D 為根節(jié)點(diǎn)的子樹(shù)構(gòu)成。
注意：?jiǎn)蝹€(gè)結(jié)點(diǎn)也可以看作是一棵樹(shù)，該結(jié)點(diǎn)即為根結(jié)點(diǎn)。例如上圖中，結(jié)點(diǎn) K、L、F 各自就可以看作是一棵樹(shù)，只不過(guò)樹(shù)中只有一個(gè)根節(jié)點(diǎn)而已。

結(jié)點(diǎn)的度：一個(gè)結(jié)點(diǎn)擁有子樹(shù)的個(gè)數(shù)，就稱(chēng)為該結(jié)點(diǎn)的度（Degree）。例如上圖中，根結(jié)點(diǎn) A 有3個(gè)子樹(shù)，它們的根節(jié)點(diǎn)分別是 B、C、D，因此結(jié)點(diǎn) A 的度為3。
樹(shù)的度：一棵樹(shù)中，最大的節(jié)點(diǎn)的度稱(chēng)為樹(shù)的度。如上圖：所有結(jié)點(diǎn)中最大的度為3，所以整棵樹(shù)的度就是3。
葉節(jié)點(diǎn)或終端節(jié)點(diǎn)：度為0的節(jié)點(diǎn)稱(chēng)為葉節(jié)點(diǎn)； 如上圖：I、J、F、K、L、M 等節(jié)點(diǎn)為葉節(jié)點(diǎn)。
分支節(jié)點(diǎn)或非終端節(jié)點(diǎn)：度不為0的節(jié)點(diǎn)； 如上圖：A、B、C、D 等節(jié)點(diǎn)為分支節(jié)點(diǎn)。

結(jié)點(diǎn)的層次：結(jié)點(diǎn)的層次從一棵樹(shù)的樹(shù)根開(kāi)始定義，樹(shù)根所在層為第一層，根的孩子結(jié)點(diǎn)所在的層為第二層，依次類(lèi)推。對(duì)于上圖這棵樹(shù)來(lái)說(shuō)，A 結(jié)點(diǎn)在第一層，B、C、D 為第二層，E、F、G、H、I、J 在第三層，K、L、M 在第四層。
樹(shù)中結(jié)點(diǎn)層次的最大值，稱(chēng)為這棵樹(shù)的深度或者高度。例如上圖這棵樹(shù)的深度為 4。
如果兩個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)不同，但它們父結(jié)點(diǎn)的層次相同，那么這兩個(gè)結(jié)點(diǎn)互為堂兄弟。例如上圖中，結(jié)點(diǎn) G 和 E、F、H、I、J 的父結(jié)點(diǎn)都在第二層，所以它們互為堂兄弟。

有序樹(shù)和無(wú)序樹(shù)：樹(shù)中結(jié)點(diǎn)的各子樹(shù)從左到右是有次序的,不能互換,稱(chēng)該樹(shù)為有序樹(shù),否則稱(chēng)為無(wú)序樹(shù)。假設(shè)圖為有序樹(shù),若將子結(jié)點(diǎn)位置互換,則變成一棵不同的樹(shù)。
在有序樹(shù)中，結(jié)點(diǎn)最左邊的子樹(shù)稱(chēng)為 “第一個(gè)孩子”，最右邊的稱(chēng)為 “最后一個(gè)孩子”。拿上圖這棵樹(shù)來(lái)說(shuō)，如果它是一棵有序樹(shù)，那么以結(jié)點(diǎn) B 為根結(jié)點(diǎn)的子樹(shù)為整棵樹(shù)的第一個(gè)孩子，以結(jié)點(diǎn) D 為根結(jié)點(diǎn)的子樹(shù)為整棵樹(shù)的最后一個(gè)孩子。

路徑和路徑長(zhǎng)度：樹(shù)中兩個(gè)結(jié)點(diǎn)之間的路徑是由這兩個(gè)結(jié)點(diǎn)之間所經(jīng)過(guò)的結(jié)點(diǎn)序列構(gòu)成的，而路徑長(zhǎng)度是路徑上所經(jīng)過(guò)的邊的個(gè)數(shù)。
注意：由于樹(shù)中的分支是有向的，即從雙親指向孩子，所以樹(shù)中的路徑是從上向下的，同一層的兩個(gè)結(jié)點(diǎn)之間不存在路徑。

森林：森林是 m(m≥0) 棵互不相交的樹(shù)的集合。森林的概念與樹(shù)的概念十分相近，因?yàn)橹灰褬?shù)的根結(jié)點(diǎn)刪去就成了森林。反之，只要給 m 棵獨(dú)立的樹(shù)加上一個(gè)結(jié)點(diǎn)，并把這 m 棵樹(shù)作為該結(jié)點(diǎn)的子樹(shù)，則森林就變成了樹(shù)。

樹(shù)的性質(zhì)

樹(shù)具有如下最基本的性質(zhì)：

1. 樹(shù)中的結(jié)點(diǎn)數(shù)等于所有結(jié)點(diǎn)的度數(shù)加1；
2. 度為 $m$ 的樹(shù)中第 $i$ 層上至多有 $m^{i?1}$ 個(gè)結(jié)點(diǎn)（$i\ge 1$）；
3. 高度為 $h$ 的 $m$ 叉樹(shù)至多有 $(m^h?1)/(m?1)$ 個(gè)結(jié)點(diǎn)；
4. 具有 $n$ 個(gè)結(jié)點(diǎn)的 $m$ 叉樹(shù)的最小高度為 $lo{g}_m(n(m?1)+1)$。

樹(shù)的其它表示方法

上圖中使用的是樹(shù)狀表示法，最基本的邏輯結(jié)構(gòu)表示法，使用一棵樹(shù)倒置表示，非常直觀(guān)。除了這種方法之外，還有其它的方式可以表示一棵樹(shù)：

上圖左側(cè)是文氏圖標(biāo)表示法：是使用集合以及集合包含關(guān)系描述樹(shù)結(jié)構(gòu)（集合之間絕不能相交，即任意兩個(gè)圓圈不能有交集）。

上圖右側(cè)使用的是凹入表示法，最長(zhǎng)條為根結(jié)點(diǎn)，相同長(zhǎng)度的表示在同一層次。例如 B、C、D 長(zhǎng)度相同，都為 A 的子結(jié)點(diǎn)，E 和 F 長(zhǎng)度相同，為 B 的子結(jié)點(diǎn)，K 和 L 長(zhǎng)度相同，為 E 的子結(jié)點(diǎn)，依此類(lèi)推。

還可以使用括號(hào)表示法：將樹(shù)的根結(jié)點(diǎn)寫(xiě)在括號(hào)的左邊，除根結(jié)點(diǎn)之外的其余結(jié)點(diǎn)寫(xiě)在括號(hào)中，并用逗號(hào)分隔。例如上面的樹(shù)用括號(hào)表示為 $(A,(B(E(K,L),F),C(G),D(H(M),I,J)))$。

樹(shù)的存儲(chǔ)結(jié)構(gòu)

說(shuō)到存儲(chǔ)結(jié)構(gòu)，自然就會(huì)想到我們前面講過(guò)的順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種結(jié)構(gòu)。

順序存儲(chǔ)結(jié)構(gòu)：樹(shù)中某個(gè)結(jié)點(diǎn)的孩子可以有多個(gè)，若將樹(shù)中所有結(jié)點(diǎn)存儲(chǔ)到數(shù)組中，結(jié)點(diǎn)的存儲(chǔ)位置無(wú)法直接反應(yīng)其邏輯關(guān)系，因此簡(jiǎn)單的順序存儲(chǔ)結(jié)構(gòu)是不能滿(mǎn)足樹(shù)的實(shí)現(xiàn)要求的。

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)，完全可以實(shí)現(xiàn)對(duì)樹(shù)的存儲(chǔ)結(jié)構(gòu)的表示。

表示方式：實(shí)際中樹(shù)有很多種表示方式， 如：雙親表示法，孩子表示法、孩子兄弟表示法等等。我們這里就簡(jiǎn)單的了解其中最常用的孩子兄弟表示法。

對(duì)于樹(shù)這樣的層級(jí)結(jié)構(gòu)，我們觀(guān)察后發(fā)現(xiàn)，任意—棵樹(shù)，它的結(jié)點(diǎn)的第一個(gè)孩子如果存在就是唯一的，它的右只弟如果存在也是唯一的。因此，我們?cè)O(shè)置兩個(gè)指針，分別指向該結(jié)點(diǎn)的第一個(gè)孩子和此結(jié)點(diǎn)的右兄弟。

結(jié)點(diǎn)結(jié)構(gòu)如下表所示：

其中 data 是數(shù)據(jù)域；firstchild 為指針域，存儲(chǔ)該結(jié)點(diǎn)的第—個(gè)孩子結(jié)點(diǎn)的存儲(chǔ)地址；rightsib是指針域，存儲(chǔ)該結(jié)點(diǎn)的右兄弟結(jié)點(diǎn)的存儲(chǔ)地址。

結(jié)構(gòu)定義代碼如下：

/* 樹(shù)的孩子兄弟表示法結(jié)構(gòu)定義 */
typedef struct CSNode
{
	TElemType data;				 // 結(jié)點(diǎn)中的數(shù)據(jù)域
    struct CSNode *firstchild1,*rightsib;    // 指向其第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)       
}CSNode,*CSTree;

對(duì)于下圖左邊的樹(shù)來(lái)說(shuō)，這種方法實(shí)現(xiàn)的示意圖如右下圖所示：

其實(shí)這個(gè)表示法的最大好處是它把一棵復(fù)雜的樹(shù)變成了一棵二叉樹(shù)，這樣就可以充分利用二叉樹(shù)的特性和算法來(lái)處理這棵樹(shù)了。嗯？有人問(wèn)，二叉樹(shù)是什么？哈哈，別急，這正是接下來(lái)要重點(diǎn)講的內(nèi)容。

常見(jiàn)類(lèi)型的樹(shù)

二叉樹(shù)

二叉樹(shù)是一種最基本的樹(shù)型數(shù)據(jù)結(jié)構(gòu)。簡(jiǎn)單地理解，度不超過(guò)2的有序樹(shù)就是二叉樹(shù)。

例如，下圖左側(cè)就是一棵二叉樹(shù)，而右側(cè)則不是。

二叉樹(shù)還可以繼續(xù)分類(lèi)，衍生出完全二叉樹(shù)、滿(mǎn)二叉樹(shù)等：

滿(mǎn)二叉樹(shù)

如果二叉樹(shù)中除了葉子結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)的度都為 2，則此二叉樹(shù)稱(chēng)為滿(mǎn)二叉樹(shù)，如下圖所示：

完全二叉樹(shù)

如果二叉樹(shù)中除去最后一層節(jié)點(diǎn)為滿(mǎn)二叉樹(shù)，且最后一層的結(jié)點(diǎn)依次從左到右分布，則此二叉樹(shù)被稱(chēng)為完全二叉樹(shù)。滿(mǎn)二叉樹(shù)是完全二叉樹(shù)的一種特殊情況。

堆

堆也是完全二叉樹(shù)的一種特殊情況，針對(duì)的是節(jié)點(diǎn)數(shù)據(jù)的大小對(duì)比。堆中每個(gè)節(jié)點(diǎn)的值都必須大于等于（或者小于等于）其子樹(shù)中的每個(gè)節(jié)點(diǎn)的值。大于等于每個(gè)子樹(shù)節(jié)點(diǎn)的值稱(chēng)為大頂堆，反正稱(chēng)為小頂堆，如下圖所示。后面將有文章專(zhuān)門(mén)分析堆。

二叉搜索樹(shù)

二叉搜索樹(shù)是一種特殊的二叉樹(shù)，又稱(chēng)為二叉查找樹(shù)、二叉排序樹(shù)等等，它實(shí)際上是數(shù)據(jù)域有序的二叉樹(shù)，即對(duì)樹(shù)上的每個(gè)結(jié)點(diǎn)，都滿(mǎn)足其左子樹(shù)上所有結(jié)點(diǎn)的數(shù)據(jù)域均小于根結(jié)點(diǎn)的數(shù)據(jù)域，右子樹(shù)上所有結(jié)點(diǎn)的數(shù)據(jù)域均大于根結(jié)點(diǎn)的數(shù)據(jù)域。

二叉排序樹(shù)意味著二叉樹(shù)中的數(shù)據(jù)是排好序的，順序?yàn)樽蠼Y(jié)點(diǎn)<根節(jié)點(diǎn)<右結(jié)點(diǎn)，這表明二叉排序樹(shù)的中序遍歷結(jié)果是有序的（二叉樹(shù)四種遍歷方式[前序遍歷、中序遍歷、后序遍歷、層序遍歷]將在下面給出）。

二叉搜索樹(shù)的特點(diǎn)：

1. 每個(gè)節(jié)點(diǎn)包含一個(gè)值，每個(gè)節(jié)點(diǎn)至多有兩個(gè)子樹(shù)。
2. 每個(gè)節(jié)點(diǎn)左子樹(shù)節(jié)點(diǎn)的值都小于自身的值，每個(gè)節(jié)點(diǎn)右子樹(shù)節(jié)點(diǎn)的值都大于自身的值。
3. 二叉搜索樹(shù)的查詢(xún)時(shí)間復(fù)雜度是 $O(\log N)$，但是隨著不斷的插入、刪除節(jié)點(diǎn)，二叉樹(shù)的樹(shù)高可能會(huì)不斷變大，當(dāng)一個(gè)二叉搜索樹(shù)所有節(jié)點(diǎn)都只有左子樹(shù)或者都只有右子樹(shù)時(shí)，其查找性能就退化成線(xiàn)性的了。

平衡二叉樹(shù)

平衡二叉樹(shù)又被稱(chēng)為 AVL 樹(shù)，它在符合二叉搜索樹(shù)的條件下，還滿(mǎn)足“高度平衡”，即任何節(jié)點(diǎn)的兩個(gè)子樹(shù)的高度最大差為1。

平衡二叉樹(shù)的產(chǎn)生是為了解決二叉搜索樹(shù)在插入時(shí)發(fā)生線(xiàn)性排列的現(xiàn)象。平衡二叉樹(shù)在插入或刪除數(shù)據(jù)時(shí)，采用旋轉(zhuǎn)的調(diào)整方式，使得二叉樹(shù)在插入數(shù)據(jù)后保持平衡。平衡二叉樹(shù)的查詢(xún)時(shí)間復(fù)雜度最好情況和最壞情況都維持在 $O(\log N)$。但是頻繁旋轉(zhuǎn)會(huì)使插入和刪除犧牲掉 $O(\log N)$ 左右的時(shí)間，不過(guò)相對(duì)二叉搜索樹(shù)來(lái)說(shuō)，時(shí)間上穩(wěn)定了很多。

紅黑樹(shù)

平衡二叉樹(shù)（AVL）為了追求高度平衡，需要通過(guò)平衡處理使得左右子樹(shù)的高度差必須小于等于1。高度平衡帶來(lái)的好處是能夠提供更高的搜索效率，其最壞的查找時(shí)間復(fù)雜度都是 $O(\log N)$。但是由于需要維持這份高度平衡，所付出的代價(jià)就是當(dāng)對(duì)樹(shù)種結(jié)點(diǎn)進(jìn)行插入和刪除時(shí)，需要經(jīng)過(guò)多次旋轉(zhuǎn)實(shí)現(xiàn)復(fù)衡。這導(dǎo)致 AVL 的插入和刪除效率并不高。

為了解決這樣的問(wèn)題，紅黑樹(shù)被提出了。紅黑樹(shù)通過(guò)將結(jié)點(diǎn)進(jìn)行紅黑著色，使得原本高度平衡的樹(shù)結(jié)構(gòu)被稍微打亂，平衡程度降低。紅黑樹(shù)不追求完全平衡，只要求達(dá)到部分平衡。這是一種折中的方案，大大提高了結(jié)點(diǎn)刪除和插入的效率，更加實(shí)用。

紅黑樹(shù)VS平衡二叉樹(shù)

除了上面所提及的樹(shù)結(jié)構(gòu)，還有許多廣泛應(yīng)用在數(shù)據(jù)庫(kù)、磁盤(pán)存儲(chǔ)等場(chǎng)景下的樹(shù)結(jié)構(gòu)。比如B樹(shù)、B+樹(shù)等。這里就先不介紹了誒。

樹(shù)的應(yīng)用

1. 文件系統(tǒng)：文件系統(tǒng)通常使用樹(shù)的結(jié)構(gòu)來(lái)組織文件和目錄。樹(shù)形結(jié)構(gòu)的特性使得文件系統(tǒng)可以方便地進(jìn)行文件的查找、插入和刪除操作。
2. 數(shù)據(jù)庫(kù)索引：數(shù)據(jù)庫(kù)索引是一種數(shù)據(jù)結(jié)構(gòu)，用于加快數(shù)據(jù)庫(kù)中數(shù)據(jù)的訪(fǎng)問(wèn)速度。常見(jiàn)的數(shù)據(jù)庫(kù)索引結(jié)構(gòu)，如B樹(shù)和B+樹(shù)，利用樹(shù)的特性實(shí)現(xiàn)高效的數(shù)據(jù)檢索。
3. 表達(dá)式解析：在編譯器和解釋器中，樹(shù)結(jié)構(gòu)常用于表示和解析數(shù)學(xué)表達(dá)式。表達(dá)式樹(shù)（Expression Tree）可以將復(fù)雜的數(shù)學(xué)表達(dá)式轉(zhuǎn)化為樹(shù)的形式，便于計(jì)算和優(yōu)化。
4. 圖形算法：許多圖形算法，如最短路徑算法和最小生成樹(shù)算法，都可以使用樹(shù)的結(jié)構(gòu)進(jìn)行表示和求解。樹(shù)的特性可以幫助解決圖形問(wèn)題中的路徑搜索和優(yōu)化。

二叉樹(shù)

二叉樹(shù)的性質(zhì)

1. 在二叉樹(shù)的第 $i$ 層上至多有 $2^{i?1}$ 個(gè)結(jié)點(diǎn) $(i\ge 1)$。

2. 深度為 $k$ 的二叉樹(shù)至多有 $2^k?1$ 個(gè)結(jié)點(diǎn) $(k\ge 1)$。

3. 對(duì)任何一棵二叉樹(shù) T，如果度為0，其葉結(jié)點(diǎn)個(gè)數(shù)為 $n_0$，度為2的分支結(jié)點(diǎn)個(gè)數(shù)為 $n_2$，則有$n_0＝n_2+1$。

4. 具有 $n$ 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為 $?{\log }_{2}n?+1$（$?x?$表示不大于 $x$ 的最大整數(shù)）。

5. 如果對(duì)一棵有 $n$ 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)（其深度為 $?{\log }_{2}n?+1$）的結(jié)點(diǎn)按層序編號(hào)（從第1層到第 $?{\log }_{2}n?+1$ 層，每層從左到右），則對(duì)于任意結(jié)點(diǎn) $i$（$1\le i\le n$） 有：
   (1). 如果 $i=1$，則結(jié)點(diǎn) $i$ 是二叉樹(shù)的根，無(wú)雙親；如果 $i>1$，則其雙親是結(jié)點(diǎn) $?i/2?$。
   (2). 如果 $2i>n$，則結(jié)點(diǎn) $i$ 無(wú)左孩子（結(jié)點(diǎn) $i$ 為葉子結(jié)點(diǎn)）；否則其左孩子是結(jié)點(diǎn) $2i$。
   (3). 如果 $2i<n$，則結(jié)點(diǎn) $i$無(wú)右孩子；否則其右孩子是結(jié)點(diǎn) $2i+1$。

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

二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)
前面我們已經(jīng)談到了樹(shù)的存儲(chǔ)結(jié)構(gòu),并且談到順序存儲(chǔ)對(duì)樹(shù)這種—對(duì)多的關(guān)系結(jié)構(gòu)實(shí)現(xiàn)起來(lái)是比較困難的。但是二叉樹(shù)是—種特殊的樹(shù),由于它的特殊性,使得用順序存儲(chǔ)結(jié)構(gòu)也可以實(shí)現(xiàn)。
順序結(jié)構(gòu)存儲(chǔ)就是使用數(shù)組來(lái)存儲(chǔ)，一般使用數(shù)組只適合表示完全二叉樹(shù)。因?yàn)椴皇峭耆鏄?shù)會(huì)有空間的浪費(fèi)。

二叉鏈表
既然順序存儲(chǔ)適用性不強(qiáng)，我們就要考慮鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。二叉樹(shù)每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩子，所以為它設(shè)計(jì)一個(gè)數(shù)據(jù)域和兩個(gè)指針域是比較自然的想法，我們稱(chēng)這樣的鏈表叫做二叉鏈表。結(jié)點(diǎn)結(jié)構(gòu)圖如下表所示：

其中 data 是數(shù)據(jù)域；lchild 和 rchild 都是指針域，分別存放指向左孩子和右孩子的指針。

以下是我們的二叉鏈表的結(jié)點(diǎn)結(jié)構(gòu)定義代碼:

/* 二叉樹(shù)的二叉鏈表結(jié)點(diǎn)結(jié)構(gòu)定義*/
typedef struct BiTNode			// 結(jié)點(diǎn)結(jié)構(gòu)
{
	TElemType data;				 // 結(jié)點(diǎn)中的數(shù)據(jù)域
    struct BiTNode *lchild,*rchild;    // 左右孩子指針       
}BiTNode,*BiTree;

結(jié)構(gòu)示意圖如下圖所示：

二叉樹(shù)的遍歷

二叉樹(shù)的遍歷（traversing binary tree）是二叉樹(shù)的一種重要操作。二叉樹(shù)的遍歷是指從根結(jié)點(diǎn)出發(fā)，按照某種次序依次訪(fǎng)問(wèn)二叉樹(shù)中的所有結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)被訪(fǎng)問(wèn)一次且僅被訪(fǎng)問(wèn)一次。

這里有兩個(gè)關(guān)鍵詞：訪(fǎng)問(wèn)和次序。訪(fǎng)問(wèn)其實(shí)是要根據(jù)實(shí)際的需要來(lái)確定具體做什么,比如對(duì)每個(gè)結(jié)點(diǎn)進(jìn)行相關(guān)計(jì)算，輸出打印等，它算作是—個(gè)抽象操作。在這里我們可以簡(jiǎn)單地假定訪(fǎng)問(wèn)就是輸出結(jié)點(diǎn)的數(shù)據(jù)信息。

二叉樹(shù)的遍歷次序不同干線(xiàn)性結(jié)構(gòu),最多也就是從頭至尾、循環(huán)、雙向等簡(jiǎn)單的遍歷方式。樹(shù)的結(jié)點(diǎn)之間不存在唯一的前驅(qū)和后繼關(guān)系,在訪(fǎng)問(wèn)一個(gè)結(jié)點(diǎn)后,下一個(gè)被訪(fǎng)問(wèn)的結(jié)點(diǎn)面臨著不同的選擇。

先序遍歷

算法講解

• 若二叉樹(shù)為空，則空操作返回，否則遍歷順序：根結(jié)點(diǎn)->左子樹(shù)->右子樹(shù)。
• 動(dòng)態(tài)圖解：和上面的動(dòng)態(tài)圖一樣，先序遍歷就像一個(gè)小人從根結(jié)點(diǎn)開(kāi)始，圍繞二叉樹(shù)的外圈開(kāi)始跑（遇到縫隙就鉆進(jìn)去），按照跑的順序，依次輸出序列。

代碼演示

void PreOrderTraversal(BiTree BT)
{
    if( BT ！= NULL ) 
    {
        printf(“%d\n”, BT->Data);        //對(duì)節(jié)點(diǎn)的數(shù)據(jù)進(jìn)行打印          
        PreOrderTraversal(BT->Left);     //訪(fǎng)問(wèn)左子樹(shù)
        PreOrderTraversal(BT->Right);    //訪(fǎng)問(wèn)右子樹(shù)
    }
}

中序遍歷

算法講解

• 若二叉樹(shù)為空，則空操作返回，否則遍歷順序：左子樹(shù)->根結(jié)點(diǎn)->右子樹(shù)。
• 動(dòng)態(tài)圖解：中序遍歷就像投影儀一樣，將二叉樹(shù)從最左側(cè)到最右側(cè)依次投影到同一水平線(xiàn)上面，得到的從左到右的相關(guān)序列就是二叉樹(shù)的中序遍歷。

代碼演示

void InOrderTraversal(BiTree BT)
{
    if(BT ！= NULL)
    {
        InOrderTraversal(BT->Left);
        printf("%d\n", BT->Data);
        InOrderTraversal(BT->Right);
    }
}

后序遍歷

算法講解

• 若二叉樹(shù)為空，則空操作返回，否則遍歷順序：左子樹(shù)->右子樹(shù)->根結(jié)點(diǎn)。
• 動(dòng)態(tài)圖解：后序遍歷就像剪葡萄，只能一個(gè)個(gè)剪，不能讓超過(guò)1個(gè)的葡萄一起掉下來(lái)，那就錯(cuò)了。例如上圖中的 B，剪去 B 后面的 D、E、H、I、J 都會(huì)掉下來(lái)（達(dá)咩），而 H 剪去只會(huì)掉下 H，規(guī)律就是這個(gè)規(guī)律。

代碼演示

void PostOrderTraversal(BiTree BT)
{
    if (BT ！= NULL)
    {
        PostOrderTraversal(BT->Left);
        PostOrderTraversal(BT->Right);
        printf("%d\n", BT->Data);
    }
}

層次遍歷

層次遍歷就是從根節(jié)點(diǎn)開(kāi)始，一層一層，從上到下，每層從左到右，依次取值。

代碼演示

void LevelOrder(BiTree T){
	InitQueue(Q);				//初始化輔助隊(duì)列
	BiTree p;
	EnQueue(Q,T);				//將根結(jié)點(diǎn)入隊(duì)
	while(!IsEmpty(Q))
	{							//隊(duì)列不空則循環(huán)
		DeQueue(Q,p);			//隊(duì)頭結(jié)點(diǎn)出隊(duì)
		visit(p);				//訪(fǎng)問(wèn)出隊(duì)結(jié)點(diǎn)
		if(p->1child!=NULL)
			EnQueue(Q,p->lchild);//左子樹(shù)不空，則左子樹(shù)根結(jié)點(diǎn)入隊(duì)
		if(p->rchild!=NULL)
			EnQueue(Q,p->rchild);//右子樹(shù)不空，則右子樹(shù)根結(jié)點(diǎn)入隊(duì)
	}
}

C語(yǔ)言

以下是使用C語(yǔ)言實(shí)現(xiàn)二叉樹(shù)（包括創(chuàng)建樹(shù)、插入結(jié)點(diǎn)、刪除結(jié)點(diǎn)、遍歷樹(shù)、計(jì)算樹(shù)的深度/高度和大小等基礎(chǔ)操作）的示例代碼：

#include <stdio.h>
#include <stdlib.h>

// 定義二叉樹(shù)節(jié)點(diǎn)
typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

// 創(chuàng)建新節(jié)點(diǎn)
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        return NULL;
    }
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 插入節(jié)點(diǎn)（遞歸實(shí)現(xiàn)）
Node* insertNode(Node* root, int data) {
    if (root == NULL) {
        return createNode(data);
    } else {
        if (data <= root->data) {
            root->left = insertNode(root->left, data);
        } else {
            root->right = insertNode(root->right, data);
        }
        return root;
    }
}

// 刪除節(jié)點(diǎn)
Node* deleteNode(Node* root, int data) {
    if (root == NULL) {
        return root;
    } else if (data < root->data) {
        root->left = deleteNode(root->left, data);
    } else if (data > root->data) {
        root->right = deleteNode(root->right, data);
    } else {
        if (root->left == NULL && root->right == NULL) {
            free(root);
            root = NULL;
        } else if (root->left == NULL) {
            Node* temp = root;
            root = root->right;
            free(temp);
        } else if (root->right == NULL) {
            Node* temp = root;
            root = root->left;
            free(temp);
        } else {
            Node* minRight = findMin(root->right);
            root->data = minRight->data;
            root->right = deleteNode(root->right, minRight->data);
        }
    }
    return root;
}

// 查找最小節(jié)點(diǎn)
Node* findMin(Node* root) {
    while (root->left != NULL) {
        root = root->left;
    }
    return root;
}

// 計(jì)算樹(shù)的深度/高度
int calculateHeight(Node* root) {
    if (root == NULL) {
        return 0;
    } else {
        int leftHeight = calculateHeight(root->left);
        int rightHeight = calculateHeight(root->right);
        return (leftHeight > rightHeight) ? (leftHeight + 1) : (rightHeight + 1);
    }
}

// 計(jì)算樹(shù)的大小（節(jié)點(diǎn)數(shù)）
int calculateSize(Node* root) {
    if (root == NULL) {
        return 0;
    } else {
        int leftSize = calculateSize(root->left);
        int rightSize = calculateSize(root->right);
        return leftSize + rightSize + 1;
    }
}

// 先序遍歷（根-左-右）
void preorderTraversal(Node* root) {
    if (root != NULL) {
        printf("%d ", root->data);
        preorderTraversal(root->left);
        preorderTraversal(root->right);
    }
}

// 中序遍歷（左-根-右）
void inorderTraversal(Node* root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        printf("%d ", root->data);
        inorderTraversal(root->right);
    }
}

// 后序遍歷（左-右-根）
void postorderTraversal(Node* root) {
    if (root != NULL) {
        postorderTraversal(root->left);
        postorderTraversal(root->right);
        printf("%d ", root->data);
    }
}

int main() {
    Node* root = NULL;

    // 插入節(jié)點(diǎn)
    root = insertNode(root, 4);
    root = insertNode(root, 2);
    root = insertNode(root, 6);
    root = insertNode(root, 1);
    root = insertNode(root, 3);
    root = insertNode(root, 5);
    root = insertNode(root, 7);

    // 先序遍歷
    printf("Preorder traversal: ");
    preorderTraversal(root);
    printf("\n");

    // 中序遍歷
    printf("Inorder traversal: ");
    inorderTraversal(root);
    printf("\n");

    // 后序遍歷
    printf("Postorder traversal: ");
    postorderTraversal(root);
    printf("\n");

    // 刪除節(jié)點(diǎn)
    root = deleteNode(root, 3);

    // 先序遍歷（刪除節(jié)點(diǎn)后）
    printf("Preorder traversal (after deletion): ");
    preorderTraversal(root);
    printf("\n");

    // 計(jì)算樹(shù)的深度/高度
    int height = calculateHeight(root);
    printf("Tree height: %d\n", height);

    // 計(jì)算樹(shù)的大?。ü?jié)點(diǎn)數(shù)）
    int size = calculateSize(root);
    printf("Tree size: %d\n", size);

    return 0;
}

結(jié)論

樹(shù)作為一種重要的數(shù)據(jù)結(jié)構(gòu)，在計(jì)算機(jī)科學(xué)中有廣泛的應(yīng)用。通過(guò)理解樹(shù)的基本概念、常見(jiàn)類(lèi)型和應(yīng)用場(chǎng)景，我們可以更好地理解和運(yùn)用樹(shù)結(jié)構(gòu)解決實(shí)際問(wèn)題。通過(guò)進(jìn)一步的學(xué)習(xí)和實(shí)踐，我們可以不斷深入和拓展樹(shù)的應(yīng)用領(lǐng)域，提升算法和數(shù)據(jù)結(jié)構(gòu)的能力。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-482822.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)之樹(shù)與二叉樹(shù)——算法與數(shù)據(jù)結(jié)構(gòu)入門(mén)筆記（五）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！