友情鏈接：數(shù)據(jù)結(jié)構(gòu)專欄

目錄

• 樹
• • 【知識框架】
  • 一、樹的基本概念
  • • 1、樹的定義
    • 2、基本術(shù)語
    • 3、樹的性質(zhì)
  • 二、樹的存儲結(jié)構(gòu)
  • • 1、雙親表示法
    • 2、孩子表示法
    • 3、孩子兄弟表示法
• 二叉樹
• • 一、二叉樹的概念
  • • 1、二叉樹的定義
    • 2、幾個特殊的二叉樹
    • • （1）斜樹
      • （2）滿二叉樹
      • （3）完全二叉樹
      • （4）二叉排序樹
      • （5）平衡二叉樹
    • 3、二叉樹的性質(zhì)
    • 4、二叉樹的存儲結(jié)構(gòu)
    • • （1）順序存儲結(jié)構(gòu)
      • （2）鏈?zhǔn)酱鎯Y(jié)構(gòu)
  • 二、遍歷二叉樹
  • • 1、先序遍歷
    • 2、中序遍歷
    • 3、后序遍歷
    • 4、遞歸算法和非遞歸算法的轉(zhuǎn)換
    • • （1）中序遍歷的非遞歸算法
      • （2）先序遍歷的非遞歸算法
      • （3）后序遍歷的非遞歸算法
    • 5、層次遍歷
    • 6、由遍歷序列構(gòu)造二叉樹
  • 三、線索二叉樹
  • • 1、線索二叉樹原理
    • 2、線索二叉樹的結(jié)構(gòu)實(shí)現(xiàn)
    • 3、二叉樹的線索化
    • • （1）中序線索二叉樹
      • （2）先序和后序線索二叉樹
  • 四、樹、森林與二叉樹的轉(zhuǎn)化
  • • 1、樹轉(zhuǎn)換為二叉樹
    • 2、森林轉(zhuǎn)化為二叉樹
  • 五、樹和森林的遍歷
  • • 1、樹的遍歷
    • 2、森林的遍歷
• 樹與二叉樹的應(yīng)用
• • 一、二叉排序樹
  • • 1、定義
    • 2、二叉排序樹的常見操作
    • • （1）查找操作
      • （2）插入操作
      • （3）刪除操作
    • 3、小結(jié)（引申出平衡二叉樹）
  • 二、平衡二叉樹
  • • 1、定義
    • 2、平衡二叉樹的查找
    • 3、平衡二叉樹的插入
  • 三、哈夫曼樹和哈夫曼編碼
  • • 1、哈夫曼樹的定義和原理
    • 2、哈夫曼樹的構(gòu)造
    • 3、哈夫曼編碼
• 附錄
• • 上文鏈接
  • 下文鏈接
  • 專欄
  • 參考資料

樹

【知識框架】

一、樹的基本概念

1、樹的定義

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

有且僅有一個特定的稱為根的結(jié)點(diǎn)。

當(dāng)n>1時，其余節(jié)點(diǎn)可分為m（m>0）個互不相交的有限集T1,T2,…,Tm，其中每個集合本身又是一棵樹，并且稱為根的子樹。

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

樹的根結(jié)點(diǎn)沒有前驅(qū)，除根結(jié)點(diǎn)外的所有結(jié)點(diǎn)有且只有一個前驅(qū)。

樹中所有結(jié)點(diǎn)可以有零個或多個后繼。

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

2、基本術(shù)語

下面結(jié)合圖示來說明一下樹的一些基本術(shù)語和概念。

考慮結(jié)點(diǎn)K。根A到結(jié)點(diǎn)K的唯一路徑上的任意結(jié)點(diǎn),稱為結(jié)點(diǎn)K的祖先。如結(jié)點(diǎn)B是結(jié)點(diǎn)K的祖先,而結(jié)點(diǎn)K是結(jié)點(diǎn)B的子孫。路徑上最接近結(jié)點(diǎn)K的結(jié)點(diǎn)E稱為K的雙親,而K為結(jié)點(diǎn)E的孩子。根A是樹中唯一沒有雙親的結(jié)點(diǎn)。有相同雙親的結(jié)點(diǎn)稱為兄弟,如結(jié)點(diǎn)K和結(jié)點(diǎn)L有相同的雙親E,即K和L為兄弟。

樹中一個結(jié)點(diǎn)的孩子個數(shù)稱為該結(jié)點(diǎn)的度,樹中結(jié)點(diǎn)的最大度數(shù)稱為樹的度。如結(jié)點(diǎn)B的度為2,結(jié)點(diǎn)D的度為3,樹的度為3。

度大于0的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)(又稱非終端結(jié)點(diǎn));度為0(沒有子女結(jié)點(diǎn))的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)(又稱終端結(jié)點(diǎn))。在分支結(jié)點(diǎn)中,每個結(jié)點(diǎn)的分支數(shù)就是該結(jié)點(diǎn)的度。

結(jié)點(diǎn)的深度、高度和層次。
結(jié)點(diǎn)的層次從樹根開始定義,根結(jié)點(diǎn)為第1層,它的子結(jié)點(diǎn)為第2層,以此類推。雙親在同一層的結(jié)點(diǎn)互為堂兄弟,圖中結(jié)點(diǎn)G與E,F,H,I,J互為堂兄弟。
結(jié)點(diǎn)的深度是從根結(jié)點(diǎn)開始自頂向下逐層累加的。
結(jié)點(diǎn)的高度是從葉結(jié)點(diǎn)開始自底向上逐層累加的。
樹的高度(或深度)是樹中結(jié)點(diǎn)的最大層數(shù)。圖中樹的高度為4。

有序樹和無序樹。樹中結(jié)點(diǎn)的各子樹從左到右是有次序的,不能互換,稱該樹為有序樹,否則稱為無序樹。假設(shè)圖為有序樹,若將子結(jié)點(diǎn)位置互換,則變成一棵不同的樹。

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

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

注意:上述概念無須刻意記憶， 根據(jù)實(shí)例理解即可。

3、樹的性質(zhì)

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

樹中的結(jié)點(diǎn)數(shù)等于所有結(jié)點(diǎn)的度數(shù)加1.

度為$m$的樹中第$i$層上至多有$m^{i?1}$個結(jié)點(diǎn)（$i>=1$）

高度為$h$的$m$叉樹至多有$(m^h?1)/(m?1)$個結(jié)點(diǎn)。

具有$n$個結(jié)點(diǎn)的$m$叉樹的最小高度為$[lo{g}_m(n(m?1)+1)]$。

二、樹的存儲結(jié)構(gòu)

在介紹以下三種存儲結(jié)構(gòu)的過程中，我們都以下面這個樹為例子。

1、雙親表示法

我們假設(shè)以一組連續(xù)空間存儲樹的結(jié)點(diǎn)，同時在每個結(jié)點(diǎn)中，附設(shè)一個指示器指示其雙親結(jié)點(diǎn)到鏈表中的位置。也就是說，每個結(jié)點(diǎn)除了知道自已是誰以外，還知道它的雙親在哪里。

其中data是數(shù)據(jù)域，存儲結(jié)點(diǎn)的數(shù)據(jù)信息。而parent是指針域，存儲該結(jié)點(diǎn)的雙親在數(shù)組中的下標(biāo)。
以下是我們的雙親表示法的結(jié)點(diǎn)結(jié)構(gòu)定義代碼。

/*樹的雙親表示法結(jié)點(diǎn)結(jié)構(gòu)定義*/ #define MAX_TREE_SIZE 100 typedef int TElemType; //樹結(jié)點(diǎn)的數(shù)據(jù)類型，目前暫定為整型 /*結(jié)點(diǎn)結(jié)構(gòu)*/ typedef struct PTNode{TElemType data; //結(jié)點(diǎn)數(shù)據(jù)int parent; //雙親位置 }PTNode; /*樹結(jié)構(gòu)*/ typedef struct{PTNode nodes[MAX_TREE_SIZE]; //結(jié)點(diǎn)數(shù)組int r, n; //根的位置和結(jié)點(diǎn)數(shù) }PTree;

這樣的存儲結(jié)構(gòu)，我們可以根據(jù)結(jié)點(diǎn)的parent 指針很容易找到它的雙親結(jié)點(diǎn)，所用的時間復(fù)雜度為0(1)，直到parent為-1時，表示找到了樹結(jié)點(diǎn)的根。可如果我們要知道結(jié)點(diǎn)的孩子是什么，對不起，請遍歷整個結(jié)構(gòu)才行。

2、孩子表示法

具體辦法是，把每個結(jié)點(diǎn)的孩子結(jié)點(diǎn)排列起來，以單鏈表作存儲結(jié)構(gòu)，則n個結(jié)點(diǎn)有n個孩子鏈表，如果是葉子結(jié)點(diǎn)則此單鏈表為空。然后n個頭指針又組成-一個線性表，采用順序存儲結(jié)構(gòu)，存放進(jìn)一個一維數(shù)組中，如圖所示。

為此，設(shè)計兩種結(jié)點(diǎn)結(jié)構(gòu)，一個是孩子鏈表的孩子結(jié)點(diǎn)。

其中child是數(shù)據(jù)域，用來存儲某個結(jié)點(diǎn)在表頭數(shù)組中的下標(biāo)。next 是指針域，用來存儲指向某結(jié)點(diǎn)的下一個孩子結(jié)點(diǎn)的指針。

另一個是表頭數(shù)組的表頭結(jié)點(diǎn)。

其中data是數(shù)據(jù)域，存儲某結(jié)點(diǎn)的數(shù)據(jù)信息。firstchild 是頭指針域，存儲該結(jié)點(diǎn)的孩子鏈表的頭指針。

以下是我們的孩子表示法的結(jié)構(gòu)定義代碼。

/*樹的孩子表示法結(jié)構(gòu)定義*/ #define MAX_TREE_SIZE 100 /*孩子結(jié)點(diǎn)*/ typedef struct CTNode{int child;struct CTNode *next; }*ChildPtr; /*表頭結(jié)點(diǎn)*/ typedef struct{TElemType data;ChildPtr firstchild; }CTBox; /*樹結(jié)構(gòu)*/ typedef struct{CTBox nodes[MAX_TREE_SIZE]; //結(jié)點(diǎn)數(shù)組int r, n; //根的位置和結(jié)點(diǎn)數(shù) }

這樣的結(jié)構(gòu)對于我們要查找某個結(jié)點(diǎn)的某個孩子，或者找某個結(jié)點(diǎn)的兄弟，只需要查找這個結(jié)點(diǎn)的孩子單鏈表即可。對于遍歷整棵樹也是很方便的，對頭結(jié)點(diǎn)的數(shù)組循環(huán)即可。
但是，這也存在著問題，我如何知道某個結(jié)點(diǎn)的雙親是誰呢?比較麻煩，需要整棵樹遍歷才行，難道就不可以把雙親表示法和孩子表示法綜合一下嗎? 當(dāng)然是可以，這個讀者可自己嘗試結(jié)合一下，在次不做贅述。

3、孩子兄弟表示法

剛才我們分別從雙親的角度和從孩子的角度研究樹的存儲結(jié)構(gòu)，如果我們從樹結(jié)點(diǎn)的兄弟的角度又會如何呢?當(dāng)然，對于樹這樣的層級結(jié)構(gòu)來說，只研究結(jié)點(diǎn)的兄弟是不行的，我們觀察后發(fā)現(xiàn)，任意一棵樹， 它的結(jié)點(diǎn)的第一個孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。 因此，我們設(shè)置兩個指針，分別指向該結(jié)點(diǎn)的第一個孩子和此結(jié)點(diǎn)的右兄弟。
結(jié)點(diǎn)的結(jié)構(gòu)如下：

其中data是數(shù)據(jù)域，firstchild 為指針域，存儲該結(jié)點(diǎn)的第一個孩子結(jié)點(diǎn)的存儲地址，rightsib 是指針域，存儲該結(jié)點(diǎn)的右兄弟結(jié)點(diǎn)的存儲地址。
這種表示法，給查找某個結(jié)點(diǎn)的某個孩子帶來了方便。
結(jié)構(gòu)定義代碼如下。

/*樹的孩子兄弟表示法結(jié)構(gòu)定義*/ typedef struct CSNode{TElemtype data;struct CSNode *firstchild, *rightsib; } CSNode, *CSTree;

于是通過這種結(jié)構(gòu)，我們就把原來的樹變成了這個樣子：

這不就是個二叉樹么？
沒錯，其實(shí)這個表示法的最大好處就是它把一棵復(fù)雜的樹變成了一棵二叉樹。
接下來，我們詳細(xì)介紹二叉樹。

二叉樹

一、二叉樹的概念

1、二叉樹的定義

二叉樹是另一種樹形結(jié)構(gòu)，其特點(diǎn)是每個結(jié)點(diǎn)至多只有兩棵子樹( 即二叉樹中不存在度大于2的結(jié)點(diǎn))，并且二叉樹的子樹有左右之分，其次序不能任意顛倒。
與樹相似，二叉樹也以遞歸的形式定義。二叉樹是n (n≥0) 個結(jié)點(diǎn)的有限集合:

或者為空二叉樹，即n=0。

或者由一個根結(jié)點(diǎn)和兩個互不相交的被稱為根的左子樹和右子樹組成。左子樹和右子樹又分別是一棵二叉樹。

二叉樹是有序樹，若將其左、右子樹顛倒，則成為另一棵不同的二叉樹。即使樹中結(jié)點(diǎn)只有一棵子樹，也要區(qū)分它是左子樹還是右子樹。二叉樹的5種基本形態(tài)如圖所示。

2、幾個特殊的二叉樹

（1）斜樹

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

（2）滿二叉樹

一棵高度為$h$，且含有$2^h?1$個結(jié)點(diǎn)的二叉樹稱為滿二叉樹，即樹中的每層都含有最多的結(jié)點(diǎn)。滿二叉樹的葉子結(jié)點(diǎn)都集中在二叉樹的最下一層，并且除葉子結(jié)點(diǎn)之外的每個結(jié)點(diǎn)度數(shù)均為$2$。可以對滿二叉樹按層序編號:約定編號從根結(jié)點(diǎn)(根結(jié)點(diǎn)編號為$1$)起，自上而下，自左向右。這樣，每個結(jié)點(diǎn)對應(yīng)一個編號,對于編號為i的結(jié)點(diǎn)，若有雙親，則其雙親為$i/2$,若有左孩子，則左孩子為$2i$;若有右孩子，則右孩子為$2i+1$。

（3）完全二叉樹

高度為$h$、有$n$個結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每個結(jié)點(diǎn)都與高度為$h$的滿二叉樹中編號為1~n的結(jié)點(diǎn)一一對應(yīng)時，稱為完全二叉樹，如圖所示。其特點(diǎn)如下:

若$i\le n/2$, 則結(jié)點(diǎn)$i$為分支結(jié)點(diǎn)，否則為葉子結(jié)點(diǎn)。

葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)。對于最大層次中的葉子結(jié)點(diǎn)，都依次排列在該層最左邊的位置上。

若有度為$1$的結(jié)點(diǎn)，則只可能有一個，且該結(jié)點(diǎn)只有左孩子而無右孩子(重要特征)。

按層序編號后，一旦出現(xiàn)某結(jié)點(diǎn)(編號為$i$)為葉子結(jié)點(diǎn)或只有左孩子，則編號大于$i$的結(jié)點(diǎn)均為葉子結(jié)點(diǎn)。

若$n$為奇數(shù)，則每個分支結(jié)點(diǎn)都有左孩子和右孩子;若$n$為偶數(shù)，則編號最大的分支結(jié)點(diǎn)(編號為$n/2$)只有左孩子，沒有右孩子，其余分支結(jié)點(diǎn)左、右孩子都有。

（4）二叉排序樹

左子樹上所有結(jié)點(diǎn)的關(guān)鍵字均小于根結(jié)點(diǎn)的關(guān)鍵字;右子樹上的所有結(jié)點(diǎn)的關(guān)鍵字均大于根結(jié)點(diǎn)的關(guān)鍵字;左子樹和右子樹又各是一棵二叉排序樹。

（5）平衡二叉樹

樹上任一結(jié)點(diǎn)的左子樹和右子樹的深度之差不超過1。

3、二叉樹的性質(zhì)

任意一棵樹，若結(jié)點(diǎn)數(shù)量為$n$,則邊的數(shù)量為$n?1$。

非空二叉樹上的葉子結(jié)點(diǎn)數(shù)等于度為$2$的結(jié)點(diǎn)數(shù)加$1$，即$n_o=n_2+1$。

非空二叉樹上第$k$層上至多有$2^{k?1}$個結(jié)點(diǎn)$(k\ge 1)$。

高度為$h$的二叉樹至多有$2^h?1$個結(jié)點(diǎn)$(h\ge 1)$。

對完全二叉樹按從上到下、從左到右的順序依次編號$1,2..?,n$,則有以下關(guān)系:

• $i>1$時，結(jié)點(diǎn)$i$的雙親的編號為$i/2$,即當(dāng)$i$為偶數(shù)時， 它是雙親的左孩子;當(dāng)i為奇數(shù)時，它是雙親的右孩子。
• 當(dāng)$2i\le n$時，結(jié)點(diǎn)$i$的左孩子編號為$2i$, 否則無左孩子。
• 當(dāng)$2i+1\le n$時，結(jié)點(diǎn)$i$的右孩子編號為$2i+1$，否則無右孩子。
• 結(jié)點(diǎn)$i$所在層次(深度)為$\{lo{g}_{2}i\}+1$。

具有$n$個$(n>0)$結(jié)點(diǎn)的完全二叉樹的高度為$\{lo{g}_{2}n\}+1$。

4、二叉樹的存儲結(jié)構(gòu)

（1）順序存儲結(jié)構(gòu)

二叉樹的順序存儲是指用一組地址連續(xù)的存儲單元依次自上而下、自左至右存儲完全二叉樹上的結(jié)點(diǎn)元素，即將完全二叉樹上編號為$i$的結(jié)點(diǎn)元素存儲在一維數(shù)組下標(biāo)為$i?1$的分量中。
依據(jù)二叉樹的性質(zhì)，完全二叉樹和滿二叉樹采用順序存儲比較合適，樹中結(jié)點(diǎn)的序號可以唯一地反映結(jié)點(diǎn)之間的邏輯關(guān)系，這樣既能最大可能地節(jié)省存儲空間，又能利用數(shù)組元素的下標(biāo)值確定結(jié)點(diǎn)在二叉樹中的位置，以及結(jié)點(diǎn)之間的關(guān)系。
但對于一般的二叉樹，為了讓數(shù)組下標(biāo)能反映二叉樹中結(jié)點(diǎn)之間的邏輯關(guān)系，只能添加一些并不存在的空結(jié)點(diǎn)，讓其每個結(jié)點(diǎn)與完全二叉樹上的結(jié)點(diǎn)相對照，再存儲到一維數(shù)組的相應(yīng)分量中。然而，在最壞情況下，一個高度為$h$且只有$h$個結(jié)點(diǎn)的單支樹卻需要占據(jù)近$2h?1$個存儲單元。二叉樹的順序存儲結(jié)構(gòu)如圖所示，其中0表示并不存在的空結(jié)點(diǎn)。

（2）鏈?zhǔn)酱鎯Y(jié)構(gòu)

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

其中data是數(shù)據(jù)域，lchild 和rchild都是指針域，分別存放指向左孩子和右孩子的指針。
以下是我們的二叉鏈表的結(jié)點(diǎn)結(jié)構(gòu)定義代碼。

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

容易驗(yàn)證，在含有$n$個結(jié)點(diǎn)的二叉鏈表中，含有$n+1$個空鏈域。

---

二、遍歷二叉樹

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

1、先序遍歷

先序遍歷(PreOrder) 的操作過程如下：
若二叉樹為空，則什么也不做，否則，
1)訪問根結(jié)點(diǎn);
2)先序遍歷左子樹;
3)先序遍歷右子樹。

對應(yīng)的遞歸算法如下:

void PreOrder(BiTree T){if(T != NULL){visit(T); //訪問根節(jié)點(diǎn)PreOrder(T->lchild); //遞歸遍歷左子樹PreOrder(T->rchild); //遞歸遍歷右子樹} }

2、中序遍歷

中序遍歷( InOrder)的操作過程如下：
若二叉樹為空，則什么也不做，否則，
1)中序遍歷左子樹;
2)訪問根結(jié)點(diǎn);
3)中序遍歷右子樹。

對應(yīng)的遞歸算法如下:

void InOrder(BiTree T){if(T != NULL){InOrder(T->lchild); //遞歸遍歷左子樹visit(T); //訪問根結(jié)點(diǎn)InOrder(T->rchild); //遞歸遍歷右子樹} }

3、后序遍歷

后序遍歷(PostOrder) 的操作過程如下：
若二叉樹為空，則什么也不做，否則，
1)后序遍歷左子樹;
2)后序遍歷右子樹;
3)訪問根結(jié)點(diǎn)。

對應(yīng)的遞歸算法如下:

void PostOrder(BiTree T){if(T != NULL){PostOrder(T->lchild); //遞歸遍歷左子樹PostOrder(T->rchild); //遞歸遍歷右子樹visit(T); //訪問根結(jié)點(diǎn)} }

三種遍歷算法中,遞歸遍歷左、右子樹的順序都是固定的，只是訪問根結(jié)點(diǎn)的順序不同。不管采用哪種遍歷算法，每個結(jié)點(diǎn)都訪問一次且僅訪問一次，故時間復(fù)雜度都是O(n)。在遞歸遍歷中，遞歸工作棧的棧深恰好為樹的深度，所以在最壞情況下，二叉樹是有n個結(jié)點(diǎn)且深度為n的單支樹，遍歷算法的空間復(fù)雜度為O(n)。

4、遞歸算法和非遞歸算法的轉(zhuǎn)換

我們以下圖的樹為例子。

（1）中序遍歷的非遞歸算法

借助棧，我們來分析中序遍歷的訪問過程:

沿著根的左孩子，依次入棧，直到左孩子為空，說明已找到可以輸出的結(jié)點(diǎn)，此時棧內(nèi)元素依次為ABD。

棧頂元素出棧并訪問:若其右孩子為空，繼續(xù)執(zhí)行步驟2;若其右孩子不空,將右子樹轉(zhuǎn)執(zhí)行步驟1。

棧頂D出棧并訪問，它是中序序列的第一個結(jié)點(diǎn); D右孩子為空，棧頂B出棧并訪問; B右孩子不空，將其右孩子E入棧，E左孩子為空，棧頂E出棧并訪問; E右孩子為空，棧頂A出棧并訪問; A右孩子不空，將其右孩子C入棧，C左孩子為空，棧頂C出棧并訪問。由此得到中序序列DBEAC。
根據(jù)分析可以寫出中序遍歷的非遞歸算法如下:

void InOrder2(BiTree T){InitStack(S); //初始化棧SBiTree p = T; //p是遍歷指針while(p || !IsEmpty(S)){ //棧不空或p不空時循環(huán)if(p){Push(S, p); //當(dāng)前節(jié)點(diǎn)入棧p = p->lchild; //左孩子不空，一直向左走}else{Pop(S, p); //棧頂元素出棧visit(p); //訪問出棧結(jié)點(diǎn)p = p->rchild; //向右子樹走，p賦值為當(dāng)前結(jié)點(diǎn)的右孩子}} }

（2）先序遍歷的非遞歸算法

先序遍歷和中序遍歷的基本思想是類似的，只需把訪問結(jié)點(diǎn)操作放在入棧操作的前面。先序遍歷的非遞歸算法如下:

void PreOrder2(BiTree T){InitStack(S); //初始化棧SBiTree p = T; //p是遍歷指針while(p || !IsEmpty(S)){ //棧不空或p不空時循環(huán)if(p){visit(p); //訪問出棧結(jié)點(diǎn)Push(S, p); //當(dāng)前節(jié)點(diǎn)入棧p = p->lchild; //左孩子不空，一直向左走}else{Pop(S, p); //棧頂元素出棧p = p->rchild; //向右子樹走，p賦值為當(dāng)前結(jié)點(diǎn)的右孩子}} }

（3）后序遍歷的非遞歸算法

后序遍歷的非遞歸實(shí)現(xiàn)是三種遍歷方法中最難的。因?yàn)樵诤笮虮闅v中，要保證左孩了和右孩子都已被訪問并且左孩子在右孩子前訪問才能訪問根結(jié)點(diǎn)，這就為流程的控制帶來了難題。

算法思想:后序非遞歸遍歷二叉樹是先訪問左子樹，再訪問右子樹，最后訪問根結(jié)點(diǎn)。

沿著根的左孩子，依次入棧，直到左孩子為空。此時棧內(nèi)元素依次為ABD。

讀棧頂元素:若其右孩子不空且未被訪問過，將右子樹轉(zhuǎn)執(zhí)行①;否則，棧頂元素出棧并訪問。

棧頂D的右孩子為空，出棧并訪問，它是后序序列的第一個結(jié)點(diǎn);棧頂B的右孩子不空且未被訪問過，E入棧，棧頂E的左右孩子均為空，出棧并訪問;棧頂B的右孩子不空但已被訪問，B出棧并訪問;棧項(xiàng)A的右孩子不空且未被訪問過，C入棧,棧項(xiàng)C的左右孩子均為空，出棧并訪問;棧頂A的右孩子不空但已被訪問，A出棧并訪問。由此得到后序序列DEBCA。
在上述思想的第②步中，必須分清返回時是從左子樹返回的還是從右子樹返回的，因此設(shè)定一個輔助指針r,指向最近訪問過的結(jié)點(diǎn)。也可在結(jié)點(diǎn)中增加一個標(biāo)志域，記錄是否已被訪問。

后序遍歷的非遞歸算法如下:

void PostOrder2(BiTree T){InitStack(S);p = T;r = NULL;while(p || !IsEmpty(S)){if(p){ //走到最左邊push(S, p);p = p->lchild;}else{ //向右GetTop(S, p); //讀棧頂元素（非出棧）//若右子樹存在，且未被訪問過if(p->rchild && p->rchild != r){p = p->rchild; //轉(zhuǎn)向右push(S, p); //壓入棧p = p->lchild; //再走到最左}else{ //否則，彈出結(jié)點(diǎn)并訪問pop(S, p); //將結(jié)點(diǎn)彈出visit(p->data); //訪問該結(jié)點(diǎn)r = p; //記錄最近訪問過的結(jié)點(diǎn)p = NULL;}}} }

5、層次遍歷

下圖為二叉樹的層次遍歷，即按照箭頭所指方向，按照1,2,3, 4的層次順序，對二叉樹中的各個結(jié)點(diǎn)進(jìn)行訪問。

要進(jìn)行層次遍歷，需要借助一個隊列。先將二叉樹根結(jié)點(diǎn)入隊，然后出隊，訪問出隊結(jié)點(diǎn)，若它有左子樹，則將左子樹根結(jié)點(diǎn)入隊;若它有右子樹，則將右子樹根結(jié)點(diǎn)入隊。然后出隊，訪問出隊結(jié)…如此反復(fù)，直至隊列為空。
二叉樹的層次遍歷算法如下:

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

6、由遍歷序列構(gòu)造二叉樹

由二叉樹的先序序列和中序序列可以唯一地確定一棵二叉樹。
在先序遍歷序列中,第一個結(jié)點(diǎn)一定是二叉樹的根結(jié)點(diǎn);而在中序遍歷中,根結(jié)點(diǎn)必然將中序序列分割成兩個子序列,前一個子序列是根結(jié)點(diǎn)的左子樹的中序序列,后一個子序列是根結(jié)點(diǎn)的右子樹的中序序列。根據(jù)這兩個子序列,在先序序列中找到對應(yīng)的左子序列和右子序列。在先序序列中,左子序列的第一個結(jié)點(diǎn)是左子樹的根結(jié)點(diǎn),右子序列的第一個結(jié)點(diǎn)是右子樹的根結(jié)點(diǎn)。
如此遞歸地進(jìn)行下去,便能唯一地確定這棵二叉樹
同理,由二叉樹的后序序列和中序序列也可以唯一地確定一棵二叉樹。
因?yàn)楹笮蛐蛄械淖詈笠粋€結(jié)點(diǎn)就如同先序序列的第一個結(jié)點(diǎn),可以將中序序列分割成兩個子序列,然后采用類似的方法遞歸地進(jìn)行劃分,進(jìn)而得到一棵二叉樹。
由二叉樹的層序序列和中序序列也可以唯一地確定一棵二叉樹。
要注意的是,若只知道二叉樹的先序序列和后序序列,則無法唯一確定一棵二叉樹。
例如,求先序序列( ABCDEFGH)和中序序列( BCAEDGHFI）所確定的二叉樹
首先,由先序序列可知A為二叉樹的根結(jié)點(diǎn)。中序序列中A之前的BC為左子樹的中序序列,EDGHFI為右子樹的中序序列。然后由先序序列可知B是左子樹的根結(jié)點(diǎn),D是右子樹的根結(jié)點(diǎn)。以此類推,就能將剩下的結(jié)點(diǎn)繼續(xù)分解下去,最后得到的二叉樹如圖?所示。

三、線索二叉樹

1、線索二叉樹原理

遍歷二叉樹是以一定的規(guī)則將二叉樹中的結(jié)點(diǎn)排列成一個線性序列，從而得到幾種遍歷序列，使得該序列中的每個結(jié)點(diǎn)(第一個和最后一個結(jié)點(diǎn)除外)都有一個直接前驅(qū)和直接后繼。
傳統(tǒng)的二叉鏈表存儲僅能體現(xiàn)一種父子關(guān)系，不能直接得到結(jié)點(diǎn)在遍歷中的前驅(qū)或后繼。

首先我們要來看看這空指針有多少個呢?對于一個有n個結(jié)點(diǎn)的二叉鏈表，每個結(jié)點(diǎn)有指向左右孩子的兩個指針域，所以一共是2n個指針域。而n個結(jié)點(diǎn)的二叉樹一共有n-1 條分支線數(shù)，也就是說，其實(shí)是存在2n- (n-1) =n+1個空指針域。

由此設(shè)想能否利用這些空指針來存放指向其前驅(qū)或后繼的指針?這樣就可以像遍歷單鏈表那樣方便地遍歷二叉樹。引入線索二叉樹正是為了加快查找結(jié)點(diǎn)前驅(qū)和后繼的速度。
我們把這種指向前驅(qū)和后繼的指針稱為線索，加上線索的二叉鏈表稱為線索鏈表，相應(yīng)的二叉樹就稱為線索二叉樹(Threaded Binary Tree)。

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

其中

• ltag為0時指向該結(jié)點(diǎn)的左孩子，為1時指向該結(jié)點(diǎn)的前驅(qū)。
• rtag為0時指向該結(jié)點(diǎn)的右孩子，為1時指向該結(jié)點(diǎn)的后繼。

因此對于上圖的二叉鏈表圖可以修改為下圖的樣子。

2、線索二叉樹的結(jié)構(gòu)實(shí)現(xiàn)

二叉樹的線索存儲結(jié)構(gòu)代碼如下：

typedef struct ThreadNode{ElemType data; //數(shù)據(jù)元素struct ThreadNode *lchild, *rchild; //左、右孩子指針int ltag, rtag; //左、右線索標(biāo)志 }ThreadNode, *ThreadTree;

3、二叉樹的線索化

二叉樹的線索化是將二叉鏈表中的空指針改為指向前驅(qū)或后繼的線索。而前驅(qū)或后繼的信息只有在遍歷時才能得到，因此線索化的實(shí)質(zhì)就是遍歷一次二叉樹，線索化的過程就是在遍歷的過程中修改空指針的過程。

（1）中序線索二叉樹

以中序線索二叉樹的建立為例。附設(shè)指針pre指向剛剛訪問過的結(jié)點(diǎn)，指針p指向正在訪問的結(jié)點(diǎn)，即pre指向p的前驅(qū)。在中序遍歷的過程中，檢查p的左指針是否為空，若為空就將它指向pre;檢查pre的右指針是否為空，若為空就將它指向p，如下圖所示。

通過中序遍歷對二叉樹線索化的遞歸算法如下:

void InThread(ThreadTree p, ThreadTree pre){if(p != NULL){InThread(p->lchild, pre); //遞歸，線索化左子樹if(p->lchild == NULL){ //左子樹為空，建立前驅(qū)線索p->lchild = pre;p->ltag = 1;}if(pre != NULL && pre->rchild == NULL){pre->rchild = p; //建立前驅(qū)結(jié)點(diǎn)的后繼線索pre->rtag = 1;}pre = p; //標(biāo)記當(dāng)前結(jié)點(diǎn)成為剛剛訪問過的結(jié)點(diǎn)InThread(p->rchild, pre); //遞歸，線索化右子樹} }

你會發(fā)現(xiàn)，除了中間的代碼，和二叉樹中序遍歷的遞歸代碼幾乎完全一樣。只不過將本是訪問結(jié)點(diǎn)的功能改成了線索化的功能。

通過中序遍歷建立中序線索二叉樹的主過程算法如下:

void CreateInThread(ThreadTree T){ThreadTree pre = NULL;if(T != NULL){InThread(T, pre); //線索化二叉樹pre->rchild = NULL; //處理遍歷的最后一個結(jié)點(diǎn)pre->rtag = 1;} }

為了方便,可以在二叉樹的線索鏈表上也添加一個頭結(jié)點(diǎn)，令其lchild域的指針指向二叉樹的根結(jié)點(diǎn)，其rchild域的指針指向中序遍歷時訪問的最后一個結(jié)點(diǎn);令二叉樹中序序列中的第一個結(jié)點(diǎn)的lchild域指針和最后一個結(jié)點(diǎn)的rchild域指針均指向頭結(jié)點(diǎn)。這好比為二叉樹建立了一個雙向線索鏈表，方便從前往后或從后往前對線索二叉樹進(jìn)行遍歷，如下圖所示。

遍歷的代碼如下：

/*T指向頭結(jié)點(diǎn)，頭結(jié)點(diǎn)左鏈lchild指向根結(jié)點(diǎn)，頭結(jié)點(diǎn)右鏈rchild指向中序遍 的最后一個結(jié)點(diǎn)。中序遍歷二叉線索鏈表表示的二叉樹T*/ void InOrderTraverse_Thr(BiThrTree T){BiThrTree p;p = T->lchild; //p指向根結(jié)點(diǎn)//空樹或遍歷結(jié)束時，p==T（最后一個結(jié)點(diǎn)指向根結(jié)點(diǎn)）while(p != T){ //當(dāng)ltag==0時循環(huán)到中序序列第一個結(jié)點(diǎn)while(p->ltag == 0){ p = p->lchild; //p指向p的左子樹}visit(p); //訪問該結(jié)點(diǎn)//后繼線索為1且不是指向頭指針while(p->rtag == 1 && p->rchild != T){ p = p->rchild; //p指向p的后繼visit(p); //訪問該節(jié)點(diǎn)}//p進(jìn)至其右子樹根，開始對右子樹根進(jìn)行遍歷p = p->rchild; } }

從這段代碼也可以看出，它等于是一個鏈表的掃描,所以時間復(fù)雜度為0(n)。
由于它充分利用了空指針域的空間(這等于節(jié)省了空間)，又保證了創(chuàng)建時的一次遍歷就可以終生受用前驅(qū)后繼的信息(這意味著節(jié)省了時間)。所以在實(shí)際問題中，如果所用的二叉樹需經(jīng)常遍歷或查找結(jié)點(diǎn)時需要某種遍歷序列中的前驅(qū)和后繼，那么采用線索二叉鏈表的存儲結(jié)構(gòu)就是非常不錯的選擇。

（2）先序和后序線索二叉樹

上面給出了建立中序線索二叉樹的代碼，建立先序線索二叉樹和后序線索二叉樹的代碼類似，只需變動線索化改造的代碼段與調(diào)用線索化左右子樹遞歸函數(shù)的位置。
以圖(a)的二叉樹為例，其先序序列為ABCDF，后序序列為CDBFA，可得出其先序和后序線索二叉樹分別如圖(b)和( c)所示：

如何在先序線索二叉樹中找結(jié)點(diǎn)的后繼?如果有左孩子，則左孩子就是其后繼;如果無左孩子但有右孩子，則右孩子就是其后繼;如果為葉結(jié)點(diǎn)，則右鏈域直接指示了結(jié)點(diǎn)的后繼。
在后序線索二叉樹中找結(jié)點(diǎn)的后繼較為復(fù)雜，可分3種情況:①若結(jié)點(diǎn)x是二叉樹的根，則其后繼為空;②若結(jié)點(diǎn)x是其雙親的右孩子，或是其雙親的左孩子且其雙親沒有右子樹，則其后繼即為雙親;③若結(jié)點(diǎn)x是其雙親的左孩子，且其雙親有右子樹，則其后繼為雙親的右子樹上按后序遍歷列出的第一個結(jié)點(diǎn)。圖( c)中找結(jié)點(diǎn)B的后繼無法通過鏈域找到，可見在后序線索二叉樹上找后繼時需知道結(jié)點(diǎn)雙親，即需采用帶標(biāo)志域的三叉鏈表作為存儲結(jié)構(gòu)。

四、樹、森林與二叉樹的轉(zhuǎn)化

在講樹的存儲結(jié)構(gòu)時，我們提到了樹的孩子兄弟法可以將一棵樹用二叉鏈表進(jìn)行存儲，所以借助二叉鏈表，樹和二叉樹可以相互進(jìn)行轉(zhuǎn)換。從物理結(jié)構(gòu)來看，它們的二叉鏈表也是相同的，只是解釋不太一樣而已。 因此，只要我們設(shè)定一定的規(guī)則，用二叉樹來表示樹，甚至表示森林都是可以的，森林與二叉樹也可以互相進(jìn)行轉(zhuǎn)換。

1、樹轉(zhuǎn)換為二叉樹

樹轉(zhuǎn)換為二義樹的規(guī)則:每個結(jié)點(diǎn)左指針指向它的第一個孩子，右指針指向它在樹中的相鄰右兄弟，這個規(guī)則又稱“左孩子右兄弟”。由于根結(jié)點(diǎn)沒有兄弟，所以對應(yīng)的二叉樹沒有右子樹。

樹轉(zhuǎn)換成二叉樹的畫法:

在兄弟結(jié)點(diǎn)之間加一連線;

對每個結(jié)點(diǎn)，只保留它與第一個孩子的連線，而與其他孩子的連線全部抹掉;

以樹根為軸心，順時針旋轉(zhuǎn)45°。

2、森林轉(zhuǎn)化為二叉樹

森林是由若干棵樹組成的，所以完全可以理解為,森林中的每一棵樹都是兄弟，可以按照兄弟的處理辦法來操作。
森林轉(zhuǎn)換成二叉樹的畫法:

將森林中的每棵樹轉(zhuǎn)換成相應(yīng)的二叉樹;

每棵樹的根也可視為兄弟關(guān)系，在每棵樹的根之間加一根連線;

以第一棵樹的根為軸心順時針旋轉(zhuǎn)45°。

至于二叉樹轉(zhuǎn)換為樹或者二叉樹轉(zhuǎn)換為森林只不過是上面步驟的逆過程，在此不做贅述。

五、樹和森林的遍歷

1、樹的遍歷

樹的遍歷是指用某種方式訪問樹中的每個結(jié)點(diǎn)，且僅訪問一次。主要有兩種方式:

先根遍歷。若樹非空，先訪問根結(jié)點(diǎn)，再依次遍歷根結(jié)點(diǎn)的每棵子樹，遍歷子樹時仍遵循先根后子樹的規(guī)則。其遍歷序列與這棵樹相應(yīng)二叉樹的先序序列相同。

后根遍歷。若樹非空，先依次遍歷根結(jié)點(diǎn)的每棵子樹，再訪問根結(jié)點(diǎn)，遍歷子樹時仍遵循先子樹后根的規(guī)則。其遍歷序列與這棵樹相應(yīng)二叉樹的中序序列相同。

下圖的樹的先根遍歷序列為ABEFCDG,后根遍歷序列為EFBCGDA。

另外，樹也有層次遍歷，與二叉樹的層次遍歷思想基本相同，即按層序依次訪問各結(jié)點(diǎn)。

2、森林的遍歷

按照森林和樹相互遞歸的定義，可得到森林的兩種遍歷方法。

先序遍歷森林。若森林為非空，則按如下規(guī)則進(jìn)行遍歷:
●訪問森林中第一棵樹的根結(jié)點(diǎn)。
●先序遍歷第一棵樹中根結(jié)點(diǎn)的子樹森林。
●先序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。

后序遍歷森林。森林為非空時，按如下規(guī)則進(jìn)行遍歷:
●后序遍歷森林中第一棵樹的根結(jié)點(diǎn)的子樹森林。
●訪問第一棵樹的根結(jié)點(diǎn)。
●后序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。

圖5.17的森林的先序遍歷序列為ABCDEFGHI，后序遍歷序列為BCDAFEHIG。

當(dāng)森林轉(zhuǎn)換成二叉樹時，其第一棵樹的子樹森林轉(zhuǎn)換成左子樹，剩余樹的森林轉(zhuǎn)換成右子樹，可知森林的先序和后序遍歷即為其對應(yīng)二叉樹的先序和中序遍歷。

樹與二叉樹的應(yīng)用

一、二叉排序樹

1、定義

二叉排序樹(也稱二叉查找樹)或者是一棵空樹，或者是具有下列特性的二叉樹:

若左子樹非空，則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值。

若右子樹非空，則右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值。

左、右子樹也分別是一棵二叉排序樹。

根據(jù)二叉排序樹的定義，左子樹結(jié)點(diǎn)值<根結(jié)點(diǎn)值<右子樹結(jié)點(diǎn)值，所以對二叉排序樹進(jìn)行中序遍歷，可以得到一個遞增的有序序列。例如，下圖所示二叉排序樹的中序遍歷序列為123468。

2、二叉排序樹的常見操作

構(gòu)造一個二叉樹的結(jié)構(gòu)：

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

（1）查找操作

/* 遞歸查找二叉排序樹T中是否存在key 指針f指向T的雙親，其初始調(diào)用值為NULL 若查找成功，則指針p指向該數(shù)據(jù)元素結(jié)點(diǎn)，并返回TRUE 否則指針p指向查找路徑上訪問的最后一個結(jié)點(diǎn)并返回FALSE */ bool SearchBST(BiTree T, int key, BiTree f, BiTree *p){if(!T){*p = f;return FALSE;}else if(key == T->data){//查找成功*p = T;return TRUE;}else if(key < T->data){return SearchBST(T->lchild, key, T, p); //在左子樹繼續(xù)查找}else{return SearchBST(T->rchild, key, T, p); //在右子樹繼續(xù)查找} }

（2）插入操作

有了二叉排序樹的查找函數(shù)，那么所謂的二叉排序樹的插入，其實(shí)也就是將關(guān)鍵字放到樹中的合適位置而已。

/* 當(dāng)二叉排序樹T中不存在關(guān)鍵字等于key的數(shù)據(jù)元素時 插入key并返回TRUE，否則返回FALSE */ bool InsertBST(BiTree *T, int key){BiTree p, s;if(!SearchBST(*T, key, NULL, &p)){//查找不成功s = (BiTree)malloc(sizeof(BiTNode));s->data = key;s->lchild = s->rchild = NULL;if(!p){*T = s; //插入s為新的根節(jié)點(diǎn)}else if(key < p->data){p->lchild = s; //插入s為左孩子}else{p->rchild = s; //插入s為右孩子}return TRUE;}else{return FALSE; //樹種已有關(guān)鍵字相同的結(jié)點(diǎn)，不再插入} }

有了二叉排序樹的插入代碼，我們要實(shí)現(xiàn)二叉排序樹的構(gòu)建就非常容易了，幾個例子：

int i; int a[10] = {62, 88, 58, 47, 35, 73, 51, 99, 37, 93}; BiTree T = NULL; for(i = 0; i<10; i++){InsertBST(&T, a[i]); }

上面的代碼就可以創(chuàng)建一棵下圖這樣的樹。

（3）刪除操作

二叉排序樹的查找和插入都很簡單，但是刪除操作就要復(fù)雜一些，此時要刪除的結(jié)點(diǎn)有三種情況：

葉子結(jié)點(diǎn)；

僅有左或右子樹的結(jié)點(diǎn)；

左右子樹都有的結(jié)點(diǎn)；

前兩種情況都很簡單，第一種只需刪除該結(jié)點(diǎn)不需要做其他操作；第二種刪除后需讓被刪除結(jié)點(diǎn)的直接后繼接替它的位置；復(fù)雜就復(fù)雜在第三種，此時我們需要遍歷得到被刪除結(jié)點(diǎn)的直接前驅(qū)或者直接后繼來接替它的位置，然后再刪除。
第三種情況如下圖所示：

代碼如下：

/* 若二叉排序樹T中存在關(guān)鍵字等于key的數(shù)據(jù)元素時，則刪除該數(shù)據(jù)元素結(jié)點(diǎn)， 并返回TRUE;否則返回FALSE */ bool DeleteBST(BiTree *T, int key){if(!*T){return FALSE; }else{if(key == (*T)->data){//找到關(guān)鍵字等于key的數(shù)據(jù)元素return Delete(T);}else if(key < (*T) -> data){return DeleteBST((*T) -> lchild, key);}else{return DeleteBST((*T) -> rchild, key);}} }

下面是Delete()方法：

/*從二叉排序樹中刪除結(jié)點(diǎn)p，并重接它的左或右子樹。*/ bool Delete(BiTree *p){BiTree q, s;if(p->rchild == NULL){//右子樹為空則只需重接它的左子樹q = *p;*p = (*p)->lchild;free(q);}else if((*p)->lchild == NULL){//左子樹為空則只需重接它的右子樹q = *p;*p = (*p)->rchild;free(q);}else{//左右子樹均不空q = *p;s = (*p)->lchild; //先轉(zhuǎn)左while(s->rchild){//然后向右到盡頭，找待刪結(jié)點(diǎn)的前驅(qū)q = s;s = s->rchild;}//此時s指向被刪結(jié)點(diǎn)的直接前驅(qū)，p指向s的父母節(jié)點(diǎn)p->data = s->data; //被刪除結(jié)點(diǎn)的值替換成它的直接前驅(qū)的值if(q != *p){q->rchild = s->lchild; //重接q的右子樹}else{q->lchild = s->lchild; //重接q的左子樹}pree(s);}return TRUE; }

3、小結(jié)（引申出平衡二叉樹）

二叉排序樹的優(yōu)點(diǎn)明顯，插入刪除的時間性能比較好。而對于二叉排序樹的查找，走的就是從根結(jié)點(diǎn)到要查找的結(jié)點(diǎn)的路徑，其比較次數(shù)等于給定值的結(jié)點(diǎn)在二叉排序樹的層數(shù)。極端情況，最少為1次，即根結(jié)點(diǎn)就是要找的結(jié)點(diǎn)，最多也不會超過樹的深度。也就是說，二叉排序樹的查找性能取決于二叉排序樹的形狀。可問題就在于，二叉排序樹的形狀是不確定的。
例如$\{62,88,58,47,35,73,51,99,37,93\}$這樣的數(shù)組，我們可以構(gòu)建如下左圖的二叉排序樹。但如果數(shù)組元素的次序是從小到大有序，如{35,37,47,51,58,62,73,88,93,99},則二叉排序樹就成了極端的右斜樹，如下面右圖的二叉排序樹：

也就是說，我們希望二叉排序樹是比較平衡的，即其深度與完全二叉樹相同，那么查找的時間復(fù)雜也就為$O(logn)$，近似于折半查找。
不平衡的最壞情況就是像上面右圖的斜樹，查找時間復(fù)雜度為$O(n)$，這等同于順序查找。
因此，如果我們希望對一個集合按二叉排序樹查找，最好是把它構(gòu)建成一棵平衡的二叉排序樹。

---

二、平衡二叉樹

1、定義

平衡二叉樹(Self-Balancing Binary Search Tree 或 Height-Balanced Binary Search Tree)是一種二叉排序樹，其中每一個節(jié)點(diǎn)的左子樹和右子樹的高度差至多等于1。
它是一種高度平衡的二叉排序樹。它要么是一棵空樹， 要么它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差的絕對值不超過1。我們將二叉樹上結(jié)點(diǎn)的左子樹深度減去右子樹深度的值稱為平衡因子BF (Balance Factor) ， 那么平衡二叉樹上所有結(jié)點(diǎn)的平衡因子只可能是-1、0和1。只要二叉樹上有一個結(jié)點(diǎn)的平衡因子的絕對值大于1，則該二叉樹就是不平衡的。

2、平衡二叉樹的查找

在平衡二叉樹上進(jìn)行查找的過程與二叉排序樹的相同。因此，在查找過程中，與給定值進(jìn)行比較的關(guān)鍵字個數(shù)不超過樹的深度。假設(shè)以$n_h$表示深度為$h$的平衡樹中含有的最少結(jié)點(diǎn)數(shù)。顯然，有$n_0=0,n_1=1,n_2=2$，并且有$n_h=n_{h?1}+n_{h?2}+1$。可以證明，含有$n$個結(jié)點(diǎn)的平衡二叉樹的最大深度為$O(log2n)$，因此平衡二叉樹的平均查找長度為$O(log2n)$ 如下圖所示。

3、平衡二叉樹的插入

二叉排序樹保證平衡的基本思想如下：每當(dāng)在二叉排序樹中插入(或刪除)一個結(jié)點(diǎn)時，首先檢查其插入路徑上的結(jié)點(diǎn)是否因?yàn)榇舜尾僮鞫鴮?dǎo)致了不平衡。若導(dǎo)致了不平衡，則先找到插入路徑上離插入結(jié)點(diǎn)最近的平衡因子的絕對值大于1的結(jié)點(diǎn)A，再對以A為根的子樹，在保持二叉排序樹特性的前提下，調(diào)整各結(jié)點(diǎn)的位置關(guān)系，使之重新達(dá)到平衡。
注意:每次調(diào)整的對象都是最小不平衡子樹，即以插入路徑上離插入結(jié)點(diǎn)最近的平衡因子的絕對值大于1的結(jié)點(diǎn)作為根的子樹。下圖中的虛線框內(nèi)為最小不平衡子樹。

平衡二叉樹的插入過程的前半部分與二叉排序樹相同，但在新結(jié)點(diǎn)插入后，若造成查找路徑上的某個結(jié)點(diǎn)不再平衡，則需要做出相應(yīng)的調(diào)整。可將調(diào)整的規(guī)律歸納為下列4種情況：

LL平衡旋轉(zhuǎn)(右單旋轉(zhuǎn))。由于在結(jié)點(diǎn)A的左孩子(L)的左子樹(L)上插入了新結(jié)點(diǎn)，A的平衡因子由1增至2，導(dǎo)致以A為根的子樹失去平衡，需要一次向右的旋轉(zhuǎn)操作。將A的左孩子B向右上旋轉(zhuǎn)代替A成為根結(jié)點(diǎn)，將A結(jié)點(diǎn)向右下旋轉(zhuǎn)成為B的右子樹的根結(jié)點(diǎn)，而B的原右子樹則作為A結(jié)點(diǎn)的左子樹。
如下圖所示，結(jié)點(diǎn)旁的數(shù)值代表結(jié)點(diǎn)的平衡因子，而用方塊表示相應(yīng)結(jié)點(diǎn)的子樹，下方數(shù)值代表該子樹的高度。

RR平衡旋轉(zhuǎn)(左單旋轉(zhuǎn))。由于在結(jié)點(diǎn)A的右孩子?的右子樹?上插入了 新結(jié)點(diǎn)，A的平衡因子由-1減至-2，導(dǎo)致以A為根的子樹失去平衡，需要一次向左的旋轉(zhuǎn)操作。將A的右孩子B向左上旋轉(zhuǎn)代替A成為根結(jié)點(diǎn)，將A結(jié)點(diǎn)向左下旋轉(zhuǎn)成為B的左子樹的根結(jié)點(diǎn)，而B的原左子樹則作為A結(jié)點(diǎn)的右子樹。

LR平衡旋轉(zhuǎn)(先左后右雙旋轉(zhuǎn))。由于在A的左孩子(L)的右子樹?上插入新結(jié)點(diǎn)，A的平衡因子由1增至2，導(dǎo)致以A為根的子樹失去平衡，需要進(jìn)行兩次旋轉(zhuǎn)操作，先左旋轉(zhuǎn)后右旋轉(zhuǎn)。先將A結(jié)點(diǎn)的左孩子B的右子樹的根結(jié)點(diǎn)C向左上旋轉(zhuǎn)提升到B結(jié)點(diǎn)的位置（即進(jìn)行一次RR平衡旋轉(zhuǎn)(左單旋轉(zhuǎn))），然后再把該C結(jié)點(diǎn)向右上旋轉(zhuǎn)提升到A結(jié)點(diǎn)的位置（即進(jìn)行一次LL平衡旋轉(zhuǎn)(右單旋轉(zhuǎn))）。

RL平衡旋轉(zhuǎn)(先右后左雙旋轉(zhuǎn))。由于在A的右孩子?的左子樹(L)上插入新結(jié)點(diǎn)，A的平衡因子由-1減至-2，導(dǎo)致以A為根的子樹失去平衡，需要進(jìn)行兩次旋轉(zhuǎn)操作，先右旋轉(zhuǎn)后左旋轉(zhuǎn)。先將A結(jié)點(diǎn)的右孩子B的左子樹的根結(jié)點(diǎn)C向右上旋轉(zhuǎn)提升到B結(jié)點(diǎn)的位置（即進(jìn)行一次LL平衡旋轉(zhuǎn)(右單旋轉(zhuǎn))），然后再把該C結(jié)點(diǎn)向左上旋轉(zhuǎn)提升到A結(jié)點(diǎn)的位置（即進(jìn)行一次RR平衡旋轉(zhuǎn)(左單旋轉(zhuǎn))）。
注意: LR和RL旋轉(zhuǎn)時，新結(jié)點(diǎn)究竟是插入C的左子樹還是插入C的右子樹不影響旋轉(zhuǎn)過程，而上圖中是以插入C的左子樹中為例。

舉個例子：
假設(shè)關(guān)鍵字序列為$15,3,7,10,9,8$，通過該序列生成平衡二叉樹的過程如下圖所示。

二叉排序樹還有另外的平衡算法，如紅黑樹(Red Black Tree)等，與平衡二叉樹(AVL樹)相比各有優(yōu)勢。

---

三、哈夫曼樹和哈夫曼編碼

1、哈夫曼樹的定義和原理

在許多應(yīng)用中，樹中結(jié)點(diǎn)常常被賦予一個表示某種意義的數(shù)值，稱為該結(jié)點(diǎn)的權(quán)。從樹的根到任意結(jié)點(diǎn)的路徑長度(經(jīng)過的邊數(shù))與該結(jié)點(diǎn)上權(quán)值的乘積，稱為該結(jié)點(diǎn)的帶權(quán)路徑長度。樹中所有葉結(jié)點(diǎn)的帶權(quán)路徑長度之和稱為該樹的帶權(quán)路徑長度，記為$$WPL=\sum _{i=1}^n{w}_i{l}_i$$式中，$w_i$是第i個葉結(jié)點(diǎn)所帶的權(quán)值，$l_i$是該葉結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑長度。
在含有n個帶權(quán)葉結(jié)點(diǎn)的二叉樹中，其中帶權(quán)路徑長度(WPL)最小的二叉樹稱為哈夫曼樹，也稱最優(yōu)二叉樹。例如，下圖中的3棵二叉樹都有4個葉子結(jié)點(diǎn)a, b,c,d,分別帶權(quán)7,5,2,4，它們的帶權(quán)路徑長度分別為

a. WPL = 7x2 + 5x2 + 2x2 + 4x2 = 36。
b. WPL = 4x2 + 7x3 + 5x3 + 2x1 = 46。
c. WPL = 7x1 + 5x2 + 2x3 + 4x3 = 35。
其中，圖c樹的WPL最小。可以驗(yàn)證，它恰好為哈夫曼樹。

2、哈夫曼樹的構(gòu)造

步驟：

先把有權(quán)值的葉子結(jié)點(diǎn)按照從大到小（從小到大也可以）的順序排列成一個有序序列。

取最后兩個最小權(quán)值的結(jié)點(diǎn)作為一個新節(jié)點(diǎn)的兩個子結(jié)點(diǎn)，注意相對較小的是左孩子。

用第2步構(gòu)造的新結(jié)點(diǎn)替掉它的兩個子節(jié)點(diǎn)，插入有序序列中，保持從大到小排列。

重復(fù)步驟2到步驟3，直到根節(jié)點(diǎn)出現(xiàn)。

看圖就清晰了，如下圖所示：

3、哈夫曼編碼

赫夫曼當(dāng)前研究這種最優(yōu)樹的目的是為了解決當(dāng)年遠(yuǎn)距離通信(主要是電報)的數(shù)據(jù)傳輸?shù)淖顑?yōu)化問題。
哈夫曼編碼是一種被廣泛應(yīng)用而且非常有效的數(shù)據(jù)壓縮編碼。
比如我們有一段文字內(nèi)容為“ BADCADFEED”要網(wǎng)絡(luò)傳輸給別人，顯然用二進(jìn)制的數(shù)字(0和1)來表示是很自然的想法。我們現(xiàn)在這段文字只有六個字母ABCDEF，那么我們可以用相應(yīng)的二進(jìn)制數(shù)據(jù)表示，如下表所示：

這樣按照固定長度編碼編碼后就是“001000011010000011101100100011”，對方接收時可以按照3位一分來譯碼。如果一篇文章很長，這樣的二進(jìn)制串也將非常的可怕。而且事實(shí)上，不管是英文、中文或是其他語言，字母或漢字的出現(xiàn)頻率是不相同的。
假設(shè)六個字母的頻率為A 27,B 8,C 15,D 15,E 30,F 5,合起來正好是
100%。那就意味著，我們完全可以重新按照赫夫曼樹來規(guī)劃它們。
下圖左圖為構(gòu)造赫夫曼樹的過程的權(quán)值顯示。右圖為將權(quán)值左分支改為0，右分支改為1后的赫夫曼樹。

這棵哈夫曼樹的WPL為:
$WPL=2?(15+27+30)+3?15+4?(5+8)=241$
此時，我們對這六個字母用其從樹根到葉子所經(jīng)過路徑的0或1來編碼，可以得到如下表所示這樣的定義。

若沒有一個編碼是另一個編碼的前綴，則稱這樣的編碼為前綴編碼。
我們將文字內(nèi)容為“ BADCADFEED”再次編碼，對比可以看到結(jié)果串變小了。

• 原編碼二進(jìn)制串: 000011000011101100100011 (共 30個字符)
• 新編碼二進(jìn)制串: 10100101010111100(共25個字符)

也就是說，我們的數(shù)據(jù)被壓縮了，節(jié)約了大約17%的存儲或傳輸成本。

注意:
0和1究竟是表示左子樹還是右子樹沒有明確規(guī)定。左、右孩子結(jié)點(diǎn)的順序是任意的，所以構(gòu)造出的哈夫曼樹并不唯一，但各哈夫曼樹的帶權(quán)路徑長度WPL相同且為最優(yōu)。此外，如有若干權(quán)值相同的結(jié)點(diǎn)，則構(gòu)造出的哈夫曼樹更可能不同，但WPL必然相同且是最優(yōu)的。

---

附錄

上文鏈接

數(shù)據(jù)結(jié)構(gòu)：串

下文鏈接

數(shù)據(jù)結(jié)構(gòu)：圖

專欄

數(shù)據(jù)結(jié)構(gòu)專欄

參考資料

1、嚴(yán)蔚敏、吳偉民：《數(shù)據(jù)結(jié)構(gòu)（C語言版）》
2、程杰：《大話數(shù)據(jù)結(jié)構(gòu)》
3、王道論壇：《數(shù)據(jù)結(jié)構(gòu)考研復(fù)習(xí)指導(dǎo)》
4、托馬斯·科爾曼等人：《算法導(dǎo)論》

總結(jié)

以上是生活随笔為你收集整理的数据结构：树(Tree)【详解】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。