算法設計：數據結構-樹

一、樹的概念

一個結點有一個前驅和多個後繼結點，這種數據結構是樹形結構

1、樹的定義

樹（Tree）是n個結點的集合，集合中有一個稱為根（root）的特殊節點，在根節點分布著一些互相不相交的集合，每個集合又是一個樹，這些樹稱為根節點的子樹

（1）空集合也是樹

（2）單個結點是一棵樹，樹根就是該結點本身

（3）若某樹有多個結點，則每個節點都可以看成是根結點

（4）在一棵樹中，有且僅有一個結點沒有前驅，這個結點就是根節點

（5）除根結點外，其餘每個結點有且僅有一個前驅，如圖B的前驅為A，不能有其它前驅

（6）每個結點可以有任意多個後繼例如：A有B、C、D三個後繼

2、樹的相關術語

（1）父節點、子節點、兄弟結點

每個節點的子樹的根稱為該結點的兒子（子結點），相應的，該結點被稱為子結點的父親（父節點），具有同一父結點的的結點稱為兄弟結點，例如結點A是B、C、D的父結點，相應的，結點B、C、D就是結點A的子結點，而結點B、C、D之間是兄弟結點。對這種層次關係進行擴展，可得出祖先結點和子孫結點等關係

（2）結點的度

一個結點的子樹的數量稱為該結點的 "度"。例如：結點A有3個子樹，因此結點A的"度"是3；而結點B、C、D的"度"分別為1、2、2

（3）樹的度

一棵樹的度是指該樹中結點的最大度數，上圖樹的度為3（結點A的度為3）

4）葉結點和分支結點

樹中度為零的結點稱為葉節點或終端節點。樹中度不為零的結點稱為分支結點或非終端節點。節點E、J、K、L、M、N為葉節點

（5）節點的層數

樹是一種層次結構，每個節點都是處在一定的層次上

（6）樹的深度

一棵樹中節點的最大層數稱為樹的深度。例如，圖中所示的樹的深度為4

（7）有序樹和無序樹

若樹中各節點的子樹（兄弟節點）是按一定次序從左向右安排的，稱為有序樹，否則稱為無序樹

（8）森林

森林是m(m>=0)課互不相交的樹的集合。如果刪去圖中所示樹的根節點A，留下的3棵子樹就構成了一個森林

3、樹的表示

樹的表示方法很多，常用的方法是用括號：先將根節點放入一對圓括號中，然後把它的子樹由左至右的順序放入括號中，而對子樹也採用同樣的方法處理；同層子樹與它的根節點用圓括號括起來，同層子樹之間用逗號隔開，最後用閉括號括起來

（ A( B(E) ) ,(C(F(J)),(G (K,L))),(D(H),(I(M,N)))）

二、二叉樹的概念

在樹的應用中，二叉樹特別重要，這是因為處理樹的許多算法應用到二叉樹時變得非常簡單，而任意的樹又可以方便的轉換為對應的二叉樹。因此，只需要定義二叉樹的算法，然後將其它樹轉換為二叉樹，即可方便的對所有樹進行操作

1、二叉樹的定義

一個二叉樹是n個結點的集合，此集合要麼是空集，要麼是由一個根節點加上分別稱為左子樹和右子樹的兩個互不相交的二叉樹

二叉樹任意節點最多只能有兩個子節點；如果只有一個子節點，可以是左子樹也可以是右子樹。因此，二叉樹有5種基本形態：

（1）空

沒有任何節點

（2）僅有根節點

只有根節點，沒有子節點

（3）僅有左子樹

（4）僅有右子樹

（5）左右子樹都有

2、二叉樹和樹的兩個主要差別如下：

（1）樹中節點的最大度數沒有限制，而二叉樹節點的最大度數為2

（2）樹的節點無左右之分，而二叉樹的節點有左右之分，因為二叉樹有左右之分，所以二叉樹是有序樹

3、特殊的二叉樹

（1）滿二叉樹

在二叉樹中，除最下一層的葉子節點外，每層的節點都有2個子節點，就構成了滿二叉樹

（2）完全二叉樹

除二叉樹最後一層外，其它各層的節點數都達到最大個數，且最後一層從左向右的葉節點連續存在，只缺右側若干節點，就是完全二叉樹

4、二叉樹的性質

（1）在二叉樹中，第i層的節點總數最多為

個

（2）深度為k的二叉樹最多有

個節點（k>=1）

（3）對於一個二叉樹，如果其葉節點數為n0，而度為2的節點總數為n2，則n0=n2+1

（4）具有n個節點的完全二叉樹的深度k為：k = [log2n ] + 1

（5）有n個節點的完全二叉樹各節點如果用順序方式存儲，對任意節點i，有如下關係：

如果i!=1，則其父節點的編號為i/2

如果2*i<=n，則其左子樹根節點編號為2*i；若2*I > n，則無左子樹

如果2*i + 1 <=n，則其右子樹根節點編號為2*i + 1；若2*i +1 > n，則無右子樹

三、二叉樹的存儲

二叉樹通常可採用順序存儲結構和鏈式存儲結構

1、順序存儲結構

與線性表的順序存儲類似，二叉樹的順序存儲結構一般也由一個一維數組來構成，二叉樹上的節點按某種規定的次序逐個保存到數組的各個單元中

二叉樹順序存儲結構的數據定義如下：

#define MAXSIZE 100 //最大節點數

typedef int DATA ; //元素類型

typedef DATA seqBinTree[MAXSIZE ];

seqBinTree SBT; //定義保存二叉樹組

對於一個完全二叉樹，若用順序存儲，各節點之間具有對應關係。如下：

對於一個完全二叉樹，若用順序存儲，各節點之間具有對應關係。例如，對於節點i，其父節點為i/2（若商不整數，則進行取整），而其左子節點的編號為2*i，右子節點的編號為2*i+1

對於節點E，由於存儲在數組第5個位置，可推算出其父節點的序號為5/2 = 2，即其父節點為節點B。而如果節點E有子節點，則其左子節點的序號為2*5 =10，即其左子節點為J。同樣，如果有右子節點，則其右子節點的序號為11，即節點K

如果順序存儲的二叉樹不是完全二叉樹，由於節點和數組中的序號沒了對應關係，就比較麻煩了。為了能使節點與數組序號有對應關係，一般採用的方法是；將非完全二叉樹轉換為完全二叉樹，將左側缺少的節點虛設為無數據的節點（這裡用「#」）

將此圖所示的完全二叉樹按順序保存到一維數組中，得到下圖所示：

但是，保存A---H共7個節點佔用15個存儲空間，造成存儲空間的浪費。因此，對於二叉樹的順序存儲，一般是適用於一些特殊情況（如保存完全二叉樹）

2、鏈式存儲結構

由於二叉樹的順序存儲結構會造成空間浪費，因此，大多數情況下，二叉樹都採用鏈式存儲結構。使用鏈式存儲結構非常符合二叉樹的邏輯結構，一個節點可以由節點元素和兩個分別指向左、右子樹的指針組成

四、操作二叉樹

1、定義二叉樹鏈式結構

#include <stdio.h>

#include <stdlib.h>

#define QUEUE_MAXSIZE 50;//隊列大小

typedef char DATA

typedef struct chainTree{

DATA data; //元素數據

struct chainTree *left;//左子樹指針

struct chainTree *right;//右子樹指針

} chainBinTree;

2、初始化二叉樹

chainBinTree * binTreeInit(chainBinTree * node){//初始化二叉樹根節點

if(node ! = NULL)

{

return node;

}else{

return NULL;

}

}

3、添加節點到二叉樹

bt 為父節點，node為子節點，n=1表示添加左子樹，n=2表示添加右子樹

int binTreeAddNode(chainBinTree *bt,chainBinTre *node,int n)

{

if(bt == NULL){

printf("父節點不存在，請先設置父節點！\n");

return 0;

}

switch(n){

case 1:

if(bt->left)//左子樹不為空

{

printf("左子樹不能為空");

return 0;

}else{

bt->left = node;

}

break;

case 2:

if(bt->right)//右子樹不為空

{

printf("右子樹不能為空");

return 0;

}else{

bt->right = node;

}

break;

default:

printf("參數錯誤");

return 0;

}

return 1;

}

4、獲取二叉樹左右的子樹

chainBinTree *binTreeLeft(chainBinTree *bt)

{

if(bt){

return bt->left;

}else{

return NULL;

}

}

chainBinTree *binTreeRight(chainBinTree *bt)

{

if(bt){

return bt->right;

}else{

return NULL;

}

}

5、獲取二叉樹狀態

檢查二叉樹是否為空

int binTreeIsEmpty(chainBinTree *bt){

if(bt)

return 0;

else

return 1;

}

求二叉樹的深度

int binTreeDeph(chainBinTree *bt){

int dep1,dep2;

if(bt==NULL){

return 0;//空樹深度為0

}else{

//左子樹深度（遞歸調用）

dep1 = binTreeDeph(bt->left)

//右子樹深度（遞歸調用）

dep2 = binTreeDeph(bt->right)

if(dep1 > dep2){

return dep1 + 1;

}else{

return dep2 + 1;

}

}

}

6、在二叉樹中查找

chainBinTree *binTreeFind(chainBinTree *bt,DATA data){

chainBinTree *p;

if(bt == NULL){

return NULL;

}else{

if(b->data == data){

return bt;

}else{

if(p = binTreeFind(bt->left,data))

return p;

else if(p = binTreeFind(bt->right,data))

return p;

else

return NULL;

}

}

}

該函數有2個參數，bt是需要查找的二叉樹的根節點，data為需要查找的節點數據

7、清空二叉樹

在向二叉樹添加節點時，每個節點都由malloc函數申請分配內存，因此需要清空二叉樹則必須使用free函數來釋放節點所佔的內存。清空二叉樹的操作就是通過遞歸調用，對二叉樹進行遍歷，釋放各個節點所佔的內存

105 void binTreeClear(chainBinTree *bt)

106 {

107 if(bt)

108 {

109 binTreeClear(bt->left);//清空左子樹

110 binTreeClear(bt->right);//清空了右子樹

111 free(bt);//釋放當前節點所佔內存

112 bt = NULL;

113 }

114 return;

115 }

該函數有一個參數bt，就是需要清空二叉樹的根節點。第107行進行判斷，若當前節點bt不為空（表示還佔用了系統內存），這時，不能直接使用free釋放當前節點所佔內存，因為該節點還可能有子樹，如果直接將該節點所佔內存釋放，則無法再連結到其左右子樹，造成內存被無效佔用。因此，這裡首先需要執行第109、110行遞歸調用當前函數，用來清空當前節點的左子樹和右子樹，最後在執行第111行釋放當前節點所佔內存

五、遍歷二叉樹

由於二叉樹是非線性結構，那麼將數據按二叉樹結構保存時，怎樣才能在所有節點中查找所需要的數據呢？這就需要定義一種算法，將二叉樹的各個節點轉換成一個線性序列來表示，以方便對各節點數據的檢索，這就是二叉樹的遍歷

遍歷是對樹的一種最基本的運算，所謂遍歷二叉樹，就是按一定的規則和順序走遍二叉樹的所有節點，使每一個節點都被訪問一次，而且只能被訪問一次

如下圖所示具有左右子樹的二叉樹，其中D表示根節點，L表示左子樹，R表示右子樹，對其進行遍歷有3種方式：

1、先序遍歷（DLR）：稱為先根次序遍歷，即先訪問根節點，再按先序遍歷左子樹，最後按先序遍歷右子樹

2、中序遍歷（LDR）：稱為中根次序遍歷，即先按中序遍歷左子樹，再訪問根節點，最後按中序遍歷右子樹

3、後序遍歷（LRD）：稱為後根次序遍歷，即先按後序遍歷左子樹，再按後序遍歷右子樹，最後訪問根節點

先序遍歷

1、算法的偽代碼描述

void binTree_DLR(binTree)

{

if(二叉樹不為空)

{

訪問根節點；

binTree_DLR(left); //先序遍歷左子樹

binTree_DLR(right);//先序遍歷右子樹

}

}

2、代碼實現

void preOrder(binTree root){

if(root != NULL ){

printf("%d",root->data);//訪問根結點

preOrder(root->lchild); //先序遍歷根節點的左子樹

preOrder(root->rchild); //先序遍歷根節點的右子樹

}

}

中序遍歷

void inOrder(binTree root){

if(root !=NULL ){

inOrder(root->lchild);//中序遍歷根結點的左子樹

printf("%d",root->data);//訪問根節點

inOrder(root->rchild);//中序遍歷根結點的右子樹

}

}

後序遍歷

void postOrder(binTree root){

if(root !=NULL ){

postOrder (root->lchild);//中序遍歷根結點的左子樹

postOrder (root->rchild);//中序遍歷根結點的右子樹

printf("%d",root->data);//訪問根節點

}

}

遍歷二叉樹的基本操作就是訪問節點，不論按照哪種次序遍歷，對於含有n個節點的二叉樹，遍歷算法的時間複雜度都為O(n)。因為在遍歷的過程中，每進行一次遞歸調用，都將函數的「活動記錄」壓入棧中，因此，棧的最大長度恰為樹的高度。所以，在最壞情況下，二叉樹有n個節點且高度為n的單枝樹，遍歷算法的空間複雜度也為O(n)

藉助一個棧，可將二叉樹的遞歸算法轉換為非遞歸算法。下面給出中序遍歷的非遞歸算法

int inOrderTraverse(binTree root){

initStack(st);//創建個空棧

p = root;//p指向樹根節點

while(p!=NULL || !initStack(st)){

if(p!=NULL){//不是空樹

push(st,p);//根節點指針進棧

p = p->lchild;//進入根的左子樹

}else{

q = top(st); pop(st);//棧頂元素出棧

printf("%d",q->data);//訪問根節點

p = q->rchild;//進入根的右子樹

}

}

}

對於二叉樹，還有層次遍歷。設二叉樹的根節點所在層樹為1,層序遍歷就是從樹的根節點出發，首先訪問第1層的樹根節點，然後從左到右依次訪問第2層上的節點，其次是第3層上的節點，以此類推，自上而下，自左至右逐層訪問樹中各節點的過程就是層序遍歷

上圖中按照層次遍歷的結果為：ABCDEFGHIJKL

//按照層次遍歷

public static void binTree_level(TreeNode root){

int QUEUE_MAXSIZE = 6;

TreeNode p;

TreeNode q[]=new TreeNode[QUEUE_MAXSIZE];//定義個順序隊列

int head = 0;//定義首序號

int tail = 0;//定義尾序號

if(root!=null){

//計算循環隊列隊尾序號

tail = (tail + 1)%QUEUE_MAXSIZE;

q[tail] = root;

}

//隊列不為空，進行循環

while(head!=tail){

//計算循環隊列隊首序號

head = (head + 1)%QUEUE_MAXSIZE;

//獲取隊首元素

p = q[head];

//若節點有左子樹，則左子樹進隊

if(p.left!=null){

tail = (tail+1)%QUEUE_MAXSIZE;

q[tail] = p.left;

}

//若節點有右子樹，則右子樹進隊

if(p.right!=null){

tail = (tail+1)%QUEUE_MAXSIZE;

q[tail] = p.right;

}

}

for(TreeNode obj:q){

if(obj!=null){

System.out.println(obj.value);

}

}

}

六、線索二叉樹

對於二叉樹進行遍歷得到的節點序列，可以將遍歷的結果看成是一個線性表。在該線性表中，除了第1個節點外，每個節點都有（且僅有）一個前驅；除了最後一個節點外，每個節點都有（且僅有）一個後繼。例如：下列二叉樹經過中序遍歷後結果為

B F D A C G E H

線索二叉樹的表示

當以二叉樹鍊表形式來保存二叉樹時，只能找到節點的左右子樹信息，而不能直接得到節點的前驅和後繼（只有通過遍歷，在動態過程中才能查到前驅和後繼的信息）。如果增加前驅和後繼的指針那麼增加了存儲的開銷。其實由二叉樹性質可知，對於一顆具有n個節點的二叉樹，對應的二叉樹鍊表中共有2n個指針域，其中n-1個用於指向除根節點外的n-1個節點，另外n+1個指針域為空。可以利用二叉樹中的這些空指針域來存放節點的前驅和後繼。將每個節點中為空的左指針或右指針分別用於指向節點的前驅和後繼，即可得到線索二叉樹

在一個線索二叉樹中，為了區別每個節點的左、右指針域所存放的是子樹指針，還是線索，必須在節點結構中增加兩個標誌域：一個是左線索標誌域lflag，另一個是右線索標誌域eflag。若某個標誌為1，則表示對應的指針域為線索，否則，對應的指針域為子樹指針

七、哈夫曼樹

1. 哈夫曼樹的構造

給定N個權值分別為w1, w2, ..., Wn的節點。構造哈夫曼樹的算法描述如下：

1）將這N個結點分別作為N棵樹僅含一個結點的二叉樹，構成森林F

2）構造一個新節點，並從F中選取兩棵根結點權值最小的樹作為新節點的左、右子樹， 並且將新節點的權值置為左、右子樹上根結點的權

值之和

3）從F中刪除剛才選出的兩棵樹，同時將新得到的樹加入F中

4）重複步驟2和3，直至F中只剩下一棵樹為止

2. 哈夫曼編碼

哈夫曼編碼是一種被廣泛應用而且非常有效的數據壓縮編碼，它是可變長度編碼。可變長編碼即可以對待處理字符串中不同字符使用不等長的二進位位表示，可變長編碼比固定長度編碼好很多，可以對頻率高的字符賦予短編碼，而對頻率較低的字符則賦予較長一些的編碼，從而可以使平均編碼長度減短，起到壓縮數據的效果。

哈夫曼編碼是前綴編碼。如果沒有一個編碼是另一個編碼的前綴，則稱這樣的編碼為前綴編碼。對前綴編碼的解碼也是相對簡單的，因為沒有一個碼是另一個編碼的前綴，所以可以識別出第一個編碼，將它翻譯為原碼，再對餘下的編碼文件重複同樣操作。

哈夫曼編碼首先要構造一棵哈夫曼樹，首先，將每個出現的字符當做一個獨立的結點，其權值作為它出現的頻度（或次數），然後構造哈夫曼樹。顯然所有字符節點均出現在葉子結點中。我們可以將字符的編碼解釋為從根至該字符路徑上標記的序列，其中標記為0表示"轉向左孩子"，標記為1表示為"轉向右孩子"。 如下圖，矩形方塊表示字符及出現的次數

因此，這棵哈夫曼樹的WPL為：

WPL = 1*45 + 3 * (13+12+16) + 4 * (5+9) = 224

哈夫曼樹練習

1、設哈夫曼樹中的節點總數為49，若用二叉鍊表作為存儲結構，則該哈夫曼樹中總共有個空指針域？

2、對於n（n大於等於2）個權值均不相同的字符構成哈夫曼樹，以下敘述正確的是（）

A、樹中一定沒有度為1的節點

B、該樹一定是一顆完全二叉樹

C、樹中任一非葉節點的權值一定不小於子孫中任一節點的權值

D、樹中兩個權值最小的節點一定是兄弟節點（假設這兩個節點恰好有兩個）

3、若以（4、5、6、7、8）作為葉節點的權值構造哈夫曼樹，則其帶權路徑長度是多少？

4、某段文本中各個字母出現的頻率是a為4、b為3、o為12、h為7，i為10，使用哈夫曼編碼，則可能的編碼是

A、 a(001) 、b(000)、h(01)、i（10）、o（11）

B、 a(000) 、b(0001)、h(001)、o（01）、i(1)

C、 a(000) 、b(001)、h(01)、i（10）、o（00）

D、 a(0000) 、b(0001)、h(001)、o（000）、i(1)

5、用二進位來編碼字符串「xyzwxyxx」，需要能夠根據編碼解碼回原來的字符串，則最少需要（）長度的二進位字符串

A、12 B、14 C、15 D、18 E、24