前言

樹是數據結構中的(de)重中之重，尤其以各類二叉樹爲學習(xí)的(de)難點。一直以來(lái)，對(duì)于樹的(de)掌握都是模棱兩可(kě)的(de)狀态，現在希望通(tōng)過寫一個(gè)關于二叉樹的(de)專題系列。在學習(xí)與總結的(de)同時(shí)更加深入的(de)了(le)解掌握二叉樹。本系列文章(zhāng)将著(zhe)重介紹一般二叉樹、完全二叉樹、滿二叉樹、線索二叉樹、霍夫曼樹、二叉排序樹、平衡二叉樹、紅黑(hēi)樹、B樹。希望各位讀者能夠關注專題，并給出相應意見，通(tōng)過系列的(de)學習(xí)做(zuò)到心中有“樹”。

1.重點概念

1.1 結點概念

結點是數據結構中的(de)基礎，是構成複雜(zá)數據結構的(de)基本組成單位。

1.2 樹結點聲明(míng)

本系列文章(zhāng)中提及的(de)結點專指樹的(de)結點。例如：結點A在圖中表示爲：

2樹

2.1 定義

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

1）有且僅有一個(gè)特定的(de)稱爲根（Root）的(de)結點；

2）當n>1時(shí)，其餘結點可(kě)分(fēn)爲m(m>0)個(gè)互不相交的(de)有限集T1、T2、......、Tn，其中每一個(gè)集合本身又是一棵樹，并且稱爲根的(de)子樹。

此外，樹的(de)定義還(hái)需要強調以下(xià)兩點：

1）n>0時(shí)根結點是唯一的(de)，不可(kě)能存在多(duō)個(gè)根結點，數據結構中的(de)樹隻能有一個(gè)根結點。

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

示例樹：

圖2.1爲一棵普通(tōng)的(de)樹：

圖2.1 普通(tōng)樹

由樹的(de)定義可(kě)以看出，樹的(de)定義使用(yòng)了(le)遞歸的(de)方式。遞歸在樹的(de)學習(xí)過程中起著(zhe)重要作用(yòng)，如果對(duì)于遞歸不是十分(fēn)了(le)解，建議(yì)先看看遞歸算(suàn)法

2.2 結點的(de)度

結點擁有的(de)子樹數目稱爲結點的(de)度。

圖2.2中标注了(le)圖2.1所示樹的(de)各個(gè)結點的(de)度。

圖2.2 度示意圖

2.3 結點關系

結點子樹的(de)根結點爲該結點的(de)孩子結點。相應該結點稱爲孩子結點的(de)雙親結點。

圖2.2中，A爲B的(de)雙親結點，B爲A的(de)孩子結點。

同一個(gè)雙親結點的(de)孩子結點之間互稱兄弟(dì)結點。

圖2.2中，結點B與結點C互爲兄弟(dì)結點。

2.4 結點層次

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

圖2.3表示了(le)圖2.1所示樹的(de)層次關系

圖2.3 層示意圖

2.5 樹的(de)深度

樹中結點的(de)最大(dà)層次數稱爲樹的(de)深度或高(gāo)度。圖2.1所示樹的(de)深度爲4。

3.二叉樹

3.1 定義

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

圖3.1展示了(le)一棵普通(tōng)二叉樹：

圖3.1 二叉樹

3.2 二叉樹特點

由二叉樹定義以及圖示分(fēn)析得(de)出二叉樹有以下(xià)特點：

1）每個(gè)結點最多(duō)有兩顆子樹，所以二叉樹中不存在度大(dà)于2的(de)結點。

2）左子樹和(hé)右子樹是有順序的(de)，次序不能任意颠倒。

3）即使樹中某結點隻有一棵子樹，也(yě)要區(qū)分(fēn)它是左子樹還(hái)是右子樹。

3.3 二叉樹性質

1）在二叉樹的(de)第i層上最多(duō)有2i-1 個(gè)節點 。（i>=1）

2）二叉樹中如果深度爲k,那麽最多(duō)有2k-1個(gè)節點。(k>=1）

3）n0=n2+1  n0表示度數爲0的(de)節點數，n2表示度數爲2的(de)節點數。

4）在完全二叉樹中，具有n個(gè)節點的(de)完全二叉樹的(de)深度爲[log2n]+1，其中[log2n]是向下(xià)取整。

5）若對(duì)含 n 個(gè)結點的(de)完全二叉樹從上到下(xià)且從左至右進行 1 至 n 的(de)編号，則對(duì)完全二叉樹中任意一個(gè)編号爲 i 的(de)結點有如下(xià)特性：

(1) 若 i=1，則該結點是二叉樹的(de)根，無雙親, 否則，編号爲 [i/2] 的(de)結點爲其雙親結點;

(2) 若 2i>n，則該結點無左孩子，  否則，編号爲 2i 的(de)結點爲其左孩子結點；

(3) 若 2i+1>n，則該結點無右孩子結點，  否則，編号爲2i+1 的(de)結點爲其右孩子結點。

3.4 斜樹

斜樹：所有的(de)結點都隻有左子樹的(de)二叉樹叫左斜樹。所有結點都是隻有右子樹的(de)二叉樹叫右斜樹。這(zhè)兩者統稱爲斜樹。

圖3.2 左斜樹

圖3.3 右斜樹

3.5 滿二叉樹

滿二叉樹：在一棵二叉樹中。如果所有分(fēn)支結點都存在左子樹和(hé)右子樹，并且所有葉子都在同一層上，這(zhè)樣的(de)二叉樹稱爲滿二叉樹。

滿二叉樹的(de)特點有：

1）葉子隻能出現在最下(xià)一層。出現在其它層就不可(kě)能達成平衡。

2）非葉子結點的(de)度一定是2。

3）在同樣深度的(de)二叉樹中，滿二叉樹的(de)結點個(gè)數最多(duō)，葉子數最多(duō)。

圖3.4 滿二叉樹

3.6 完全二叉樹

完全二叉樹：對(duì)一顆具有n個(gè)結點的(de)二叉樹按層編号，如果編号爲i(1<=i<=n)的(de)結點與同樣深度的(de)滿二叉樹中編号爲i的(de)結點在二叉樹中位置完全相同，則這(zhè)棵二叉樹稱爲完全二叉樹。

圖3.5展示一棵完全二叉樹

圖3.5 完全二叉樹

特點：

1）葉子結點隻能出現在最下(xià)層和(hé)次下(xià)層。

2）最下(xià)層的(de)葉子結點集中在樹的(de)左部。

3）倒數第二層若存在葉子結點，一定在右部連續位置。

4）如果結點度爲1，則該結點隻有左孩子，即沒有右子樹。

5）同樣結點數目的(de)二叉樹，完全二叉樹深度最小。

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

3.7 二叉樹的(de)存儲結構

3.7.1 順序存儲

二叉樹的(de)順序存儲結構就是使用(yòng)一維數組存儲二叉樹中的(de)結點，并且結點的(de)存儲位置，就是數組的(de)下(xià)标索引。

圖3.6

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

圖3.7 順序存儲

由圖3.7可(kě)以看出，當二叉樹爲完全二叉樹時(shí)，結點數剛好填滿數組。

那麽當二叉樹不爲完全二叉樹時(shí)，采用(yòng)順序存儲形式如何呢(ne)？例如：對(duì)于圖3.8描述的(de)二叉樹：

圖3.8.png

其中淺色結點表示結點不存在。那麽圖3.8所示的(de)二叉樹的(de)順序存儲結構如圖3.9所示：

圖3.9

其中，∧表示數組中此位置沒有存儲結點。此時(shí)可(kě)以發現，順序存儲結構中已經出現了(le)空間浪費的(de)情況。

那麽對(duì)于圖3.3所示的(de)右斜樹極端情況對(duì)應的(de)順序存儲結構如圖3.10所示：

圖3.10

由圖3.10可(kě)以看出，對(duì)于這(zhè)種右斜樹極端情況，采用(yòng)順序存儲的(de)方式是十分(fēn)浪費空間的(de)。因此，順序存儲一般适用(yòng)于完全二叉樹。

3.7.2 二叉鏈表

既然順序存儲不能滿足二叉樹的(de)存儲需求，那麽考慮采用(yòng)鏈式存儲。由二叉樹定義可(kě)知，二叉樹的(de)每個(gè)結點最多(duō)有兩個(gè)孩子。因此，可(kě)以将結點數據結構定義爲一個(gè)數據和(hé)兩個(gè)指

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

圖3.11

定義結點代碼：

typedef struct BiTNode{

    TElemType data;//數據

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

} BiTNode, *BiTree;

則圖3.6所示的(de)二叉樹可(kě)以采用(yòng)圖3.12表示。

圖3.12

圖3.12中采用(yòng)一種鏈表結構存儲二叉樹，這(zhè)種鏈表稱爲二叉鏈表。

3.8 二叉樹遍曆

二叉樹的(de)遍曆一個(gè)重點考查的(de)知識點。

3.8.1 定義

二叉樹的(de)遍曆是指從二叉樹的(de)根結點出發，按照(zhào)某種次序依次訪問二叉樹中的(de)所有結點，使得(de)每個(gè)結點被訪問一次，且僅被訪問一次。

二叉樹的(de)訪問次序可(kě)以分(fēn)爲四種：

前序遍曆

中序遍曆

後序遍曆

層序遍曆

3.8.2 前序遍曆

前序遍曆通(tōng)俗的(de)說就是從二叉樹的(de)根結點出發，當第一次到達結點時(shí)就輸出結點數據，按照(zhào)先向左在向右的(de)方向訪問。

3.13

圖3.13所示二叉樹訪問如下(xià)：

從根結點出發，則第一次到達結點A，故輸出A;

繼續向左訪問，第一次訪問結點B，故輸出B；

按照(zhào)同樣規則，輸出D，輸出H；

當到達葉子結點H，返回到D，此時(shí)已經是第二次到達D，故不在輸出D，進而向D右子樹訪問，D右子樹不爲空，則訪問至I，第一次到達I，則輸出I；

I爲葉子結點，則返回到D，D左右子樹已經訪問完畢，則返回到B，進而到B右子樹，第一次到達E，故輸出E；

向E左子樹，故輸出J；

按照(zhào)同樣的(de)訪問規則，繼續輸出C、F、G；

則3.13所示二叉樹的(de)前序遍曆輸出爲：

ABDHIEJCFG

3.8.3 中序遍曆

中序遍曆就是從二叉樹的(de)根結點出發，當第二次到達結點時(shí)就輸出結點數據，按照(zhào)先向左在向右的(de)方向訪問。

圖3.13所示二叉樹中序訪問如下(xià)：

從根結點出發，則第一次到達結點A，不輸出A，繼續向左訪問，第一次訪問結點B，不輸出B；繼續到達D，H；

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

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

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

按照(zhào)同樣規則繼續訪問，輸出J、E、A、F、C、G；

則3.13所示二叉樹的(de)中序遍曆輸出爲：

HDIBJEAFCG

3.8.4 後序遍曆

後序遍曆就是從二叉樹的(de)根結點出發，當第三次到達結點時(shí)就輸出結點數據，按照(zhào)先向左在向右的(de)方向訪問。

圖3.13所示二叉樹後序訪問如下(xià)：

從根結點出發，則第一次到達結點A，不輸出A，繼續向左訪問，第一次訪問結點B，不輸出B；繼續到達D，H；

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

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

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

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

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

按照(zhào)同樣規則繼續訪問，輸出J、E、B、F、G、C，A；

則圖3.13所示二叉樹的(de)後序遍曆輸出爲：

HIDJEBFGCA

雖然二叉樹的(de)遍曆過程看似繁瑣，但是由于二叉樹是一種遞歸定義的(de)結構，故采用(yòng)遞歸方式遍曆二叉樹的(de)代碼十分(fēn)簡單。

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

/*二叉樹的(de)前序遍曆遞歸算(suàn)法*/

void PreOrderTraverse(BiTree T)

{

    if(T==NULL)

    return;

    printf("%c", T->data);  /*顯示結點數據，可(kě)以更改爲其他(tā)對(duì)結點操作*/

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

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

}

/*二叉樹的(de)中序遍曆遞歸算(suàn)法*/

void InOrderTraverse(BiTree T)

{

    if(T==NULL)

    return;

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

    printf("%c", T->data);  /*顯示結點數據，可(kě)以更改爲其他(tā)對(duì)結點操作*/

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

}

/*二叉樹的(de)後序遍曆遞歸算(suàn)法*/

void PostOrderTraverse(BiTree T)

{

    if(T==NULL)

    return;

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

    PostOrderTraverse(T->rchild);   /*再後續遍曆右子樹*/

    printf("%c", T->data);  /*顯示結點數據，可(kě)以更改爲其他(tā)對(duì)結點操作*/

}

3.8.5 層次遍曆

層次遍曆就是按照(zhào)樹的(de)層次自上而下(xià)的(de)遍曆二叉樹。針對(duì)圖3.13所示二叉樹的(de)層次遍曆結果爲：

ABCDEFGHIJ

3.8.6 遍曆常考考點

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

1）已知前序遍曆序列和(hé)中序遍曆序列，确定一棵二叉樹。

例題：若一棵二叉樹的(de)前序遍曆爲ABCDEF，中序遍曆爲CBAEDF，請畫(huà)出這(zhè)棵二叉樹。

分(fēn)析：前序遍曆第一個(gè)輸出結點爲根結點，故A爲根結點。早中序遍曆中根結點處于左右子樹結點中間，故結點A的(de)左子樹中結點有CB，右子樹中結點有EDF。

如圖3.14所示：

圖3.14

按照(zhào)同樣的(de)分(fēn)析方法，對(duì)A的(de)左右子樹進行劃分(fēn)，最後得(de)出二叉樹的(de)形态如圖3.15所示：

圖3.15.png

2）已知後序遍曆序列和(hé)中序遍曆序列，确定一棵二叉樹。

後序遍曆中最後訪問的(de)爲根結點，因此可(kě)以按照(zhào)上述同樣的(de)方法，找到根結點後分(fēn)成兩棵子樹，進而繼續找到子樹的(de)根結點，一步步确定二叉樹的(de)形态。

注：已知前序遍曆序列和(hé)後序遍曆序列，不可(kě)以唯一确定一棵二叉樹。

4.結語

通(tōng)過上述的(de)介紹，已經對(duì)于二叉樹有了(le)初步的(de)認識。本篇文章(zhāng)介紹的(de)基礎知識希望讀者能夠牢牢掌握，并且能夠在腦(nǎo)海中建立一棵二叉樹的(de)模型，爲後續學習(xí)打好基礎。