樹形結(jié)構(gòu)是一種十分重要的數(shù)據(jù)結(jié)構(gòu)。二叉樹庐冯、樹與樹林都屬于樹形結(jié)構(gòu)戚篙。
樹形結(jié)構(gòu)每個(gè)結(jié)點(diǎn)最多只有一個(gè)前驅(qū)結(jié)點(diǎn)撒汉，但可以有多個(gè)后繼的結(jié)構(gòu)。
5.1 二叉樹及其抽象數(shù)據(jù)類型
5.1.1 基本概念
二叉樹可以定義為結(jié)點(diǎn)的有限集合巢钓，這個(gè)集合或者為空集病苗，或者由根結(jié)點(diǎn)、左子樹和右子樹的二叉樹組成症汹。二叉樹是一個(gè)遞歸定義硫朦。
相關(guān)概念
父結(jié)點(diǎn)、左右孩子結(jié)點(diǎn)背镇、邊：
若x是某二叉樹的根結(jié)點(diǎn)咬展，結(jié)點(diǎn)y是x的左(右)子樹的根，則稱x是y的父結(jié)點(diǎn)瞒斩，y是x的左(右)孩子結(jié)點(diǎn)破婆。有序?qū)?lt;x, y>稱作從x到y(tǒng)的邊。
兄弟：
具有同一父結(jié)點(diǎn)的結(jié)點(diǎn)彼此稱作兄弟胸囱。
祖先荠割、子孫：
如果結(jié)點(diǎn)y在以結(jié)點(diǎn)x為根的左右子樹中，且 y != x旺矾，則稱x是y的祖先，y是x的子孫夺克。
路徑箕宙、路徑長(zhǎng)度：
如果x是y的一個(gè)祖先，又有x = x0铺纽， x1,..., xn = y柬帕，滿足 xi 為xi+1的父結(jié)點(diǎn)則稱x0, x1,..., xn 為x到y(tǒng)的一條路徑，n稱為路徑長(zhǎng)度
結(jié)點(diǎn)的層數(shù)：
規(guī)定根的層數(shù)為0狡门，其余結(jié)點(diǎn)的層數(shù)等于其父結(jié)點(diǎn)的層數(shù)加一陷寝。
結(jié)點(diǎn)的度數(shù)(邊數(shù))：
結(jié)點(diǎn)的非空子樹(即后綴)個(gè)數(shù)叫作結(jié)點(diǎn)的度數(shù)。在二叉樹中其馏，結(jié)點(diǎn)的度數(shù)最大為2凤跑，即最多有兩條邊。 度數(shù) = 總結(jié)點(diǎn)數(shù) - 1
二叉樹的高度(深度)：
二叉樹中結(jié)點(diǎn)的最大層數(shù)稱為二叉樹的高度叛复。
樹葉仔引、分支結(jié)點(diǎn)：
左(右)子樹均為空二叉樹的結(jié)點(diǎn)稱為樹葉扔仓，否則稱為分支結(jié)點(diǎn)。
特殊二叉樹
滿二叉樹：
如果一顆二叉樹的任何結(jié)點(diǎn)或是樹葉咖耘，或有兩顆非空子樹翘簇，則稱為滿二叉樹，結(jié)點(diǎn)度數(shù)一定為0或者2.
完全二叉樹：
如果一顆二叉樹中儿倒，只有最下面兩層結(jié)點(diǎn)度數(shù)小于2版保，其余各層結(jié)點(diǎn)度數(shù)都等于2，并且最下面一層的結(jié)點(diǎn)都集中在該層最左邊的若干位置上夫否，則此二叉樹稱為完全二叉樹彻犁。
擴(kuò)充的二叉樹：
擴(kuò)充的二叉樹是對(duì)一個(gè)已有二叉樹的擴(kuò)充，擴(kuò)充后原二叉樹的結(jié)點(diǎn)都變?yōu)槎葦?shù)為2的分支結(jié)點(diǎn)慷吊。也就是說袖裕，如果結(jié)點(diǎn)的度數(shù)為2，則不變溉瓶，度數(shù)為1急鳄，則增加一個(gè)分支，度數(shù)為0則增加兩個(gè)分支堰酿。增加的結(jié)點(diǎn)稱為外部結(jié)點(diǎn)疾宏，原有的結(jié)點(diǎn)稱為內(nèi)部結(jié)點(diǎn)。
5.1.2 主要性質(zhì)
一般二叉樹的性質(zhì)
性質(zhì)1 在非空二叉樹的i層上触创，至多有2^i個(gè)結(jié)點(diǎn)(i >= 0)
性質(zhì)2 在高度為k的二叉樹上坎藐，最多有2^(k+1) - 1個(gè)結(jié)點(diǎn)(k >= 0)
性質(zhì)3 對(duì)于任意一顆非空的二叉樹，如果葉結(jié)點(diǎn)的個(gè)數(shù)為n0哼绑，度數(shù)為2的結(jié)點(diǎn)個(gè)數(shù)為n2岩馍，則 n0 = n2 + 1。
證明： B為邊的總數(shù)抖韩，n為結(jié)點(diǎn)總數(shù)蛀恩，則 n = n0 + n1 + n2, B = n - 1。 則 B = n0 * 0 + n1 * 1 + n2 * 2, 由此可以求得 n0 = n2 + 1茂浮。
完全二叉樹的性質(zhì)
性質(zhì)4 具有n個(gè)結(jié)點(diǎn)的完全二叉樹高度k為lgn
性質(zhì)5 對(duì)于具有n個(gè)結(jié)點(diǎn)的完全二叉樹双谆，如果按照以上(從根結(jié)點(diǎn))到下(葉結(jié)點(diǎn))和從左到右的順序?qū)Χ鏄渲械乃薪Y(jié)點(diǎn)從0開始到n-1進(jìn)行編號(hào)，則對(duì)于任意的下標(biāo)為i的結(jié)點(diǎn)席揽，有：
(1) 如果i = 0顽馋， 則它是根結(jié)點(diǎn)，如果i>0, 則它的父結(jié)點(diǎn)的下標(biāo)為 (i - 1) / 2
(2) 如果2i+1 <= n-1, 則下標(biāo)為i的結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的下標(biāo)為2i+1, 否則下標(biāo)為i的結(jié)點(diǎn)沒有左孩子結(jié)點(diǎn)
(3) 如果2i+2 <= N-1, 則下標(biāo)為i的結(jié)點(diǎn)的右孩子結(jié)點(diǎn)的下標(biāo)為2i+2幌羞，否則下標(biāo)為i的結(jié)點(diǎn)沒有右孩子結(jié)點(diǎn)
滿二叉樹性質(zhì)
性質(zhì)6 在滿二叉樹中寸谜，葉節(jié)點(diǎn)的個(gè)數(shù)比分支結(jié)點(diǎn)個(gè)數(shù)多1.
擴(kuò)充的二叉樹性質(zhì)
性質(zhì)7 在擴(kuò)充二叉樹中，外部結(jié)點(diǎn)的個(gè)數(shù)比內(nèi)部結(jié)點(diǎn)的個(gè)數(shù)多1新翎。這個(gè)由性質(zhì)6和內(nèi)外部結(jié)點(diǎn)的定義可以得到
性質(zhì)8 對(duì)任意擴(kuò)充的二叉樹程帕，外部路徑長(zhǎng)度E和內(nèi)部路徑長(zhǎng)度I之間滿足以下關(guān)系： E = I + 2n, 其中n是內(nèi)部結(jié)點(diǎn)的個(gè)數(shù)
5.1.3 抽象數(shù)據(jù)類型
假設(shè) BinTree 表示二叉樹類型住练，用BinTreeNode 表示二叉樹中結(jié)點(diǎn)的類型，作為抽象數(shù)據(jù)類型二叉樹可以提供的操作十分豐富愁拭。在ADT BinTree中讲逛，定義了最常見的操作如下：
ADT BinTree is
operations
// 創(chuàng)建一顆空的二叉樹
BinTree createEmptyBinTree(void);
// 返回一顆二叉樹，其根結(jié)點(diǎn)是root岭埠，左右二叉樹分別為left 和 right
BinTree consBinTree（BinTreeNode root, BinTree left, BinTree right);
// 判斷二叉樹是否為空
int isEmpty(BinTree tree);
// 返回二叉樹的根結(jié)點(diǎn)
BinTreeNode root(BinTree tree);
// 返回結(jié)點(diǎn)p的雙親結(jié)點(diǎn)
BinTree parent(BinTree tree, BinTreeNode p);
// 返回p結(jié)點(diǎn)的左子樹
BinTree leftChild(BinTree tree, BinTreeNode p);
// 返回p結(jié)點(diǎn)的右子樹
BinTree rightChild(BinTree tree, BinTreeNode p);
end ADT BinTree
5.2 二叉樹的遍歷
5.2.1 什么是遍歷盏混？
二叉樹的遍歷是一種按某種方式系統(tǒng)地訪問二叉樹中的所有結(jié)點(diǎn)的過程，使每個(gè)結(jié)點(diǎn)都被訪問一次且只被訪問一次惜论。
5.2.2 遍歷的分類
遍歷的方法尅分成兩類许赃，一類是廣度優(yōu)先遍歷，一類是深度優(yōu)先遍歷馆类。
深度優(yōu)先遍歷
二叉樹的遍歷有6種混聊，如果限定從左到右，則只能采用三種乾巧，即先根次序遍歷句喜、后根次序遍歷和中根次序遍歷。
先根次序 先訪問根沟于，然后先序遍歷左子樹咳胃，再先序遍歷右子樹
后根次序 先后序遍歷左子樹，然后后序遍歷右子樹旷太，再遍歷根
中根次序 先中序遍歷左子樹展懈，然后遍歷根，然后中序遍歷右子樹
廣度優(yōu)先遍歷
若二叉樹的高度為h供璧，則從0到h逐層如下處理：從左到右逐個(gè)訪問存在的結(jié)點(diǎn)
廣度優(yōu)先遍歷一顆二叉樹所得到的結(jié)點(diǎn)序列存崖，叫作這顆二叉樹的層次序列
5.2.3 一個(gè)例子 (略過)
5.2.4 遍歷的抽象算法
二叉樹的先序遍歷遞歸描述：
void preTreeWalk(BinTree tree) {
if (tree == NULL) {
return;
}
visit(root(tree));
preTreeWalk(leftChild(tree));
preTreeWalk(rightChild(tree));
}
二叉樹的先序遍歷非遞歸描述：
void iterativePreTreeWalk(BinTree tree) {
Stack s;
BinTreeNode *c;
if (tree == NULL) {
return;
}
s = createEmptyStack();
push(s, t);
while(!isEmptyStack(s)) {
c = top(s);
pop(s);
if (c != NULL) {
visit(root(c));
push(s, rightChild(c));
push(s, leftChild(c));
}
}
}
二叉樹的中序遍歷遞歸描述：
void inTreeWalk(BinTree tree) {
if (tree == NULL) {
return;
}
inTreeWalk(leftChild(tree));
visit(root(tree));
inTreeWalk(rightChild(tree));
}
二叉樹的中序遍歷非遞歸描述：
void iterativeInTreeWalk(BinTree tree) {
Stack s = createEmptyStack();
BinTree c = t;
if (c == NULL) {
return;
}
do {
while (c != NULL) {
push(s, c);
c = leftChild(c);
}
c = top(s);
pop(s);
visit(root(c));
c = rightChild(c);
} while (c != NULL || !isEmptyStack(s));
}
二叉樹的后序遍歷遞歸描述：
void postTreeWalk(BinTree tree) {
if (tree == NULL) {
retur;
}
postTreeWalk(leftChild(tree));
postTreeWalk(rightChild(tree));
visit(root(tree));
}
二叉樹的后序遍歷非遞歸描述：
void iterativePostTreeWalk(BinTree tree) {
Stack s = createEmptyStack();
BinTree pr;
BinTree p = tree;
while (p != NULL || !isEmptyStack(s)) {
// 將左子樹壓入棧中
while (p != NULL) {
push(s, p);
pr = rightChild(p);
p = leftChild(p);
if (p == NULL) {
p = pr;
}
}
// 從棧頂取出元素
p = top(s);
pop(s);
// 訪問元素
visit(root(p));
// 取得右子樹
if (!isEmptyStack(s) && leftChild(top(s)) == p) {
p = rightChild(top(s));
} else {
p = NULL;
}
}
}
廣度優(yōu)先遍歷二叉樹的偽代碼描述如下：
void levelTreeWalk(BinTree tree) {
BinTree c, cc
Queue q = createEmptyQueue();
if (tree == NULL) {
return;
}
c = tree;
enQueue(q,c)
while (!isEmptyQueue(q)) {
c = frontQueue(q);
deQueue(q);
visit(root(c));
cc = leftChild(c);
if (cc != NULL) {
enQueue(q, cc);
}
cc = rightChild(c);
if (cc != NULL) {
enQueue(q, cc);
}
}
}
5.3 二叉樹的實(shí)現(xiàn)
5.3.1 順序表示
二叉樹的順序表示，也是采用一組連續(xù)的存儲(chǔ)單元來存放二叉樹中的結(jié)點(diǎn)睡毒。對(duì)于完全二叉樹金句，只要通過數(shù)組下標(biāo)的關(guān)系，就可以確定結(jié)點(diǎn)之間的邏輯關(guān)系吕嘀，其他類型二叉樹無(wú)法根據(jù)存儲(chǔ)的先后順序確定
順序表示的二叉樹定義如下：
struct SeqBinTree {
int MAXIMUM; // 允許結(jié)點(diǎn)的最大個(gè)數(shù)
int n; // 改造成完全二叉樹后，結(jié)點(diǎn)的實(shí)際個(gè)數(shù)
DataType * nodelist; // 存放結(jié)點(diǎn)的數(shù)組
};
typedef struct SeqBinTree *PSeqBinTree; // 順序二叉樹的指針類型
運(yùn)算的實(shí)現(xiàn)
下標(biāo)為p的結(jié)點(diǎn)雙親結(jié)點(diǎn)的下標(biāo)：
int parent(PSeqBinTree tree, int p) {
if (p < 0 || p >= tree->n) {
return -1;
}
return (p - 1) / 2;
}
下標(biāo)為p的結(jié)點(diǎn)左孩子結(jié)點(diǎn)的下標(biāo)：
int leftChild(PSeqBinTree tree, int p) {
if (p < 0 || p >= tree-> n) {
return -1;
}
return 2 * p + 1;
}
下標(biāo)為p的結(jié)點(diǎn)左孩子結(jié)點(diǎn)的下標(biāo)：
int rightChild(PSeqBinTree tree, int p) {
if (p < 0 || p >= tree-> n) {
return -1;
}
return 2 * (p + 1);
}
顯然贞瞒，順序表示對(duì)完全二叉樹比較合適偶房，既可以節(jié)省空間，又可以利用數(shù)組元素的下標(biāo)確定結(jié)點(diǎn)在二叉樹中的位置以及結(jié)點(diǎn)之間的關(guān)系军浆。
5.3.2 鏈表表示
二叉樹的鏈表表示是用一個(gè)鏈表來存儲(chǔ)一顆二叉樹棕洋，二叉樹中的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)鏈表中的一個(gè)結(jié)點(diǎn)。
每個(gè)結(jié)點(diǎn)可以形象地描述為：
|left|right|info|
C語(yǔ)言描述如下：
typedef struct BinTreeNode {
DataType info;
struct BinTreeNode * left;
struct BinTreeNode * rightl
} BinTreeNode;
運(yùn)算的實(shí)現(xiàn)
返回p結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的指針：
BinTreeNode *leftChild(BinTreeNode *p) {
if (p == NULL) {
return NULL;
}
return p->left;
}
返回p結(jié)點(diǎn)的右孩子結(jié)點(diǎn)的指針：
BinTreeNode *rightChild(BinTreeNode *p) {
if (p == NULL) {
return NULL;
}
return p->right;
}
實(shí)現(xiàn)求雙親結(jié)點(diǎn)的操作比較困難乒融，需要從根結(jié)點(diǎn)出發(fā)查找當(dāng)前結(jié)點(diǎn)的位置掰盘。為了方便使用摄悯，可以增加一個(gè)雙親指針parent
5.3.3 線索二叉樹
線索二叉樹是對(duì)左-右指針表示法的一種修改
它利用空的左指針存儲(chǔ)該節(jié)點(diǎn)的某種遍歷序列前驅(qū)結(jié)點(diǎn)的位置，利用空的右指針在同種遍歷序列中的后繼結(jié)點(diǎn)的位置
這種附加的指向前驅(qū)和后繼結(jié)點(diǎn)額指針稱為線索愧捕。
為了區(qū)分左右指針和線索奢驯，需要在每個(gè)結(jié)點(diǎn)里面增加兩個(gè)標(biāo)志位ltag 和rtag，當(dāng)tag置為1時(shí)次绘，表示線索
用C語(yǔ)言表述如下：
typedef struct ThreadTreeNode {
DataType *info;
struct ThreadTreeNode * left;
struct ThreadTreeNode * right;
int ltag, rtag;
} ThreadTreeNode, ThreadTree;
中序線索化二叉樹：
void threadTree(ThreadTree *tree) {
// 創(chuàng)建一個(gè)M大小的空順序棧瘪阁，M一般為樹的高度
SeqStack *st = createEmptyStack(M);
ThreadTree *p, *pr;
if (tree == NULL) {
return;
}
p = tree;
pr = NULL;
do {
while (p != NULL) {
push(st, p);
p = p->left;
}
p = top(st);
pop(st);
if (pr != NULL) {
if (pr->right == NULL) {
pr->right = p;
pr->rtag = 1;
}
if (p->left == NULL) {
p->left = pr;
p->ltag = 1;
}
}
pr = p;
p = p->right;
} while (!isEmptyStack(st) || p != NULL);
}
構(gòu)造中序線索二叉樹的最大意義是：可以很方便地從中找到指定結(jié)點(diǎn)在中序序列中的前驅(qū)和后繼，而不必重新遍歷二叉樹
中序遍歷中序線索二叉樹：
void threadInTreeWalk(ThreadTree *tree) {
ThreadTree *p = tree;
if (tree == NULL) {
return;
}
while (p->left != NULL && p->ltag == 0) {
p = p->left;
}
while (p != NULL) {
visit(*p);
if (p->right != NULL && p->rtag == 0) {
p = p->right;
// 右子樹的左子樹一直向下
while (p->left != NULL && p->ltag == 0) {
p = p->left;
}
} else {
p = p->right;
}
}
}
5.4 二叉樹的應(yīng)用
5.4.1 堆與優(yōu)先隊(duì)列
首先給出堆得定義：n個(gè)元素的序列 K = (k0, k1,..., kn-1) 稱為堆邮偎，當(dāng)且僅當(dāng)滿足條件：
ki >= k(2i+1) && ki >= k(2i+2)
或者
ki <= k(2i+1) && ki <= k(2i+2)
這個(gè)特征稱為堆序性管跺。 如果堆根結(jié)點(diǎn)最小，則稱為小根堆禾进，根結(jié)點(diǎn)最大豁跑，則稱為大根堆
優(yōu)先隊(duì)列
優(yōu)先隊(duì)列是一種常見的抽象數(shù)據(jù)類型，跟普通的隊(duì)列不同泻云，不遵循“先進(jìn)先出”的原則艇拍，而遵循“最小元素先出”的原則。優(yōu)先隊(duì)列的基本操作有三種：
添加元素壶愤，找出做小元素和刪除優(yōu)先隊(duì)列中的最小元素
優(yōu)先隊(duì)列的抽象數(shù)據(jù)類型如下：
ADT PriorityQueue is
Operations
// 創(chuàng)建一個(gè)空的優(yōu)先隊(duì)列
PriorityQueue createEmptyPriQueue(void);
// 判斷隊(duì)列是否為空
int isEmpty(PriorityQueue s);
// 添加元素
void add(PriorityQueue s, DataType data);
// 返回最小元素
DataType min(PriorityQueue s);
// 刪除最小元素
void removeMin(PriorityQueue s);
end ADT PriorityQueue
在優(yōu)先隊(duì)列中找出最小元素并刪除：
DataType deleteMin(PriorityQueue pq) {
DataType result;
result = min(pq);
removeMin(pq);
return result;
}
優(yōu)先隊(duì)列的實(shí)現(xiàn)
(1) 存儲(chǔ)結(jié)構(gòu)
優(yōu)先隊(duì)列的定義與二叉樹的順序表示基本一樣：
typedef struct PriorityQueue {
int MAXNUM; // 堆中的元素個(gè)數(shù)上限
int n; // 堆中的實(shí)際元素個(gè)數(shù)
DataType *pq; //堆中元素的順序表示
} PriorityQueue;
(2) 操作的實(shí)現(xiàn)
向優(yōu)先隊(duì)列中插入一個(gè)元素：
void addHeap(PriorityQueue *queue, DataType x) {
int i;
if (queue->n >= MAXNUM - 1) {
printf("Full !\n");
return;
}
for (i = queue->n; i >0 && queue->pq[(i - 1) / 2] > x; i = (i - 1) / 2) {
queue->pq[i] = queue->pq[(i - 1) / 2];
}
queue->pq[queue->i] = x;
queue->n++;
}
從優(yōu)先隊(duì)列中刪除最小元素：
void removeMin(PriorityQueue *queue) {
int s;
if (isEmptyHeap(queue)) {
printf("Empty!\n");
return;
}
s = --queue->n;
queue->pq[0] = queue->pq[s];
sift(queue, s, 0);
}
把完全二叉樹從指定結(jié)點(diǎn)調(diào)整為堆：
void sift(PriorityQueue *queue, int size, int p) {
DataType temp;
int i, child;
temp = queue->pq[queue->p];
i = p;
child = 2 * i + 1;
while (child < size) {
if (child < size-1 && queue->pq[child].key >queue->pq[child + 1].key) {
child++;
}
if (temp.key > queue->pq[child].key) {
queue->pq[i] = queue->pq[child];
i = child;
child = 2 * i + 1;
} else {
break;
}
}
queue->pq[i] = temp;
}
5.4.2 哈夫曼樹及其應(yīng)用
若用E表示某擴(kuò)充二叉樹的外部路徑長(zhǎng)度淑倾，則有：
E = ∑li, i = 1 to m
其中l(wèi)i為從根到第i個(gè)外部結(jié)點(diǎn)的路徑長(zhǎng)度，m為外部結(jié)點(diǎn)的個(gè)數(shù)征椒。
設(shè)擴(kuò)充二叉樹具有m個(gè)帶有權(quán)值得外部結(jié)點(diǎn)娇哆，那么從根結(jié)點(diǎn)到外部結(jié)點(diǎn)的路徑長(zhǎng)度與相應(yīng)權(quán)值的乘積和，叫做擴(kuò)充二叉樹的帶權(quán)外部路徑：
WPL = ∑wili勃救，i = i to m
wi是第i個(gè)外部結(jié)點(diǎn)的權(quán)值
假設(shè)有一組(無(wú)序)實(shí)數(shù){w1,w2,w3,...,wm}, 現(xiàn)要構(gòu)造一顆以wi為權(quán)的m個(gè)外部結(jié)點(diǎn)的擴(kuò)充二叉樹碍讨，使得帶權(quán)的外部路徑長(zhǎng)度WPL最小，滿足這一要求的擴(kuò)充二叉樹就被稱作哈夫曼樹蒙秒，又稱最優(yōu)二叉樹勃黍。
例子：
給出帶權(quán)是{ 2,3,4,11 }, 可以構(gòu)造出不同的擴(kuò)充二叉樹，其中三種如下：
O O O
/ \ / \ / \
11 O O 2 O O
/ \ / \ / \ / \
4 O 3 O 2 11 3 4
/ \ / \
2 3 4 11
(a) (b) (c)
上面的帶權(quán)外部路徑長(zhǎng)度分別為：
(a) WPL = 1x11 + 2x4 + 3x2 + 3x3 = 34
(b) WPL = 1x2 + 2x3 + 3x4 + 3x11 = 53
(c) WPL = 2x2 + 2x11 + 2x3 + 2x4 = 40
由此可見晕讲，對(duì)于一組帶有確定權(quán)值的外部結(jié)點(diǎn)覆获，構(gòu)造出不同擴(kuò)充二叉樹，帶權(quán)外部路徑長(zhǎng)度并不相同瓢省。
哈夫曼樹的構(gòu)造
從上面的例子可以看出弄息，一棵擴(kuò)充二叉樹要使得WPL最小，必須使權(quán)值越大的外部結(jié)點(diǎn)離根越近勤婚，權(quán)值越小離根越遠(yuǎn)摹量。使用哈夫曼算法可以構(gòu)造一棵最優(yōu)二叉樹。
算法的基本思想：
(1) 由給定的m個(gè)權(quán)值{w1,w2,w3,...,wm}，構(gòu)造m棵由空二叉樹擴(kuò)充得到的擴(kuò)充二叉樹{T1,T2,...,Tm}缨称。每個(gè)Ti(1<= i <= m)只有一個(gè)外部結(jié)點(diǎn)凝果，其權(quán)值外wi.
(2) 在已經(jīng)構(gòu)造的所有擴(kuò)充二叉樹中，選取根結(jié)點(diǎn)的權(quán)值最小和次最小的兩棵睦尽，將其作為左器净、右子樹，構(gòu)造成一棵新的擴(kuò)充二叉樹骂删，根結(jié)點(diǎn)的權(quán)值置為左掌动、右子樹根結(jié)點(diǎn)權(quán)值之和
重復(fù)步驟(2)，每次都使擴(kuò)充二叉樹的個(gè)數(shù)減一宁玫，當(dāng)只剩一棵擴(kuò)充二叉樹時(shí)粗恢，它便是所要構(gòu)造的哈夫曼樹。
數(shù)據(jù)結(jié)構(gòu)：
C語(yǔ)言定義為：
typedef struct HTNode {
int wpl; // WPL權(quán)值
int parent; // 雙親結(jié)點(diǎn)下標(biāo)欧瘪，無(wú)則置為-1
int left; // 左孩子結(jié)點(diǎn)下標(biāo)眷射，無(wú)則置為-1
int right; // 右孩子結(jié)點(diǎn)下標(biāo)，無(wú)則置為-1
} HTNode;
typedef struct HTTree {
int m; // 外部結(jié)點(diǎn)個(gè)數(shù)
int root; // 根結(jié)點(diǎn)下標(biāo)
HTNode *hTree; // 存放 2xm-1個(gè)結(jié)點(diǎn)的數(shù)組
} HTTree;
哈夫曼算法：
HTTree *huffmanTree(int m, int *w) {
HTTree *pht;
int i, j, x1, x2, m1, m2;
pht = (HTTree *) malloc(sizeof(HTTree));
if (pht == NULL) {
printf("Out of space!\n");
return pht;
}
pht->hTree = (HTNode *) malloc(sizeof(HTNode));
// 設(shè)置數(shù)組初始值
for (i = 0; i <2 * m-1; i++) {
pht->hTree[i].left = -1;
pht->hTree[i].right = -1;
pht->hTree[i].parent = -1;
if (i < m) {
pht->hTree[i].wpl = w[i];
} else {
pht->hTree[i].wpl = -1;
}
}
for (i = 0; i < m - 1; i++) {
m1 = MAXINT; // 最小權(quán)值
m2 = MAXINT; // 次最小權(quán)值
x1 = -1; // 最小下標(biāo)
x2 = -1; // 次最小下標(biāo)
// 找出最小權(quán)的無(wú)雙親結(jié)點(diǎn)的結(jié)點(diǎn)
for (j = 0; j < m+i; j++) {
if (pht->hTree[j].wpl < m1 && pht->hTree[i].parent == -1) {
m2 = m1;
x2 = x1;
m1 = pht->hTree[j].wpl;
x1 = j; // x1存放最小權(quán)的無(wú)雙親結(jié)點(diǎn)的結(jié)點(diǎn)下標(biāo)
} else if (pht->hTree[j].wpl < m2 && pht->hTree[j].parent == -1) {
m2 = pht->hTree[j].wpl;
x2 = j; // x2存放次最小權(quán)的無(wú)雙親結(jié)點(diǎn)的結(jié)點(diǎn)下標(biāo)
}
}
// 構(gòu)造內(nèi)部結(jié)點(diǎn)
pht->hTree[x1].parent = m + i;
pht->hTree[x2].parent = m + i;
pht->hTree[m+i].wpl = m1 + m2;
pht->hTree[m+i].left = x1;
pht->hTree[m+i].right = x2;
}
// 根結(jié)點(diǎn)的位置
pht->root = 2 * m - 2佛掖；
return pht;
}
哈夫曼編碼：
設(shè)
d = {d1,d2,...,dn}為需要編碼的字符集合
w = {w1,w2,...,wn}為d中各個(gè)字符出現(xiàn)的概率
現(xiàn)要對(duì)d進(jìn)行二進(jìn)制編碼妖碉，使得：
(1) 按給出的編碼傳輸文件時(shí)，通訊編碼總長(zhǎng)最短
(2) 若di != dj芥被，則di的編碼不可能是dj編碼的開始部分(前綴)
滿足上述要求額二進(jìn)制編碼稱為最優(yōu)前綴編碼
最優(yōu)前綴編碼(哈夫曼編碼)可以用哈夫曼樹來實(shí)現(xiàn)：
d1,d2,..,dn作為外部結(jié)點(diǎn)欧宜，w1,w2,...,wn作為外部結(jié)點(diǎn)的權(quán)值，構(gòu)建哈夫曼樹拴魄。在哈夫曼樹中冗茸，把從每個(gè)結(jié)點(diǎn)的指向左孩子結(jié)點(diǎn)的邊標(biāo)上二進(jìn)制數(shù)"0"，指向右孩子的邊標(biāo)上二進(jìn)制數(shù)"1"匹中。從根到每個(gè)葉結(jié)點(diǎn)路徑上的二進(jìn)制數(shù)連接起來夏漱，就是這個(gè)葉節(jié)點(diǎn)所代表的最優(yōu)前綴編碼。這種編碼叫作哈夫曼編碼顶捷。
編碼的結(jié)果是挂绰，出現(xiàn)概率大的字符其編碼較短，出現(xiàn)概率小的字符其編碼較長(zhǎng)服赎。
解碼時(shí)葵蒂，從二叉樹的根結(jié)點(diǎn)開始，用需要編碼的二進(jìn)制位串重虑，從頭開始與二叉樹根結(jié)點(diǎn)到子結(jié)點(diǎn)邊上標(biāo)的0刹勃、1相匹配，確定一條到達(dá)樹葉結(jié)點(diǎn)的路徑嚎尤，一旦到達(dá)樹葉結(jié)點(diǎn)，則譯出一個(gè)字符伍宦，然后再回到根結(jié)點(diǎn)芽死，從二進(jìn)制位串中的下一位開始繼續(xù)解碼乏梁。
5.5 樹及其抽象數(shù)據(jù)類型
樹形結(jié)構(gòu)在客觀世界是大量存在的。一棵樹幾種不同的表現(xiàn)形式：樹形关贵、文氏圖遇骑、凹入表、嵌套括號(hào)
5.5.1 基本概念
樹氏包含 n(n>=0) 個(gè)結(jié)點(diǎn)的有窮集合T揖曾，當(dāng)T非空時(shí)滿足：
(1) 有且僅有一個(gè)特別標(biāo)出的稱作根的結(jié)點(diǎn)
(2) 除了根結(jié)點(diǎn)外落萎，其余結(jié)點(diǎn)分別為若干個(gè)不相交的非空集合T1,T2,...,Tm，這些集合中的每一個(gè)又都是樹炭剪。樹T1,T2,...,Tm稱作這個(gè)根結(jié)點(diǎn)的子樹
只包括一個(gè)結(jié)點(diǎn)的樹是僅由根結(jié)點(diǎn)構(gòu)成练链。不包含任何結(jié)點(diǎn)的樹稱作空樹。
樹中的一個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)個(gè)數(shù)叫作這個(gè)結(jié)點(diǎn)的度數(shù)奴拦。其中度數(shù)最大的結(jié)點(diǎn)的度數(shù)叫作樹的度數(shù)媒鼓。
對(duì)于子樹的次序不加區(qū)別的樹叫作無(wú)序樹，對(duì)于子樹之間的次序加以區(qū)別的樹叫作有序樹错妖。
5.5.2 抽象數(shù)據(jù)類型
樹型結(jié)構(gòu)的抽象數(shù)據(jù)結(jié)構(gòu)如下：
ADT Tree is
Operations
// 創(chuàng)建一棵空樹
Tree createEmptyTree(void)
// 以p為根绿鸣，t1,...,ti為子樹創(chuàng)建一顆樹
Tree consTree(Node p, Tree t1, ... Tree ti)
// 判斷樹是否為空
int isEmpty(Tree t)
// 父結(jié)點(diǎn)
Node parent(Node p)
// 左孩子結(jié)點(diǎn)
Tree leftChild(Tree t)
// 右兄弟樹
Tree rightSibling(Tree t);
end ADT Tree
5.5.3 樹的遍歷
樹的遍歷是一種按某種方式系統(tǒng)地訪問樹中的所有結(jié)點(diǎn)的過程，它使每個(gè)結(jié)點(diǎn)都被訪問一次并且只訪問一次暂氯。
深度優(yōu)先遍歷
先序遍歷 —— 首先訪問根結(jié)點(diǎn)潮模，然后從左到右按先序遍歷根結(jié)點(diǎn)的每棵子樹
后序遍歷 —— 首先從左到右按后序遍歷根結(jié)點(diǎn)的每棵子樹，最后訪問根結(jié)點(diǎn)
先序遍歷的遞歸算法：
void preTreeWalk(Tree *tree) {
Tree *subTree;
if (tree == NULL) {
return;
}
visit(root(tree));
subTree = leftChild(tree);
while (subTree != NULL) {
preTreeWalk(subTree);
subTree = rightSibling(subTree);
}
}
先序遍歷的非遞歸算法：
void iterativeTreeWalk(Tree *tree) {
Tree *subTree = tree;
Stack *s = createEmptyStack();
do {
while (subTree != NULL) {
visit(root(subTree));
push(s, subTree);
subTree = leftChild(subTree);
}
while ((subTree == NULL) && !isEmptyStack(s)) {
subTree = rightSibling(top(s));
pop(s);
}
} while (subTree != NULL);
}
后序遍歷的遞歸算法：
void postTreeWalk(Tree *tree) {
Tree *subTree;
if (tree == NULL) {
return;
}
subTree = leftChild(tree);
while(subTree != NULL) {
postTreeWalk(subTree);
subTree = rightSibling(subTree);
visit(root(tree));
}
}
廣度優(yōu)先遍歷算法：
void levelTreeWalk(Tree *tree) {
Tree *subTree;
Queue *queue;
queue = createEmptyQueue();
subTree = tree;
if (subTree == NULL) {
return;
}
// 將子樹入隊(duì)
enQueue(queue, subTree);
while (!isEmptyQueue(queue)) {
// 不斷從隊(duì)列中取出子樹
subTree = frontQueue(queue);
deQueue(queue);
// 訪問子樹的根結(jié)點(diǎn)
visit(root(subTree));
// 找到長(zhǎng)子
subTree = leftChild(subTree);
while (c != NULL) {
// 子樹入隊(duì)
enQueue(queue, subTree);
// 找到當(dāng)前子樹的右兄弟子樹入隊(duì)
subTree = rightSibling(subTree);
}
}
}
5.6 樹的實(shí)現(xiàn)
5.6.1 父指針表示法
用一組連續(xù)的存儲(chǔ)空間痴施，存儲(chǔ)樹中的各個(gè)結(jié)點(diǎn)擎厢，數(shù)組中的一個(gè)元素為一個(gè)結(jié)構(gòu)，其中包含結(jié)點(diǎn)本身的信息以及本結(jié)點(diǎn)的父結(jié)點(diǎn)在數(shù)組中的下標(biāo)晾剖，樹的這種存儲(chǔ)放方法稱為父指針表示法锉矢。
結(jié)構(gòu)體定義如下：
struct ParTreeNode{
DataType info;
int parent;
};
樹的定義如下：
typedef struct ParTree {
int MAXNUM;
int n;
ParTreeNode *nodeList;
} ParTree;
求兄弟結(jié)點(diǎn)的位置：
int rightSibling(ParTree *tree, int p) {
int i;
if ( p >= 0 && p < tree->n) {
for (i = p + 1; i < tree->n; i++) {
if (tree->nodeList[i].parent == tree->nodeList[p].parent) {
return i;
}
}
}
return -1;
}
求左孩子結(jié)點(diǎn)的位置：
int leftChild(ParTree *tree, int p) {
if (tree->nodeList[p + 1].parent == p) {
return p + 1;
} else {
return -1;
}
}
父指針表示法比較節(jié)省存儲(chǔ)空間，但求某個(gè)結(jié)點(diǎn)的兄弟運(yùn)算比較慢齿尽。
5.6.2 子表表示法
重要而常用的表示方法沽损。把整棵樹表示成一個(gè)結(jié)點(diǎn)表，而結(jié)點(diǎn)表中的每個(gè)元素又包含一個(gè)表循头，它記錄了這個(gè)結(jié)點(diǎn)的所有子結(jié)點(diǎn)的位置绵估，稱為子表。結(jié)點(diǎn)表的長(zhǎng)度即樹中結(jié)點(diǎn)的個(gè)數(shù)們一般用一維數(shù)組順序存儲(chǔ)卡骂。
子表表示法定義如下：
typedef struct EdgeNode {
int nodePosition;
struct EdgeNode *link;
} EdgeNode;
結(jié)點(diǎn)表中每個(gè)結(jié)點(diǎn)定義如下：
typedef struct ChildTreeNode {
DataType info;
EdgeNode *children;
} ChildTreeNode;
子表表示的樹結(jié)構(gòu)定義如下：
typedef struct ChildTree {
int MAXNUM;
int n;
ChildTreeNode *nodeList;
} ChildTree;
求右兄弟結(jié)點(diǎn)的位置:
int rightSibling(ChildTree *tree, int p) {
int i;
EdgeNode *v;
for (i = 0; i < tree->n; i++) {
v = tree->nodeList[i].children;
while (v != NULL) {
if (v->nodePosition == p) {
if (v->link == NULL) {
return -1;
} else {
return v->link->nodePosition;
}
} else {
v = v->link;
}
}
}
return -1;
}
求父結(jié)點(diǎn)的位置:
int parent(ChildTree *tree, int p) {
int i;
EdgeNode *v;
for (i = 0; i < tree->n; i++) {
v = tree->nodeList[i].children;
while (v != NULL) {
if (v->nodePosition == p) {
return i;
} else {
v = v->link;
}
}
}
return -1;
}
5.6.3 長(zhǎng)子-兄弟表示法
這種表示法是在樹中的每個(gè)結(jié)點(diǎn)中除其信息域国裳，再增加一個(gè)紙箱其最左子結(jié)點(diǎn)的指針域lChild和指向其右兄弟指針域rSibling
結(jié)點(diǎn)定義如下：
typedef struct CSNode {
DataType info;
struct CSNode *lchild;
struct CSNode *rsibing;
} CSNode;
5.6.4 樹的其他表示法
除了前面介紹的各種表示方法以外，樹還有帶右兄弟指針和子結(jié)點(diǎn)標(biāo)記的先根次序表示法全跨、帶有右兄弟和子結(jié)點(diǎn)雙標(biāo)記的先根次序表示法缝左、帶長(zhǎng)子指針和右兄弟標(biāo)記的層次次序表示法以及帶度數(shù)的后根次序表示法等
5.7 樹林
樹林是由零個(gè)或多個(gè)不相交的樹所組成的集合。樹林中的樹也是有序的，彼此稱為兄弟渺杉。這里的樹林可以是一個(gè)空集蛇数，也可以由一棵樹構(gòu)成。
5.7.1 樹林的遍歷
先根次序遍歷 —— 首先訪問樹林中第一棵樹的根結(jié)點(diǎn)是越，然后先根次序遍歷第一棵樹除去根結(jié)點(diǎn)剩下的所有子樹構(gòu)成的樹林耳舅，最后先根次序遍歷除去第一棵樹之后剩下的樹林
后根次序遍歷 —— 首先后根次序遍歷第一棵樹的根結(jié)點(diǎn)的所有子樹構(gòu)成的樹林，然后訪問樹林中第一棵樹的根結(jié)點(diǎn)倚评，最后后根次序遍歷除去第一棵樹之后剩下的樹林
5.7.2 樹林的存儲(chǔ)表示
所有樹的表示方法都可以推廣到樹林的表示浦徊。
5.7.3 樹林與二叉樹的轉(zhuǎn)換
在樹林(包括樹)與二叉樹之間有一個(gè)自然的一一對(duì)應(yīng)關(guān)系。任何樹都唯一地對(duì)應(yīng)到一棵二叉樹天梧。反過來也成立盔性。
樹林轉(zhuǎn)為二叉樹
步驟如下：
首先在所有相鄰的兄弟結(jié)點(diǎn)之間加一條線
然后對(duì)每個(gè)非終端結(jié)點(diǎn)，只保留它的其最左子結(jié)點(diǎn)的連線腿倚，刪去其他孩子結(jié)點(diǎn)之間原有的連線纯出。
最后以根結(jié)點(diǎn)為軸心，將整棵樹順時(shí)針旋轉(zhuǎn)一定角度敷燎，使其層次分明
二叉樹轉(zhuǎn)為樹林
步驟如下：
(1) 若某結(jié)點(diǎn)是其父母的左子結(jié)點(diǎn)暂筝，則把該結(jié)點(diǎn)的右結(jié)子結(jié)點(diǎn)遞歸用虛線連起來
(2) 去掉原二叉樹中所有父母到右子結(jié)點(diǎn)的連線。
