【數(shù)據(jù)結(jié)構(gòu)之二叉樹(shù)】二叉樹(shù)的相關(guān)概念及原理

作者：行小觀 2021-04-19 07:47:42

使用具有一對(duì)多關(guān)系的數(shù)據(jù)結(jié)構(gòu)啦!有這種數(shù)據(jù)結(jié)構(gòu)嗎?有!本文就來(lái)介紹這種數(shù)據(jù)結(jié)構(gòu) —— 樹(shù)及其特殊形式的二叉樹(shù)。

[[393908]]

0. 前言

到目前為止，我們已經(jīng)講述了順序表、鏈表、棧、隊(duì)列四種數(shù)據(jù)結(jié)構(gòu)，它們有一個(gè)共同的特點(diǎn)，就是它們都是線性表，換句話來(lái)說(shuō)，它們都是線性結(jié)構(gòu)，像一根繩子一樣。

四種線性數(shù)據(jù)結(jié)構(gòu)

在文章【線性表】已經(jīng)介紹過(guò)線性表的定義了，即由若干元素按照線性結(jié)構(gòu)(一對(duì)一的關(guān)系)組成的有限序列。

關(guān)鍵詞是一對(duì)一的關(guān)系。

顯然，在復(fù)雜的現(xiàn)實(shí)社會(huì)中，這種一對(duì)一的關(guān)系是不能較好的滿足我們的需求的。

比如說(shuō)，父母和多個(gè)孩子之間的關(guān)系，一個(gè)父親/母親對(duì)應(yīng)多個(gè)孩子，這顯然不是一對(duì)一，而是一對(duì)多的關(guān)系。那么此時(shí)我們?nèi)绾蝸?lái)描述這種一對(duì)多的關(guān)系呢?

當(dāng)然是使用具有一對(duì)多關(guān)系的數(shù)據(jù)結(jié)構(gòu)啦!有這種數(shù)據(jù)結(jié)構(gòu)嗎?有!本文就來(lái)介紹這種數(shù)據(jù)結(jié)構(gòu) —— 樹(shù)及其特殊形式的二叉樹(shù)。

1. 識(shí)樹(shù)

1.0. 什么是樹(shù)?

提到樹(shù)(Tree)，大家腦海中首先浮出的畫面應(yīng)該是類似這樣的：

圖片來(lái)自網(wǎng)絡(luò)

之所以我們會(huì)用“樹(shù)”這個(gè)名詞來(lái)命名具有“一對(duì)多關(guān)系”特性的數(shù)據(jù)結(jié)構(gòu)，是因?yàn)闃?shù)剛好能夠很形象地詮釋這種特性。我們來(lái)分析一下。

看一下上圖中的樹(shù)(土地以上的部分)，它有一個(gè)樹(shù)根，從樹(shù)根開(kāi)始往上分叉，主樹(shù)干分叉成許多次樹(shù)干，次樹(shù)干又繼續(xù)分叉為許多小樹(shù)枝，小樹(shù)枝上有許多葉子……

主樹(shù)干對(duì)次樹(shù)干、次樹(shù)干對(duì)小樹(shù)枝、小樹(shù)枝對(duì)葉子都是一對(duì)多的關(guān)系，我們用圓圈代表樹(shù)干和葉子，把自然界的樹(shù)倒過(guò)來(lái)進(jìn)行一次抽象，得下圖(為了方便起見(jiàn)，我們的數(shù)據(jù)全為字符類型)：

一棵樹(shù)

可以看到，現(xiàn)實(shí)中的樹(shù)完美契合我們需要的數(shù)據(jù)結(jié)構(gòu)，所以我們稱這種數(shù)據(jù)結(jié)構(gòu)為樹(shù)(Tree)。

1.1. 名詞與概念

我們按圖索驥，來(lái)認(rèn)識(shí)樹(shù)的相關(guān)名詞。

子樹(shù)：樹(shù)是一個(gè)有限集合，子樹(shù)則是該集合的子集。就像套娃一樣，一棵樹(shù)下面還包含著其子樹(shù)。

比如，樹(shù)T1 的子樹(shù)為樹(shù)T2、T3、T4，樹(shù)T2的子樹(shù)為 T5、T6. 上圖中還有許多子樹(shù)沒(méi)有標(biāo)記出來(lái)。

結(jié)點(diǎn)(Node)：一個(gè)結(jié)點(diǎn)包括一個(gè)數(shù)據(jù)元素和若干指向其子樹(shù)分支。

比如，在樹(shù)T1 中，結(jié)點(diǎn)A 包括一個(gè)數(shù)據(jù)元素A 和三個(gè)指向其子樹(shù)的分支。上圖中共有 17 個(gè)結(jié)點(diǎn)。

根結(jié)點(diǎn)(Root)：一顆樹(shù)只有一個(gè)樹(shù)根，這是常識(shí)。在數(shù)據(jù)結(jié)構(gòu)中，“樹(shù)根”即根節(jié)點(diǎn)。

比如，結(jié)點(diǎn)A 是樹(shù) T1 的根結(jié)點(diǎn);結(jié)點(diǎn)C 是樹(shù)T1 的子結(jié)點(diǎn)，是樹(shù) T3 的根結(jié)點(diǎn)。

度(Degree)：一個(gè)結(jié)點(diǎn)擁有的子樹(shù)數(shù)。

比如，結(jié)點(diǎn)A 的度為 3，結(jié)點(diǎn)G 的度為 3，結(jié)點(diǎn)H 的度為 1.

葉子(Leaf)/ 終端結(jié)點(diǎn)：度為 0 的結(jié)點(diǎn)被稱為葉子結(jié)點(diǎn)，很形象吧。

比如，對(duì)于樹(shù) T1來(lái)說(shuō)，結(jié)點(diǎn)F、I、K、L、M、N、O、P、Q 均為葉子。

分支結(jié)點(diǎn) / 非終端結(jié)點(diǎn)：和葉子結(jié)點(diǎn)相對(duì)，即度不為 0 的結(jié)點(diǎn)。

內(nèi)部結(jié)點(diǎn)：顧名思義，在樹(shù)內(nèi)部的結(jié)點(diǎn)，即不是根結(jié)點(diǎn)和葉子結(jié)點(diǎn)的結(jié)點(diǎn)。

孩子(Child)、雙親(Parent)、兄弟(Sibling)、堂兄弟、祖先、子孫這些概念和族譜上的相同。

比如，對(duì)于結(jié)點(diǎn)B 來(lái)說(shuō)：結(jié)點(diǎn)A 是其雙親結(jié)點(diǎn)，結(jié)點(diǎn)E、F 是其孩子結(jié)點(diǎn)，結(jié)點(diǎn)C、D 是其兄弟結(jié)點(diǎn)，結(jié)點(diǎn)K 是其子孫結(jié)點(diǎn)。

層次(Level)：從根結(jié)點(diǎn)開(kāi)始，根為第一次，根的孩子為第二層，依次往下。

比如，結(jié)點(diǎn)K 在樹(shù) T1 中的層次為 4.

深度(Depth)/ 高度：指樹(shù)的最大層次。

比如，樹(shù) T1 的深度為 4.

有序樹(shù)：如果結(jié)點(diǎn)的各子樹(shù)從左到右是有次序的、不能顛倒，則為有序樹(shù)，否則為無(wú)序樹(shù)。對(duì)于有序樹(shù)的孩子來(lái)說(shuō)，最左邊的孩子稱為第一個(gè)孩子，最右邊的孩子稱為最后一個(gè)孩子。

比如，如果樹(shù)T1是一個(gè)有序樹(shù)，則其根結(jié)點(diǎn)的第一個(gè)孩子為結(jié)點(diǎn)B，最后一個(gè)孩子為結(jié)點(diǎn)D.

1.2. 樹(shù)的遞歸概念

前面已經(jīng)介紹了樹(shù)的輪廓和相關(guān)名詞概念，為了回答什么是樹(shù)這個(gè)問(wèn)題，我們這里還需要介紹三種常見(jiàn)的樹(shù)結(jié)構(gòu)。

【空樹(shù)】：一顆空樹(shù)，即沒(méi)有結(jié)點(diǎn)的樹(shù)。

空樹(shù)

【只有根結(jié)點(diǎn)的樹(shù)】：只有一個(gè)根節(jié)點(diǎn)，沒(méi)有其他結(jié)點(diǎn)。

只有根結(jié)點(diǎn)的樹(shù)

【普通的樹(shù)】

普通樹(shù)

現(xiàn)在我們能來(lái)回答什么是樹(shù)了：

樹(shù)(Tree)是由 N (N >= 0) 個(gè)結(jié)點(diǎn)構(gòu)成的有限集合。

當(dāng) N = 0 時(shí)，樹(shù)為空樹(shù)
當(dāng) N = 1 時(shí)，樹(shù)只有一個(gè)根結(jié)點(diǎn)
當(dāng) N > 1 時(shí)，樹(shù)除了一個(gè)根結(jié)點(diǎn)外，其余結(jié)點(diǎn)又可分為若干個(gè)不相交的有限集合，我們稱之為子樹(shù)。

非空樹(shù)有且僅有一個(gè)根結(jié)點(diǎn)。

樹(shù)的一對(duì)多的關(guān)系存在于雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間。

在樹(shù)中，因?yàn)榇嬖跇?shù)、子樹(shù)的概念，所以樹(shù)的子樹(shù)仍是一顆樹(shù)，子樹(shù)的子樹(shù)仍是一棵樹(shù)。

舉個(gè)例子：人類的孩子仍是人類，人類的孩子的孩子仍是人類。

因?yàn)榇嬖陔p親、孩子、子孫的概念，所以根結(jié)點(diǎn)的孩子結(jié)點(diǎn)可以其子樹(shù)的根結(jié)點(diǎn)。

舉個(gè)例子：一個(gè)人，在其孩子看來(lái)是父親，在其父母看來(lái)是兒子。

這種概念，就是遞歸的概念。

即，對(duì)于某個(gè)“事物”而言，它的“孩子”和它本身并無(wú)實(shí)質(zhì)區(qū)別，它做的事，它的“孩子”也會(huì)做、也要做。一直向下，“孫子”“曾孫”“玄孫”皆是如此。

為了說(shuō)明遞歸這個(gè)概念，我們將上圖的樹(shù)遞歸地分解為子樹(shù)，下圖中每個(gè)區(qū)域都是一顆樹(shù)(或子樹(shù))：

遞歸解樹(shù)

分解到最后，我們最終得到的，可以說(shuō)是葉子結(jié)點(diǎn)，也可以說(shuō)是只有根結(jié)點(diǎn)的樹(shù)。如結(jié)點(diǎn)F、K、L.

在分解的過(guò)程中，我們還可以發(fā)現(xiàn)，對(duì)于每個(gè)結(jié)點(diǎn)來(lái)說(shuō)，我們都可以將其看作某棵樹(shù)(子樹(shù))的根結(jié)點(diǎn)。比如結(jié)點(diǎn)E、I都是某棵子樹(shù)的根結(jié)點(diǎn)。這與樹(shù)有且只有一個(gè)根結(jié)點(diǎn)并不矛盾。

這就好比我們說(shuō)，小明只能有一個(gè)親生父親，但不影響他成為別人的父親。

整個(gè)過(guò)程就像在族譜上從祖宗找到子孫一樣。所以如果對(duì)樹(shù)的概念有啥不了解的，可以找個(gè)族譜翻翻看。

到此，我們可以說(shuō)，樹(shù)的定義是一個(gè)遞歸的定義，樹(shù)是由根結(jié)點(diǎn)和它的若干子樹(shù)組成的，子樹(shù)也是由根結(jié)點(diǎn)和它的若干子樹(shù)組成的……即在樹(shù)的定義中又用到樹(shù)的定義。

1.3. 樹(shù)和線性表的比較

比較

看圖直觀體驗(yàn)何為(前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)間)一對(duì)一的關(guān)系，何為(雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間)一對(duì)多的關(guān)系。

2. 識(shí)二叉樹(shù)

2.0. 什么是二叉樹(shù)?

何為二叉樹(shù)?首先它得是顆樹(shù)，其次它得是二叉的。

前面已經(jīng)初步認(rèn)識(shí)了樹(shù)，它的結(jié)點(diǎn)的孩子數(shù)量是沒(méi)有限制的，即，你想要幾個(gè)孩子就要幾個(gè)孩子，想分幾個(gè)叉就分幾個(gè)叉。

而二叉樹(shù)，則是限制了孩子數(shù)量，即每個(gè)結(jié)點(diǎn)最多只能有兩個(gè)孩子(左孩子和右孩子)，打個(gè)比方就是“二胎樹(shù)”。

二叉樹(shù)

結(jié)點(diǎn)A 的左孩子是結(jié)點(diǎn)B，右孩子是結(jié)點(diǎn)C.

二叉樹(shù)是一種每個(gè)結(jié)點(diǎn)至多有兩棵子樹(shù)(即每個(gè)結(jié)點(diǎn)的度最大為 2 )的有序樹(shù)。

2.1. 二叉樹(shù)的幾種形態(tài)

一、空二叉樹(shù)

二、僅有根結(jié)點(diǎn)的二叉樹(shù)

三、左子樹(shù)為空的二叉樹(shù)

四、右子樹(shù)為空的二叉樹(shù)

五、左右子樹(shù)都不為空的二叉樹(shù)

2.2. 滿二叉樹(shù)和完全二叉樹(shù)

滿二叉樹(shù)的特點(diǎn)在于“滿”，即每層的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)。

滿二叉樹(shù)

T2 的第 3 層次沒(méi)有達(dá)到最大結(jié)點(diǎn)數(shù)，缺了 1 個(gè);T3 的第 4 層次沒(méi)有達(dá)到最大結(jié)點(diǎn)數(shù)，缺了 7 個(gè)。

完全二叉樹(shù)是相對(duì)于滿二叉樹(shù)來(lái)說(shuō)的，見(jiàn)下圖：

紅色部分為編號(hào)

二叉樹(shù)是有序樹(shù)，對(duì)一顆滿二叉樹(shù)和一顆完全二叉樹(shù)按「自上向下，自左向右」的順序進(jìn)行編號(hào)，如上圖。

完全二叉樹(shù)中的所有結(jié)點(diǎn)的編號(hào)必須和滿二叉樹(shù)的相同編號(hào)的結(jié)點(diǎn)在位置上完全相同。

換句話說(shuō)，完全二叉樹(shù)的結(jié)點(diǎn)按「自上向下，自左向右」的順序不能中斷。T3 的結(jié)點(diǎn)C 沒(méi)有左孩子，顯然按那個(gè)順序是中斷的。

3. 二叉樹(shù)的遍歷

3.0. 如何遍歷?

在線性表中，我們的遍歷非常簡(jiǎn)單粗暴，找到線性表頭，使用循環(huán)直接一股腦的到線性表尾，即完成遍歷了。在樹(shù)中，我們不能在做這么簡(jiǎn)單粗暴的事了，因?yàn)闃?shù)是一對(duì)多的關(guān)系，所以從頭到尾的遍歷是不可能的。

遍歷的實(shí)質(zhì)是，將線性排列的元素順序打印出來(lái)。(遍歷不止干打印的事，為了方便起見(jiàn)，我們的遍歷是打印元素)

而遍歷樹(shù)的矛盾在于，我們的樹(shù)不是線性的，為了解決這個(gè)矛盾，我們可不可以約定好某種順序，將樹(shù)的元素按這種順序線性排列起來(lái)，然后遍歷就是從頭到尾的簡(jiǎn)單粗暴之事了?答案是可以的。

我們知道樹(shù)是遞歸的定義，二叉樹(shù)是由根結(jié)點(diǎn)、左子樹(shù)、右子樹(shù)這三部分遞歸地組合而成的。所以我們要約定的就是這三部分誰(shuí)先誰(shuí)后。

按照人們寫字先左后右的約定，我們也約定先左子樹(shù)后右子樹(shù)的順序(當(dāng)然你可以先右后左)，那么根結(jié)點(diǎn)就只有三個(gè)位置可以放了。

根結(jié)點(diǎn) >> 左子樹(shù) >> 右子樹(shù)，稱為先序(根)遍歷

左子樹(shù) >> 根結(jié)點(diǎn) >> 右子樹(shù)，稱為中序(根)遍歷

左子樹(shù) >> 右子樹(shù) >> 根結(jié)點(diǎn)，稱為后序(根)遍歷

約定好之后，只需要按照順序遞歸地來(lái)就好了，就像找族譜一樣。

下面以遍歷下圖二叉樹(shù)為例：

為了方便起見(jiàn)，我們將 null 畫出來(lái)，且將所有子樹(shù)用顏色標(biāo)志出來(lái)。

3.1. 先序遍歷

先序遍歷的遞歸描述如下：

若二叉樹(shù)為空，則空操作;否則：

訪問(wèn)根結(jié)點(diǎn)
先序遍歷左子樹(shù)
先序遍歷右子樹(shù)

你可能會(huì)問(wèn)，怎么只有訪問(wèn)根結(jié)點(diǎn)這一步?左孩子和右孩子結(jié)點(diǎn)呢?前面說(shuō)過(guò)一句話：對(duì)于每個(gè)結(jié)點(diǎn)來(lái)說(shuō)，我們都可以將其看作某棵樹(shù)(子樹(shù))的根結(jié)點(diǎn)。就像你的兒子會(huì)成為別人的父親一樣。所以只要遞歸地訪問(wèn)根結(jié)點(diǎn)，將每個(gè)結(jié)點(diǎn)遞歸地變?yōu)?ldquo;根結(jié)點(diǎn)”，我們就能完成遍歷。

所以與其說(shuō)是在遍歷結(jié)點(diǎn)，不如說(shuō)是在遍歷「根結(jié)點(diǎn)」，我們只是在遞歸地把「所有根結(jié)點(diǎn)」找出來(lái)并輸出而已。(因?yàn)槊總€(gè)結(jié)點(diǎn)都可以看做是根結(jié)點(diǎn))

所以遍歷的重點(diǎn)，在于將所有結(jié)點(diǎn)轉(zhuǎn)化為根結(jié)點(diǎn)看待，又因?yàn)槊靠脴?shù)有且僅有一個(gè)根結(jié)點(diǎn)，所以我們要不斷地遞歸分解子樹(shù)(先左子樹(shù)后右子樹(shù))，直到分解到 NULL為止。

過(guò)程如下：