前言

樹是數(shù)據(jù)結(jié)構(gòu)中的重中之重，尤其以各類二叉樹為學(xué)習(xí)的難點(diǎn)。一直以來，對(duì)于樹的掌握都是模棱兩可的狀態(tài)，現(xiàn)在希望通過寫一個(gè)關(guān)于二叉樹的專題系列。在學(xué)習(xí)與總結(jié)的同時(shí)更加深入的了解掌握二叉樹。本系列文章將著重介紹一般二叉樹、完全二叉樹、滿二叉樹、線索二叉樹、霍夫曼樹、二叉排序樹、平衡二叉樹、紅黑樹、B樹。希望各位讀者能夠關(guān)注專題，并給出相應(yīng)意見，通過系列的學(xué)習(xí)做到心中有“樹”。

1.重點(diǎn)概念

1.1 結(jié)點(diǎn)概念

結(jié)點(diǎn)是數(shù)據(jù)結(jié)構(gòu)中的基礎(chǔ)，是構(gòu)成復(fù)雜數(shù)據(jù)結(jié)構(gòu)的基本組成單位。

1.2 樹結(jié)點(diǎn)聲明

本系列文章中提及的結(jié)點(diǎn)專指樹的結(jié)點(diǎn)。例如：結(jié)點(diǎn)A在圖中表示為：

2樹

2.1 定義

樹（Tree）是n（n>=0)個(gè)結(jié)點(diǎn)的有限集。n=0時(shí)稱為空樹。在任意一顆非空樹中：

1）有且僅有一個(gè)特定的稱為根（Root）的結(jié)點(diǎn)；

2）當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集T1、T2、......、Tn，其中每一個(gè)集合本身又是一棵樹，并且稱為根的子樹。

此外，樹的定義還需要強(qiáng)調(diào)以下兩點(diǎn)：

1）n>0時(shí)根結(jié)點(diǎn)是唯一的，不可能存在多個(gè)根結(jié)點(diǎn)，數(shù)據(jù)結(jié)構(gòu)中的樹只能有一個(gè)根結(jié)點(diǎn)。

2）m>0時(shí)，子樹的個(gè)數(shù)沒有限制，但它們一定是互不相交的。

示例樹：

圖2.1為一棵普通的樹：

圖2.1 普通樹

由樹的定義可以看出，樹的定義使用了遞歸的方式。遞歸在樹的學(xué)習(xí)過程中起著重要作用，如果對(duì)于遞歸不是十分了解，建議先看看遞歸算法

2.2 結(jié)點(diǎn)的度

結(jié)點(diǎn)擁有的子樹數(shù)目稱為結(jié)點(diǎn)的度。

圖2.2中標(biāo)注了圖2.1所示樹的各個(gè)結(jié)點(diǎn)的度。

圖2.2 度示意圖

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

結(jié)點(diǎn)子樹的根結(jié)點(diǎn)為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)。相應(yīng)該結(jié)點(diǎn)稱為孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn)。

圖2.2中，A為B的雙親結(jié)點(diǎn)，B為A的孩子結(jié)點(diǎn)。

同一個(gè)雙親結(jié)點(diǎn)的孩子結(jié)點(diǎn)之間互稱兄弟結(jié)點(diǎn)。

圖2.2中，結(jié)點(diǎn)B與結(jié)點(diǎn)C互為兄弟結(jié)點(diǎn)。

2.4 結(jié)點(diǎn)層次

從根開始定義起，根為第一層，根的孩子為第二層，以此類推。

圖2.3表示了圖2.1所示樹的層次關(guān)系

圖2.3 層示意圖

2.5 樹的深度

樹中結(jié)點(diǎn)的最大層次數(shù)稱為樹的深度或高度。圖2.1所示樹的深度為4。

3.二叉樹

3.1 定義

二叉樹是n(n>=0)個(gè)結(jié)點(diǎn)的有限集合，該集合或者為空集（稱為空二叉樹），或者由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的、分別稱為根結(jié)點(diǎn)的左子樹和右子樹組成。

圖3.1展示了一棵普通二叉樹：

圖3.1 二叉樹

3.2 二叉樹特點(diǎn)

由二叉樹定義以及圖示分析得出二叉樹有以下特點(diǎn)：

1）每個(gè)結(jié)點(diǎn)最多有兩顆子樹，所以二叉樹中不存在度大于2的結(jié)點(diǎn)。

2）左子樹和右子樹是有順序的，次序不能任意顛倒。

3）即使樹中某結(jié)點(diǎn)只有一棵子樹，也要區(qū)分它是左子樹還是右子樹。

3.3 二叉樹性質(zhì)

1）在二叉樹的第i層上最多有2i-1 個(gè)節(jié)點(diǎn) 。（i>=1）

2）二叉樹中如果深度為k,那么最多有2k-1個(gè)節(jié)點(diǎn)。(k>=1）

3）n0=n2+1  n0表示度數(shù)為0的節(jié)點(diǎn)數(shù)，n2表示度數(shù)為2的節(jié)點(diǎn)數(shù)。

4）在完全二叉樹中，具有n個(gè)節(jié)點(diǎn)的完全二叉樹的深度為[log2n]+1，其中[log2n]是向下取整。

5）若對(duì)含 n 個(gè)結(jié)點(diǎn)的完全二叉樹從上到下且從左至右進(jìn)行 1 至 n 的編號(hào)，則對(duì)完全二叉樹中任意一個(gè)編號(hào)為 i 的結(jié)點(diǎn)有如下特性：

(1) 若 i=1，則該結(jié)點(diǎn)是二叉樹的根，無雙親, 否則，編號(hào)為 [i/2] 的結(jié)點(diǎn)為其雙親結(jié)點(diǎn);

(2) 若 2i>n，則該結(jié)點(diǎn)無左孩子，  否則，編號(hào)為 2i 的結(jié)點(diǎn)為其左孩子結(jié)點(diǎn)；

(3) 若 2i+1>n，則該結(jié)點(diǎn)無右孩子結(jié)點(diǎn)，  否則，編號(hào)為2i+1 的結(jié)點(diǎn)為其右孩子結(jié)點(diǎn)。

3.4 斜樹

斜樹：所有的結(jié)點(diǎn)都只有左子樹的二叉樹叫左斜樹。所有結(jié)點(diǎn)都是只有右子樹的二叉樹叫右斜樹。這兩者統(tǒng)稱為斜樹。

圖3.2 左斜樹

圖3.3 右斜樹

3.5 滿二叉樹

滿二叉樹：在一棵二叉樹中。如果所有分支結(jié)點(diǎn)都存在左子樹和右子樹，并且所有葉子都在同一層上，這樣的二叉樹稱為滿二叉樹。

滿二叉樹的特點(diǎn)有：

1）葉子只能出現(xiàn)在最下一層。出現(xiàn)在其它層就不可能達(dá)成平衡。

2）非葉子結(jié)點(diǎn)的度一定是2。

3）在同樣深度的二叉樹中，滿二叉樹的結(jié)點(diǎn)個(gè)數(shù)最多，葉子數(shù)最多。

圖3.4 滿二叉樹

3.6 完全二叉樹

完全二叉樹：對(duì)一顆具有n個(gè)結(jié)點(diǎn)的二叉樹按層編號(hào)，如果編號(hào)為i(1<=i<=n)的結(jié)點(diǎn)與同樣深度的滿二叉樹中編號(hào)為i的結(jié)點(diǎn)在二叉樹中位置完全相同，則這棵二叉樹稱為完全二叉樹。

圖3.5展示一棵完全二叉樹

圖3.5 完全二叉樹

特點(diǎn)：

1）葉子結(jié)點(diǎn)只能出現(xiàn)在最下層和次下層。

2）最下層的葉子結(jié)點(diǎn)集中在樹的左部。

3）倒數(shù)第二層若存在葉子結(jié)點(diǎn)，一定在右部連續(xù)位置。

4）如果結(jié)點(diǎn)度為1，則該結(jié)點(diǎn)只有左孩子，即沒有右子樹。

5）同樣結(jié)點(diǎn)數(shù)目的二叉樹，完全二叉樹深度最小。

注：滿二叉樹一定是完全二叉樹，但反過來不一定成立。

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

3.7.1 順序存儲(chǔ)

二叉樹的順序存儲(chǔ)結(jié)構(gòu)就是使用一維數(shù)組存儲(chǔ)二叉樹中的結(jié)點(diǎn)，并且結(jié)點(diǎn)的存儲(chǔ)位置，就是數(shù)組的下標(biāo)索引。

圖3.6

圖3.6所示的一棵完全二叉樹采用順序存儲(chǔ)方式，如圖3.7表示：

圖3.7 順序存儲(chǔ)

由圖3.7可以看出，當(dāng)二叉樹為完全二叉樹時(shí)，結(jié)點(diǎn)數(shù)剛好填滿數(shù)組。

那么當(dāng)二叉樹不為完全二叉樹時(shí)，采用順序存儲(chǔ)形式如何呢？例如：對(duì)于圖3.8描述的二叉樹：

圖3.8.png

其中淺色結(jié)點(diǎn)表示結(jié)點(diǎn)不存在。那么圖3.8所示的二叉樹的順序存儲(chǔ)結(jié)構(gòu)如圖3.9所示：

圖3.9

其中，∧表示數(shù)組中此位置沒有存儲(chǔ)結(jié)點(diǎn)。此時(shí)可以發(fā)現(xiàn)，順序存儲(chǔ)結(jié)構(gòu)中已經(jīng)出現(xiàn)了空間浪費(fèi)的情況。

那么對(duì)于圖3.3所示的右斜樹極端情況對(duì)應(yīng)的順序存儲(chǔ)結(jié)構(gòu)如圖3.10所示：

圖3.10

由圖3.10可以看出，對(duì)于這種右斜樹極端情況，采用順序存儲(chǔ)的方式是十分浪費(fèi)空間的。因此，順序存儲(chǔ)一般適用于完全二叉樹。

3.7.2 二叉鏈表

既然順序存儲(chǔ)不能滿足二叉樹的存儲(chǔ)需求，那么考慮采用鏈?zhǔn)酱鎯?chǔ)。由二叉樹定義可知，二叉樹的每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩子。因此，可以將結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)定義為一個(gè)數(shù)據(jù)和兩個(gè)指

針域。表示方式如圖3.11所示：

圖3.11

定義結(jié)點(diǎn)代碼：

typedef struct BiTNode{

    TElemType data;//數(shù)據(jù)

    struct BiTNode *lchild, *rchild;//左右孩子指針

} BiTNode, *BiTree;

則圖3.6所示的二叉樹可以采用圖3.12表示。

圖3.12

圖3.12中采用一種鏈表結(jié)構(gòu)存儲(chǔ)二叉樹，這種鏈表稱為二叉鏈表。

3.8 二叉樹遍歷

二叉樹的遍歷一個(gè)重點(diǎn)考查的知識(shí)點(diǎn)。

3.8.1 定義

二叉樹的遍歷是指從二叉樹的根結(jié)點(diǎn)出發(fā)，按照某種次序依次訪問二叉樹中的所有結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)被訪問一次，且僅被訪問一次。

二叉樹的訪問次序可以分為四種：

前序遍歷

中序遍歷

后序遍歷

層序遍歷

3.8.2 前序遍歷

前序遍歷通俗的說就是從二叉樹的根結(jié)點(diǎn)出發(fā)，當(dāng)?shù)谝淮蔚竭_(dá)結(jié)點(diǎn)時(shí)就輸出結(jié)點(diǎn)數(shù)據(jù)，按照先向左在向右的方向訪問。

3.13

圖3.13所示二叉樹訪問如下：

從根結(jié)點(diǎn)出發(fā)，則第一次到達(dá)結(jié)點(diǎn)A，故輸出A;

繼續(xù)向左訪問，第一次訪問結(jié)點(diǎn)B，故輸出B；

按照同樣規(guī)則，輸出D，輸出H；

當(dāng)?shù)竭_(dá)葉子結(jié)點(diǎn)H，返回到D，此時(shí)已經(jīng)是第二次到達(dá)D，故不在輸出D，進(jìn)而向D右子樹訪問，D右子樹不為空，則訪問至I，第一次到達(dá)I，則輸出I；

I為葉子結(jié)點(diǎn)，則返回到D，D左右子樹已經(jīng)訪問完畢，則返回到B，進(jìn)而到B右子樹，第一次到達(dá)E，故輸出E；

向E左子樹，故輸出J；

按照同樣的訪問規(guī)則，繼續(xù)輸出C、F、G；

則3.13所示二叉樹的前序遍歷輸出為：

ABDHIEJCFG

3.8.3 中序遍歷

中序遍歷就是從二叉樹的根結(jié)點(diǎn)出發(fā)，當(dāng)?shù)诙蔚竭_(dá)結(jié)點(diǎn)時(shí)就輸出結(jié)點(diǎn)數(shù)據(jù)，按照先向左在向右的方向訪問。

圖3.13所示二叉樹中序訪問如下：

從根結(jié)點(diǎn)出發(fā)，則第一次到達(dá)結(jié)點(diǎn)A，不輸出A，繼續(xù)向左訪問，第一次訪問結(jié)點(diǎn)B，不輸出B；繼續(xù)到達(dá)D，H；

到達(dá)H，H左子樹為空，則返回到H，此時(shí)第二次訪問H，故輸出H；

H右子樹為空，則返回至D，此時(shí)第二次到達(dá)D，故輸出D；

由D返回至B，第二次到達(dá)B，故輸出B；

按照同樣規(guī)則繼續(xù)訪問，輸出J、E、A、F、C、G；

則3.13所示二叉樹的中序遍歷輸出為：

HDIBJEAFCG

3.8.4 后序遍歷

后序遍歷就是從二叉樹的根結(jié)點(diǎn)出發(fā)，當(dāng)?shù)谌蔚竭_(dá)結(jié)點(diǎn)時(shí)就輸出結(jié)點(diǎn)數(shù)據(jù)，按照先向左在向右的方向訪問。

圖3.13所示二叉樹后序訪問如下：

從根結(jié)點(diǎn)出發(fā)，則第一次到達(dá)結(jié)點(diǎn)A，不輸出A，繼續(xù)向左訪問，第一次訪問結(jié)點(diǎn)B，不輸出B；繼續(xù)到達(dá)D，H；

到達(dá)H，H左子樹為空，則返回到H，此時(shí)第二次訪問H，不輸出H；

H右子樹為空，則返回至H，此時(shí)第三次到達(dá)H，故輸出H；

由H返回至D，第二次到達(dá)D，不輸出D；

繼續(xù)訪問至I，I左右子樹均為空，故第三次訪問I時(shí)，輸出I；

返回至D，此時(shí)第三次到達(dá)D，故輸出D；

按照同樣規(guī)則繼續(xù)訪問，輸出J、E、B、F、G、C，A；

則圖3.13所示二叉樹的后序遍歷輸出為：

HIDJEBFGCA

雖然二叉樹的遍歷過程看似繁瑣，但是由于二叉樹是一種遞歸定義的結(jié)構(gòu)，故采用遞歸方式遍歷二叉樹的代碼十分簡(jiǎn)單。

遞歸實(shí)現(xiàn)代碼如下：

/*二叉樹的前序遍歷遞歸算法*/

void PreOrderTraverse(BiTree T)

{

    if(T==NULL)

    return;

    printf("%c", T->data);  /*顯示結(jié)點(diǎn)數(shù)據(jù)，可以更改為其他對(duì)結(jié)點(diǎn)操作*/

    PreOrderTraverse(T->lchild);    /*再先序遍歷左子樹*/

    PreOrderTraverse(T->rchild);    /*最后先序遍歷右子樹*/

}

/*二叉樹的中序遍歷遞歸算法*/

void InOrderTraverse(BiTree T)

{

    if(T==NULL)

    return;

    InOrderTraverse(T->lchild); /*中序遍歷左子樹*/

    printf("%c", T->data);  /*顯示結(jié)點(diǎn)數(shù)據(jù)，可以更改為其他對(duì)結(jié)點(diǎn)操作*/

    InOrderTraverse(T->rchild); /*最后中序遍歷右子樹*/

}

/*二叉樹的后序遍歷遞歸算法*/

void PostOrderTraverse(BiTree T)

{

    if(T==NULL)

    return;

    PostOrderTraverse(T->lchild);   /*先后序遍歷左子樹*/

    PostOrderTraverse(T->rchild);   /*再后續(xù)遍歷右子樹*/

    printf("%c", T->data);  /*顯示結(jié)點(diǎn)數(shù)據(jù)，可以更改為其他對(duì)結(jié)點(diǎn)操作*/

}

3.8.5 層次遍歷

層次遍歷就是按照樹的層次自上而下的遍歷二叉樹。針對(duì)圖3.13所示二叉樹的層次遍歷結(jié)果為：

ABCDEFGHIJ

3.8.6 遍歷?？伎键c(diǎn)

對(duì)于二叉樹的遍歷有一類典型題型。

1）已知前序遍歷序列和中序遍歷序列，確定一棵二叉樹。

例題：若一棵二叉樹的前序遍歷為ABCDEF，中序遍歷為CBAEDF，請(qǐng)畫出這棵二叉樹。

分析：前序遍歷第一個(gè)輸出結(jié)點(diǎn)為根結(jié)點(diǎn)，故A為根結(jié)點(diǎn)。早中序遍歷中根結(jié)點(diǎn)處于左右子樹結(jié)點(diǎn)中間，故結(jié)點(diǎn)A的左子樹中結(jié)點(diǎn)有CB，右子樹中結(jié)點(diǎn)有EDF。

如圖3.14所示：

圖3.14

按照同樣的分析方法，對(duì)A的左右子樹進(jìn)行劃分，最后得出二叉樹的形態(tài)如圖3.15所示：

圖3.15.png

2）已知后序遍歷序列和中序遍歷序列，確定一棵二叉樹。

后序遍歷中最后訪問的為根結(jié)點(diǎn)，因此可以按照上述同樣的方法，找到根結(jié)點(diǎn)后分成兩棵子樹，進(jìn)而繼續(xù)找到子樹的根結(jié)點(diǎn)，一步步確定二叉樹的形態(tài)。

注：已知前序遍歷序列和后序遍歷序列，不可以唯一確定一棵二叉樹。

4.結(jié)語

通過上述的介紹，已經(jīng)對(duì)于二叉樹有了初步的認(rèn)識(shí)。本篇文章介紹的基礎(chǔ)知識(shí)希望讀者能夠牢牢掌握，并且能夠在腦海中建立一棵二叉樹的模型，為后續(xù)學(xué)習(xí)打好基礎(chǔ)。