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

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

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

[[393908]]

0. 前言

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

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

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

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

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

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

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

1. 識(shí)樹

1.0. 什么是樹?

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

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

之所以我們會(huì)用“樹”這個(gè)名詞來命名具有“一對多關(guān)系”特性的數(shù)據(jù)結(jié)構(gòu)，是因?yàn)闃鋭偤媚軌蚝苄蜗蟮卦忈屵@種特性。我們來分析一下。

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

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

一棵樹

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

1.1. 名詞與概念

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

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

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

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

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

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

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

度(Degree)：一個(gè)結(jié)點(diǎn)擁有的子樹數(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)，很形象吧。

比如，對于樹 T1來說，結(jié)點(diǎn)F、I、K、L、M、N、O、P、Q 均為葉子。

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

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

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

比如，對于結(jié)點(diǎn)B 來說：結(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)開始，根為第一次，根的孩子為第二層，依次往下。

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

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

比如，樹 T1 的深度為 4.

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

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

1.2. 樹的遞歸概念

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

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

空樹

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

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

【普通的樹】

普通樹

現(xiàn)在我們能來回答什么是樹了：

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

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

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

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

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

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

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

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

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

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

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

遞歸解樹

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

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

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

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

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

1.3. 樹和線性表的比較

比較

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

2. 識(shí)二叉樹

2.0. 什么是二叉樹?

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

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

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

二叉樹

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

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

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

一、空二叉樹

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

三、左子樹為空的二叉樹

四、右子樹為空的二叉樹

五、左右子樹都不為空的二叉樹

2.2. 滿二叉樹和完全二叉樹

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

滿二叉樹

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

完全二叉樹是相對于滿二叉樹來說的，見下圖：

紅色部分為編號

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

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

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

3. 二叉樹的遍歷

3.0. 如何遍歷?

在線性表中，我們的遍歷非常簡單粗暴，找到線性表頭，使用循環(huán)直接一股腦的到線性表尾，即完成遍歷了。在樹中，我們不能在做這么簡單粗暴的事了，因?yàn)闃涫且粚Χ嗟年P(guān)系，所以從頭到尾的遍歷是不可能的。

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

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

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

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

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

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

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

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

下面以遍歷下圖二叉樹為例：

為了方便起見，我們將 null 畫出來，且將所有子樹用顏色標(biāo)志出來。

3.1. 先序遍歷

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

若二叉樹為空，則空操作;否則：

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

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

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

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

過程如下：