第六章樹和二叉樹

6.1樹的定義和基本術語

6.2二叉樹

6.3遍歷二叉樹和線索二叉樹

6.4樹和森林

6.6赫夫曼樹及其應用UNIX文件系統的系統結構圖/(root)binlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp一、樹的定義

樹是由n(n

0)個結點組成的有限集合。如果n=0，稱為空樹；如果n>0，則

有一個特定的稱之為根(root)的結點，它只有直接后繼，沒有直接前驅；

除根以外的其它結點劃分為m(m

0)個互不相交的有限集合T0,T1,…,Tm-1，每個集合又是一棵樹，并且稱之為根的子樹(subTree)。

6.1樹的定義和基本術語樹二叉樹1413121112345678910987456231二、樹的基本概念A為“根”T1、T2和T3都是一棵樹，稱為A的子樹。稱根和子樹根之間的連線為“分支”（P120)結點分支的個數定義為“結點的度”，如結點B的度為2，D的度為3。樹中所有結點度的最大值定義為“樹的度”。稱度為零的結點為“葉子” 或“終端結點”所有度不為零的結點 被稱作"分支結點"

二、樹的基本概念樹的深度定義為樹中葉子結點所在最大層次數。稱根結點為子樹根的"雙親"。稱子樹根為根結點的"孩子“根的所有子樹根互為“兄弟”。有序樹、無序樹如果樹中每棵子樹從左向右的排列擁有一定的順序，不得互換，則稱為有序樹，否則稱為無序樹。森林為m(m≥0)棵互不相交的樹的集合。(F=(T1,T2,..Tm)

樹和線性結構對照：三、樹的抽象數據類型

ADTTree{

數據對象：D是具有相同特性的數據元素的集合。

數據關系：

若D為空集，則稱為空樹；

若D中僅含一個數據元素，則關系R為空集；

否則R={H}，

(1)

在D中存在唯一的稱為根的數據元素root，它在關系H下無前驅；

(2)

當n>1時，其余數據元素可分為m(m>0)個互不相交的(非空)有限集T1,T2,…,Tm,其中每一個子集本身又是一棵符合本定義的樹，稱為根root的子樹，每一棵子樹的根xi都是根root的后繼，即<root,xi>H,i=1,2,…,m。基本操作：

{結構初始化}

InitTree(&T);

操作結果：構造空樹T。

CreateTree(&T,definition);

初始條件：definition給出樹T的定義。

操作結果：按definition構造樹T。

{銷毀結構}

DestroyTree(&T);

初始條件：樹T存在。

操作結果：銷毀樹T。{引用型操作}

TreeEmpty(T);

初始條件：樹T存在。

操作結果：若T為空樹，則返回TRUE，否則返回FALSE。

TreeDepth(T);

初始條件：樹T存在。

操作結果：返回T的深度。

Root(T);

初始條件：樹T存在。

操作結果：返回T的根。

Value(T,cur_e);

初始條件：樹T存在，cur_e是T中某個結點。

操作結果：返回cur_e的值。Parent(T,cur_e);

初始條件：樹T存在，cur_e是T中某個結點。

操作結果：若cur_e是T的非根結點，則返回它的雙親，否則返回"空"。

LeftChild(T,cur_e);

初始條件：樹T存在，cur_e是T中某個結點。

操作結果：若cur_e是T的非葉子結點，則返回它的最左孩子，否則返回"空"。

RightSibling(T,cur_e);

初始條件：樹T存在，cur_e是T中某個結點。

操作結果：若cur_e有右兄弟，則返回它的右兄弟，否則返回"空"。

TraverseTree(T,visit());

初始條件：樹T存在，visit是對結點操作的應用函數。

操作結果：按某種次序對T的每個結點調用函數visit()一次且至多一次。一旦visit()失敗，則操作失敗。

{加工型操作}

Assign(T,cur_e,value);

初始條件：樹T存在，cur_e是T中某個結點。

操作結果：結點cur_e賦值為value。

ClearTree(&T);

初始條件：樹T存在。

操作結果：將樹T清為空樹。

InsertChild(&T,&p,i,c);

初始條件：樹T存在，p指向T中某個結點，1≤i≤p所指結點的度＋1，非空樹c與T不相交。

操作結果：插入c為T中p所指結點的第i棵子樹。

DeleteChild(&T,&p,i);

初始條件：樹T存在，p指向T中某個結點，1≤i≤p指結點的度。

操作結果：刪除T中p所指結點的第i棵子樹。

}ADTTree

四、樹的應用--例：算術表達式的樹結構表示(l)表達式中的每一個運算符在樹中對應一個結點,稱為運算符結點。(2)運算符的每一個運算對象在樹中為該運算符結點的子樹，遵從從左到右的順序(3)運算對象中的單變量均為葉子結點。

a*(b+c/d)+e*h-g*f(s,t,x+y)a*(b+c/d)+e*h-g*f(s,t,x+y)定義：二叉樹是另一種樹形結構。它與樹形結構的區別是：（1）每個結點最多有兩棵子樹；（2）子樹有左右之分。二叉樹也可以用遞歸的形式定義。即：二叉樹是n（n≥0）個結點的有限集合。當n=0時，稱為空二叉樹；當n>0時，有且僅有一個結點為二叉樹的根，其余結點被分成兩個互不相交的子集，一個作為左子集，另一個作為右子集，每個子集又是一個二叉樹。6.2二叉樹(BinaryTree)二叉樹的5種形態：?(a)(b)(c)(d)(e)二叉樹的抽象數據類型定義ADTBinaryTree{

數據對象：D是具有相同特性的數據元素的集合。

數據關系：

若D為空集，稱BinaryTree為空二叉樹；

否則關系R={H}：

(1)在D中存在唯一的稱為根的數據元素root，它在關系H下無前驅；

(2)D中其余元素必可分為兩個互不相交的子集

L和R，每一個子集都是一棵符合本定義的二叉樹，并分別為root的左子樹和右子樹。如果左子樹L不空，則必存在一個根結點，它是root的"左后繼"(<root,>∈H)，如果右子樹R不空，則必存在一個根結點為root的"右后繼"(<root,>∈H)。基本操作P：

{結構初始化}

InitBiTree(&T);

操作結果：構造空二叉樹T。

CreateBiTree(&T,definition);

初始條件：definition給出二叉樹T的定義。

操作結果：按definition構造二叉樹T。

{銷毀結構}

DestroyBiTree(&T);

初始條件：二叉樹T存在。

操作結果：銷毀二叉樹T。{引用型操作}

BiTreeEmpty(T);

初始條件：二叉樹T存在。

操作結果：若T為空二叉樹，則返回TRUE，否則返回FALSE。

BiTreeDepth(T);

初始條件：二叉樹T存在。

操作結果：返回T的深度。

Root(T);

初始條件：二叉樹T存在。

操作結果：返回T的根。

Value(T,e);

初始條件：二叉樹T存在，e是T中某個結點。

操作結果：返回e的值。Parent(T,e);

初始條件：二叉樹T存在，e是T中某個結點。

操作結果：若e是T的非根結點，則返回它的雙親，否則返回"空"。

LeftChild(T,e);

初始條件：二叉樹T存在，e是T中某個結點。

操作結果：返回e的左孩子。若e無左孩子，則返回"空"。

RightChild(T,e);

初始條件：二叉樹T存在，e是T中某個結點。

操作結果：返回e的右孩子。若e無右孩子，則返回"空"。

LeftSibling(T,e);

初始條件：二叉樹T存在，e是T中某個結點。

操作結果：返回e的左兄弟。若e是其雙親的左孩子或無左兄弟，則返回"空"。RightSibling(T,e);

初始條件：二叉樹T存在，e是T的結點。

操作結果：返回e的右兄弟。若e是其雙親的右孩子或無右兄弟，則返回"空"。

PreOrderTraverse(T,visit());

初始條件：二叉樹T存在,visit是對結點操作的應用函數。

操作結果：先序遍歷

T，對每個結點調用函數visit一次且僅一次。一旦visit()失敗，則操作失敗。

InOrderTraverse(T,vsit());

初始條件：二叉樹T存在，visit是對結點操作的應用函數。

操作結果：中序遍歷

T，對每個結點調用函數Visit一次且僅一次。一旦visit()失敗，則操作失敗。

PostOrderTraverse(T,visit());

初始條件：二叉樹T存在，visit是對結點操作的應用函數。

操作結果：后序遍歷

T，對每個結點調用函數visit一次且僅一次。一旦visit()失敗，則操作失敗。LevelOrderTraverse(T,visit());

初始條件：二叉樹T存在，visit是對結點操作的應用函數。

操作結果：層序遍歷

T，對每個結點調用函數visit一次且僅一次。一旦visit()失敗，則操作失敗。

{加工型操作}

ClearBiTree(&T);

初始條件：二叉樹T存在。

操作結果：將二叉樹T清為空樹。

Assign(&T,&e,value);

初始條件：二叉樹T存在，e是T中某個結點。

操作結果：結點e賦值為value。InsertChild(&T,p,LR,c);

初始條件：二叉樹T存在，p指向T中某個結點，LR為0或1，非空二叉樹c與T不相交且右子樹為空。

操作結果：根據LR為0或1，插入c為T中p所指結點的左或右子樹。p所指結點原有左或右子樹成為c的右子樹。

DeleteChild(&T,p,LR);

初始條件：二叉樹T存在，p指向T中某個結點，LR為0或1。

操作結果：根據LR為0或1，刪除T中p所指結點的左或右子樹。

}ADTBinaryTree

性質1

若二叉樹的層次從1開始,則在二叉樹的第i層最多有2i-1個結點。(i

1)

[證明用數學歸納法]性質2

深度為k的二叉樹最多有2k-1個結點。(k0)

[證明用求等比數列前k項和的公式]性質3

對任何一棵二叉樹,如果其葉結點個數為n0,度為2的非葉結點個數為n2,則有

n0＝n2＋1二、二叉樹的性質證明：若設度為1，2的結點有n1，n2

個，總結點個數為n，總邊數為e，則:

n=n0+n1+n2

e=n–1（邊）=2n2+n1（度）

因此，2n2+n1＋1

=n0+n1+n2n0=n2+1

1413121112456810定義1

滿二叉樹(FullBinaryTree)

除最后一層外,每一層上的所有結點都有兩個子結點。定義2

完全二叉樹(CompleteBinaryTree)

除最后一層外，其它各層的結點數都達到最大個數，最后一層可缺若干結點，但需從右向左連續缺。三、滿二叉樹與完全二叉樹性質1

具有

n

個結點的完全二叉樹的高度為

[log2n]+1性質2

將一棵有n個結點的完全二叉樹自頂向下，同一層自左向右連續給結點編號1,2,…,n，然后按此結點編號將樹中各結點順序地存放于一個一維數組中,并簡稱編號為i的結點為結點i(0<i

n)。則有以下關系：

若i==1,則i無雙親，即為根結點。若i>1,則i的雙親為[i/2]

若2*i<n,則i的左子女為2*i

若2*i+1<n,則i的右子女為2*i+112

81234567131415

910111、順序存儲結構二叉樹的順序存儲結構的定義如下：constMAXSIZE=100;//暫定二叉樹中結點數的最大值為100

typedefstruct{

ElemType*data;

//存儲空間基址(初始化時分配空間)

intnodeNum;

//二叉樹中結點數

}SqBiTree;

//二叉樹的順序存儲結構

四、二叉樹的存儲結構完全二叉樹的順序存儲表示一般二叉樹的順序存儲表示順序存儲結構實例

單支樹由于一般二叉樹必須仿照完全二叉樹那樣存儲，可能會浪費很多存儲空間，單支樹就是一個極端情況。2鏈式存儲結構二叉樹的二叉鏈表存儲表示typedefstructBiTNode{

ElemTypedata;

structBiTNode*Lchild,*Rchild;//左、右孩子指針

}*BiTree;二叉樹的三叉鏈表存儲表示

typedefstructTriTNode{

ElemTypedata;

structBiTNode*Lchild,*Rchild;//左、右孩子指針

structBiTNode*parent;

//雙親指針

}*TriTree;

二叉樹的雙親鏈表存儲表示

typedefstructBPTNode{

//結點結構

ElemTypedata;

intparent;

//指向雙親的指針

charLRTag;

//左、右孩子標志域

}BPTNode6.3遍歷二叉樹和線索二叉樹

一、遍歷二叉樹

所謂樹的遍歷，就是按某種次序訪問樹中的結點，要求每個結點訪問一次且僅訪問一次。 由于二叉樹中每個結點都有兩個后繼，則可以有三條搜索路徑：

1)先左(子樹)后右(子樹)；

2)先右(子樹)后左(子樹)；

3)按層次從上到下。

限定先左后右的遍歷前序遍歷(PreorderTraversal)算法框架:若二叉樹為空，則空操作；否則訪問根結點(V)；前序遍歷左子樹(L)；前序遍歷右子樹(R)。遍歷結果-+a*b-cd/ef先序遍歷遞歸算法voidPreOrder(BTreeBT){if(BT){Visit(BT);PreOrder(BT->Lchild);PreOrder(BT->Rchild);}}先序遍歷算法框架：若二叉樹為空，則空操作；否則中序遍歷左子樹(L)；訪問根結點(V)；中序遍歷右子樹(R)。遍歷結果

a+b*c-d-e/f中序遍歷(InorderTraversal)中序遍歷遞歸算法voidInOrder(BTreeBT){if(BT){InOrder(BT->Lchild);Visit(BT);InOrder(BT->Rchild);}}中序遍歷后序遍歷(PostorderTraversal)算法框架:若二叉樹為空，則空操作；否則后序遍歷左子樹(L)；后序遍歷右子樹(R)；訪問根結點(V)。遍歷結果abcd-*+ef/-后序遍歷遞歸算法voidPostOrder(BTreeBT){if(BT){PostOrder(BT->Lchild);PostOrder(BT->Rchild);Visit(BT);}}后序遍歷GHDEFBCA先序序列： ABDGCEFH 中序序列： DGBAECHF 后序序列： GDBEHFCA 建立二叉樹

voidCreateBiTree(BiTree&T)

{

//在先序遍歷二叉樹的過程中輸入二叉樹的“先序字符串”，

//建立根指針為T的二叉鏈表存儲結構。在先序字符串中，

//字符‘#’表示空樹，其它字母字符為結點的數據元素

cin>>ch；

if(ch==‘#’)T=NULL;

else{

T=newBiTNode;

T->data=ch;

CreateBiTree(T->Lchild);

CreateBiTree(T->Rchild);

}

}6-4-6.swf二叉樹遍歷的應用--計算二叉樹葉結點數目

可以使用三種遍歷順序的任何一種，只需將訪問操作改成判斷是否為葉結點。利用中序遍歷實現：voidLeaf(structBTree*BT,int&count){if(BT！＝NULL){Leaf(BT->Child,count);//計算左子樹的葉子結點個數

if(BT->LChild==NULL&&BT->RChild==NULL)count++;Leaf(BT->RChild,count);//計算右子樹的葉子結點個數

}}二叉樹遍歷的應用－－計算二叉樹的高度使用后序遍歷比較符合人們求解二叉樹高度的思維方式。首先分別求出左右子樹的高度，在此基礎上得出該棵樹的高度，即左右子樹較大的高度值加1。inthight(structBTree*BT){//h1和h2分別是以BT為根的左右子樹的高度

if(BT==NULL)return0;else{h1=hight(BT->lChild);h2=hight(BT->right);returnmax{h1,h2}+1;}}中序遍歷（非遞歸）StatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){ InitStack(S); Push(S,T); //根入棧

while(!StackEmpty(S)) { while(GetTop(S,p)&&p) Push(S,p->lchild); //向左到盡頭

Pop(S,p); //空指針出棧

if(!StackEmpty(S)) //訪問，向右

{ Pop(S,p); if(!Visit(p->data))returnERROR; Push(S,p->rchild); } } returnOK;}二、線索二叉樹將在二叉樹中每個結點（除第一個和最后一個外）的直接前驅和直接后繼保存起來。這種信息是在遍歷的動態過程中產生的，如果將這些信息在第一次遍歷時就保存起來，則在以后再次需要對二叉樹進行“遍歷”時就可以將二叉樹視作線性結構進行訪問操作了。樹結構存儲占用個數：n-1余：2n-(n-1)=n+1ACBDEF指針個數：2n存在問題？ACBDEF無法區分結構指針和線索指針。通過增加指針類型標識變量，標識指針是否為線索？typedefenumPointerType{Link=0,Thread=1};

//定義指針類型，以Link表示指針，Thread表示線索

typedefstructBiThrNode{

ElemTypedata;

structBiThrNode*Lchild,*Rchild;//左右指針

PointerTypeLTag,RTag;//左右指針類型標志

}*BiThrTree;在線索鏈表中添加了一個"頭結點"，頭結點的左指針指向二叉樹的根結點，其右線索指向中序序列中的最后一個結點

(2)若當前訪問到的結點的左指針為空,則將上次訪問結點地址填人,并置當前訪問到的結點的左標志域為l。中序遍歷二叉樹線索化以中序遍歷線索化為例：在中序遍歷過程中,將訪問根結點用以下操作代替:(l)若上次訪問到的結點的右指針為空,則將當前訪問結點地址填入,并置上次訪問到的結點右標志域為l;二叉線索鏈表的生成

voidInOrderThreading(BiThrTree&Th,BiThrTreeBT)

{

//BT為指向二叉樹根結點的指針，由此二叉鏈表建立二叉樹的中序線索鏈表，Thead指向線索鏈表中的頭結點。

BiThrTreepre;//注意該變量的作用

if(!(Th=newBiThrNode))exit(1);//存儲分配失敗

Th->LTag=Link;Th->RTag=Thread;

//建頭結點

Th->Rchild=Th;

//右指針回指

if(!BT)Th->Lchild=Th;

//若二叉樹空，則左指針回指

else{

Th->Lchild=BT;pre=Th;

InThreading(BT,pre);

//中序遍歷進行中序線索化

pre->Rchild=Th;pre->RTag=Thead;//對中序序列中最后一個結點進行線索化

Th->Rchild=pre;

//建非空樹的頭結點的“右線索”

}

}中序遍歷二叉樹線索化voidInThreading(BiThrTreep，BiThrTree&pre)

{

//對p指向根結點的二叉樹進行中序遍歷，遍歷過程中進行“中序線索化”。若pre所指結點的右指針為空，則將它改為“右線索”。若p所指結點的左指針為空，則將它改為“左線索”，指針pre在遍歷過程中緊隨其后，即始終指向p所指結點在中序序列中的前驅。

if(p){

InThreading(p->Lchild,pre);

//對左子樹進行線索化

if(!pre->Rchild)

{pre->RTag=Thread;pre->Rchild=p;}//建后繼線索if(!p->Lchild)

{p->LTag=Thread;p->Lchild=pre;}//建前驅線索

pre=p;

//保持pre指向p的前驅

InThreading(p->Rchild,pre);

//對右子樹進行線索化

}

}若當前結點的右指標值為0，則沿右子樹的左鏈進行搜索，直到發現某結點的左標志值為l且其左指針值不空為止，該結點即為當前結點的后件。線索二叉樹的遍歷-以中序遍歷為例

從根結點開始,沿左鏈找到葉子結點,為中序遍歷的第一個結點。

從該結點開始掃描,依次找出中序序列的后件，其規則如下:若當前結點的右標志值為l,則其右指針值為其后件的存儲地址;線索二叉樹遍歷以中序線索鏈表為存儲結構的中序遍歷voidInOrderTraverse_Thr(BiThrTreeT,void(*Visit)(ElemTypee))

{//T指向中序線索鏈表中的頭結點，頭結點的左指針Lchild指向二叉樹的根結點，頭結點的右線索Rchild指向中序遍歷訪問的最后一個結點。本算法對此二叉樹進行中序遍歷，對樹中每個元素調用函數Visit進行訪問操作

p=T->Lchild;

//p指向二叉樹的根結點

while(p!=T) {

//空樹或遍歷結束時，p==Thead

while(p->LTag==Link)p=p->Lchild;

Visit(p->data);

//訪問其左子樹為空的結點

while(p->RTag==Thread&&p->Rchild!=T) {

p=p->rchild;Visit(p->data);//訪問“右線索”所指后繼結點

}

p=p->Rchild;

//p進至其右子樹根

}

}6.4樹和森林一、樹的存儲結構雙親表示法孩子表示法孩子兄弟表示法1樹的雙親表示法

constMAX_TREE_SIZE=100;

typedefstruct{//結點結構

ElemTypedata;

intparent;//雙親位置域

}PTNode;

typedefstruct{//樹結構

PTNodenodes[MAX_TREE_SIZE];

intr,n;//根的位置和結點數

}PTree;

2樹的孩子表示法

樹的孩子鏈表存儲表示

typedefstructCTNode{

//孩子結點 intchild;//結點的位置 structCTNode*next;//相同父親的下一節點的指針

}*ChildPtr;

typedefstruct{

ElemTypedata;//結點的數據元素

ChildPtrfirstchild;//孩子鏈表頭指針

}CTBox;

typedefstruct{

CTBoxnodes[MAX_TREE_SIZE];

intn,r;

//結點數和根結點的位置

}CTree;3樹和森林的孩子兄弟表示法

存儲表示

typedefstructCSNode{

ElemTypedata;

structCSNode*firstchild,*nextsibling;

}CSNode,*CSTree;

firstchild指向該結點的"第一個"子樹根結點，nextsibling指向它的"下一個"兄弟結點。樹的孩子-兄弟鏈表

森林的孩子-兄弟鏈表

二、森林和二叉樹的轉換樹－>二叉樹森林－>二叉樹將森林中的每棵樹變為二叉樹，轉換所得二叉樹根結點的右子樹均為空；將各二叉樹的根結點視為兄弟從左至右，連在一起，形成一棵二叉樹。二叉樹森林二叉樹森林若結點x是其雙親y的左孩子，則把x的右孩子，右孩子的右孩子…，都與y用連線連接起來，最后去掉所有雙親到右孩子的連線。三、樹和森林的遍歷

先根(次序)遍歷樹

若樹不空，則先訪問根結點，然后依次從左到右先根遍歷根的各棵子樹；ABEHIJCDFGK后根(次序)遍歷樹

若樹不空，則先依次從左到右后根遍歷根的各棵子樹，然后訪問根結點；HIJEBCFKGDA森林的遍歷：1、先序遍歷森林

若森林不空，則可依下列次序進行遍歷

(1)訪問森林中第一棵樹的根結點；

(2)先序遍歷第一棵樹中的子樹森林；

(3)先序遍歷除去第一棵樹之后剩余的樹構成的森林。2、中序遍歷森林

若森林不空，則可依下列次序進行遍歷：

(1)中序遍歷第一棵樹中的子樹森林；

(2)訪問森林中第一棵樹的根結點；

(3)中序遍歷除去第一棵樹之后剩余的樹構成的森林。6.6赫夫曼樹及其應用（5%+2*15%+3*40%+4*40%）*10000=31500一、最優二叉樹0~5960~6970~7980~8990~1005%15%40%30%10%（2*40%+3*20%+2*40%）*10000=22000具有不同路徑長度的二叉樹路徑長度(PathLength)

兩個結點之間的路徑長度是連接兩結點的路徑上的分支數。樹的路徑長度是各葉結點到根結點的路徑長度之和。帶權路徑長度

(WeightedPathLength,WPL)樹的帶權路徑長度是樹的各葉結點所帶的權值與該結點到根的路徑長度的乘積的和。具有不同帶權路徑長度的二叉樹最優二叉樹

帶權路徑長度達到最小的二叉樹即為最優二叉樹。在最優二叉樹中，權值大的結點離根最近。二最優二叉樹的構造——赫夫曼算法

(1)由給定的n個權值{w0,w1,w2,…,wn