樹和二叉樹第六章

第六章樹和二叉樹6.1樹的定義和基本術(shù)語6.2二叉樹6.3遍歷二叉樹和線索二叉樹6.4樹和森林6.6赫夫曼樹及其應(yīng)用

6.1樹的定義和基本術(shù)語樹(Tree)：是n(n>=0)個(gè)結(jié)點(diǎn)的有限集。在任意一個(gè)非空樹中：⑴有且僅有一個(gè)特定的稱為根(Root)的結(jié)點(diǎn)；⑵當(dāng)n>=1時(shí)，其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集T1,T2,…,Tm,其中Ti是一棵樹，稱為根結(jié)點(diǎn)子樹例:(a)是只有一個(gè)根結(jié)點(diǎn)的樹.(b)是有13個(gè)結(jié)點(diǎn)的樹，A是根，其余結(jié)點(diǎn)分成三個(gè)互不相交的子集：T1=(B,E,F,K,L);T2=(C,G);T3=(D,H,I,J,M).T1,T2,T都是根A的子樹，本身也是一棵樹AAFLDJGEBIKHMC(a)只有根結(jié)點(diǎn)的樹T1T2T3(b)一般的樹A是根，T1,T2,T3是三棵子樹ADTTree{

數(shù)據(jù)對象D:D是具有相同特性的數(shù)據(jù)元素的集合.

數(shù)據(jù)關(guān)系R:若D為空集，則稱為空樹；若D僅含一個(gè)數(shù)據(jù)元素，則R為空集，否則R={H},H是如下二元關(guān)系：(1)在D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下無前驅(qū)；

抽象類型樹的定義(2)若D-{root}=φ，則存在D-{root}的一個(gè)劃分D1D2,…,

Dn(m>0),對任意j=k(1<=j,k<=m)有Dj∩

Dk=φ,且對任意的i(1<=i<=m),唯一存在數(shù)據(jù)元素xi∈Di，有<root,xi>∈H;⑶對應(yīng)于D-{root}的劃分，H-{<root,xi>,…,<root,xn>}有唯一的一個(gè)劃分H1,H2,…,

Hn(m>0),對任意的j=k(1<=j,k<=m)有Hj

∩Hk=φ，且對任意i(1<=i<=m),Hi是Di上的二元關(guān)系，(Di,{Hi})是一棵符合本定義的樹，稱為根root的子樹。

基本操作P:InitTree(&T);操作結(jié)果：構(gòu)造空樹T

DestroyTree(&T);初始條件：樹T存在操作結(jié)果：銷毀樹T樹的基本操作CreatTree(&T,definition);初始條件：definition給出樹T的定義操作結(jié)果：按definition樹構(gòu)造樹T

ClearTree(&T)初始條件：數(shù)T存在操作結(jié)果：將樹T清為空樹TreeEmpty(T);初始條件：樹T存在操作結(jié)果：若T為空樹，則返回TRUE，否則FALSETreeDepth(T);初始條件：樹T存在操作結(jié)果：返回T的深度Root(T);初始條件：樹T存在操作結(jié)果：返回T的根Value(T,cur_e);初始條件：樹T存在，cur_e是T中某個(gè)結(jié)點(diǎn)操作結(jié)果：返回cur_e的值A(chǔ)ssign(T,cur_e,value);初始條件：樹T存在，cur_e是T中某個(gè)結(jié)點(diǎn)操作結(jié)果：結(jié)點(diǎn)cur_e賦值為valueParent(T,cur_e);初始條件：樹T存在，cur_e是T中某個(gè)結(jié)點(diǎn)操作結(jié)果：若cur_e是T的非根結(jié)點(diǎn)，則返回它的雙親，否則函數(shù)值為“空”LeftChild(T,cur_e);初始條件：樹T存在，cur_e是T中某個(gè)結(jié)點(diǎn)操作結(jié)果：若cur_e是T的非葉子結(jié)點(diǎn)，則返回它的最左孩子，否則返回“空”RightSibling(T,cur_e);初始條件：樹T存在，cur_e是T中某個(gè)結(jié)點(diǎn)操作結(jié)果：若cur_e有右兄弟，則返回它的右兄弟，否則函數(shù)值為“空”InsertChild(&T,&P,i,c);初始條件：樹T存在，P指向T中某個(gè)結(jié)點(diǎn)，1<=i<=P所指結(jié)點(diǎn)的度+1,非空樹c與T不相交操作結(jié)果：插入c為T中p指結(jié)點(diǎn)第i棵子樹DeleteChild(&T,&P,i);初始條件：樹T存在,p指向T中某個(gè)結(jié)點(diǎn)，1<=i<=P指結(jié)點(diǎn)的度操作結(jié)果：刪除T中P所指結(jié)點(diǎn)的第i棵子樹TraverseTree(T,Visit());初始條件：樹T存在,Visit是對結(jié)點(diǎn)操作的應(yīng)用函數(shù)操作結(jié)果：按某種次序樹對T的每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)visit()一次且至多一次，一旦visit()失敗，則操作失敗}ADTTree樹的邏輯表示形式(a)樹型結(jié)構(gòu)(b)嵌套集合(c)廣義表(d)凹入表(目錄表示法)ACFEBDABCDEF(b)(a)(A(B(E),C(F),D)(C)ABECFD(d)凹入表度：結(jié)點(diǎn)擁有的子樹數(shù)稱為結(jié)點(diǎn)的度葉子（終端結(jié)點(diǎn)）：度為0的結(jié)點(diǎn)非終端結(jié)點(diǎn)（分支結(jié)點(diǎn)）：度不為0的結(jié)點(diǎn)樹的度是樹內(nèi)各結(jié)點(diǎn)的度的最大值結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的孩子該結(jié)點(diǎn)稱為孩子的雙親(parent)深度：樹中結(jié)點(diǎn)的最大層次樹的基本術(shù)語AFLDJGEBIKHMC例下圖，D是A的子樹T3的根，則D是A的孩子，而A則是D的雙親，同一個(gè)雙親的孩子之間互稱兄弟。結(jié)點(diǎn)的層次從根開始定義起，根為第一層，根的孩子為第二層。T3T2T1有序樹：將樹中結(jié)點(diǎn)的各子樹看成從左到右是有次序的（不能互換），稱該樹為有序樹。無序樹：將樹中結(jié)點(diǎn)的各子樹看成從左到右是無次序的（不能互換），稱該樹為無序樹。森林：是m(m>=0)棵互不相交的樹的集合

6.2二叉樹定義：是一棵或?yàn)榭諛?，或樹中每個(gè)結(jié)點(diǎn)的度數(shù)<=2有序樹特點(diǎn)：⑴每個(gè)結(jié)點(diǎn)至多有兩棵子樹⑵二叉樹的子樹有左右之分,其次序不能任意互換Φ(a)(b)(c)(d)(e)(a)空二叉樹(b)僅有根結(jié)點(diǎn)的二叉樹(c)右子樹為空的二叉樹(d)左，右子樹均非空的二叉樹(e)左子樹為空的二叉樹二叉樹的五中基本形態(tài)：InitBiTree(&T);操作結(jié)果：構(gòu)造空二叉樹T

DestroyBiTree(&T);初始條件：二叉樹T存在操作結(jié)果：銷毀二叉樹T二叉樹的基本操作CreatBiTree(&T,definition);初始條件：definition給出二叉樹T的定義操作結(jié)果：按definition樹構(gòu)造二叉樹T

ClearBiTree(&T)初始條件：二叉樹T存在操作結(jié)果：將二叉樹T清為空樹BiTreeEmpty(T);初始條件：二叉樹T存在操作結(jié)果：若T為空二叉樹，則返回TRUE，否則FALSEBiTreeDepth(T);初始條件：二叉樹T存在操作結(jié)果：返回T的深度Root(T);初始條件：二叉樹T存在操作結(jié)果：返回T的根Value(T,e);初始條件：二叉樹T存在，e是T中某個(gè)結(jié)點(diǎn)操作結(jié)果：返回e的值A(chǔ)ssign(T,cur_e,value);初始條件：樹T存在，cur_e是T中某個(gè)結(jié)點(diǎn)操作結(jié)果：結(jié)點(diǎn)cur_e賦值為valueParent(T,e);初始條件：二叉樹T存在，e是T中某個(gè)結(jié)點(diǎn)操作結(jié)果：若e是T的非根結(jié)點(diǎn)，則返回它的雙親，否則返回“空”LeftChild(T,e);初始條件：二叉樹T存在，e是T中某個(gè)結(jié)點(diǎn)操作結(jié)果：返回e的左孩子，若無左孩子.返回“空”RightChild(T,e);初始條件：二叉樹T存在，e是T中某個(gè)結(jié)點(diǎn)操作結(jié)果：返回e的右孩子若無右孩子.返回“空”LeftSibling(T,cur_e);初始條件：二叉樹T存在，e是T中某個(gè)結(jié)點(diǎn)操作結(jié)果：返回e的左兄弟，否則函數(shù)值為“空”RightSibling(T,e);初始條件：二叉樹T存在，e是T中某個(gè)結(jié)點(diǎn)操作結(jié)果：返回e的右兄弟，否則函數(shù)值為“空”InsertChild(T,P,LR,c);初始條件：二叉樹T存在，P指向T中某個(gè)結(jié)點(diǎn)，LR為0或者1,非空二叉樹c與T不相交并且右子樹為空.操作結(jié)果：根據(jù)LR為0或1,插入c為T中p指結(jié)點(diǎn)左或右子樹.P所指結(jié)點(diǎn)的原有左或者右子樹則成為c的右子樹DeleteChild(T,P,LR);初始條件：二叉樹T存在,p指向T中某個(gè)結(jié)點(diǎn)，LR為0或1.操作結(jié)果：根據(jù)LR為0或1,刪除T中P所指結(jié)點(diǎn)的左或者右子樹PreorderTraverse(T,Visit());初始條件：二叉樹T存在,Visit是對結(jié)點(diǎn)操作的應(yīng)用函數(shù)操作結(jié)果：按先序遍歷二叉樹T,對T的每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)visit()一次且至多一次，一旦visit()失敗，則操作失敗InorderTraverse(T,Visit());初始條件：二叉樹T存在,Visit是對結(jié)點(diǎn)操作的應(yīng)用函數(shù)操作結(jié)果：中序遍歷樹T,對T的每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)visit()一次且至多一次，一旦visit()失敗，則操作失敗.PostTraverse(T,Visit());初始條件：二叉樹T存在,Visit是對結(jié)點(diǎn)操作的應(yīng)用函數(shù)操作結(jié)果：后序遍歷樹T,對T的每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)visit()一次且至多一次，一旦visit()失敗，則操作失敗LevelTraverseT(T,Visit());初始條件：二叉樹T存在,Visit是對結(jié)點(diǎn)操作的應(yīng)用函數(shù)操作結(jié)果：層次遍歷樹T,對T的每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)visit()一次且至多一次，一旦visit()失敗，則操作失敗.}ADTBinarytree性質(zhì)1

在二叉樹的第i層上至多有2i-1各結(jié)點(diǎn)證明：用歸納法證明

i=1時(shí)，只有一個(gè)根結(jié)點(diǎn).顯然，2i-1=20=1是對的設(shè)當(dāng)n=k-1時(shí)，第k-1層上至多有2k-2個(gè)結(jié)點(diǎn)則當(dāng)n=k時(shí)，每個(gè)結(jié)點(diǎn)至多有兩棵子樹所以：k層結(jié)點(diǎn)數(shù)最多為k-1層的2倍所以：S<=2×2k-2=2k-1成立二叉樹的性質(zhì)性質(zhì)2

深度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)(k>=1)由性質(zhì)1可知，深度為k的二叉樹的最大結(jié)點(diǎn)數(shù)為∑i=1k(第i層上的最大結(jié)點(diǎn)數(shù))=∑i=1k2i-1=2k-1性質(zhì)3

對任何一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1

證明：設(shè)n1為二叉樹T中度為1的結(jié)點(diǎn)數(shù)。因?yàn)槎鏄渲兴薪Y(jié)點(diǎn)的度均小于或等于2，所以結(jié)點(diǎn)總數(shù)為

n=n0+n1+

n2(1)

對二叉樹的分支數(shù)，除了根結(jié)點(diǎn)外，其余結(jié)點(diǎn)都有一個(gè)分支進(jìn)入，設(shè)B為分支總數(shù)，則n=B+1。由于這些分支是由度為1或2的結(jié)點(diǎn)射出的，所以又有B=n1+2n2

得出：n=n1+2n2+1(2)

由式(1)和式(2)得:n0=n2+1

特殊形態(tài)的二叉樹滿二叉樹：深度為k,具有2k-1個(gè)結(jié)點(diǎn)得二叉樹完全二叉樹：對深度為k，n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每個(gè)結(jié)點(diǎn)都與深度為k的完整二叉樹結(jié)點(diǎn)為編號(hào)從1到n結(jié)點(diǎn)一一對應(yīng)特殊形態(tài)的二叉樹圖示6175432165432滿二叉樹完全二叉樹性質(zhì)4

具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為log2n+1證明：假設(shè)深度為k，則根據(jù)性質(zhì)2和完全二叉樹的定義有

2k-1-1<n<=2k-1

于是k-1<=log2n<k因?yàn)閗是整數(shù)所以原題得證

完全二叉樹的兩個(gè)重要特性性質(zhì)5如果對一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹，則對任一結(jié)點(diǎn)i(1<=i>=n)有⑴如果i=1，則結(jié)點(diǎn)i是二叉樹的根，無雙親;如果i>1,則其雙親PARENT(i)是結(jié)點(diǎn)i/2。⑵如果2i>n,則結(jié)點(diǎn)i無左孩子（結(jié)點(diǎn)i為葉子結(jié)點(diǎn));否則其左孩子LCHILD(i)是結(jié)點(diǎn)2i.⑶如果2i+1>n,則結(jié)點(diǎn)i無右孩子;否則其右孩子RCHILD(i)是結(jié)點(diǎn)2i+1㈠順序存儲(chǔ)結(jié)構(gòu)：15643271234567對應(yīng)順序存儲(chǔ)結(jié)構(gòu)完全二叉樹二叉樹的存儲(chǔ)結(jié)構(gòu)

135642712345000067一般二叉樹順序存儲(chǔ)結(jié)構(gòu)二叉樹的順序存儲(chǔ)表示#defineMAX_TREE_SIZE100//二叉樹的最大結(jié)點(diǎn)數(shù)Typedef

TElemType

SqBiTree[MAX_TREE_SIZE];//0號(hào)單元存儲(chǔ)根結(jié)點(diǎn)SqBiTree

bt;㈡鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)二叉鏈表結(jié)點(diǎn)結(jié)構(gòu)lchilddatarchild左指針域數(shù)據(jù)域右指針域二叉樹的二叉鏈表存儲(chǔ)表示Typedef

struct

Bitnode{

TElemTypedata;

struct

BiTNode*lchild,*rchild;//左,右孩子指針}BiTNode,*BiTree;三叉鏈表結(jié)點(diǎn)結(jié)構(gòu)lchildDataParentrchild雙親結(jié)點(diǎn)域ADCBA∧B∧C∧∧D∧單支樹的二叉鏈表ADFEBCGA∧BD∧C∧∧F∧∧E∧G∧二叉鏈表ACBDFEGA∧∧B∧C∧D∧F∧∧E∧G∧三叉鏈表6.3遍歷二叉樹和線索二叉樹遍歷二叉樹：訪問每個(gè)結(jié)點(diǎn)，一次僅且一次先序遍歷二叉樹的操作定義為：若二叉樹為空，則空操作；否則⑴訪問根結(jié)點(diǎn)⑵先序遍歷左子樹⑶先序遍歷右子樹中序遍歷二叉樹的操作定義為：若二叉樹為空，則空操作；否則⑴中序遍歷左子樹⑵訪問根結(jié)點(diǎn)；⑶中序遍歷右子樹后序遍歷二叉樹的操作定義若二叉樹為空，則空操作；否則⑴后序遍歷左子樹⑵后序遍歷右子樹⑶訪問根結(jié)點(diǎn)層次遍歷二叉樹的操作定義若二叉樹為空，則空操作；否則從上到下,從左到右依次訪問各個(gè)結(jié)點(diǎn)例：如圖所示的二叉樹，表示下述表達(dá)式a+b*(c－d)－e/f若先序遍歷此樹，得到前綴表達(dá)式（波蘭式）－+a*b－cd/ef若中序遍歷二叉樹，得到中綴表達(dá)式a+b*c－d－e/f若后序遍歷二叉樹，的到后綴表達(dá)式（逆波蘭式）abcd－*+ef/－－fe/+a*b－dc算法6.1StatusPreOrderTraverse(BiTree

T,Status(*Visit)(TElemTypee)){If(T){if(Visit(T->data))

if(PreorderTraverse(T->lchild,Visit))

if(PreorderTraverse(T->rchild,Visit))returnOK;returnERROR;}elsereturnOK;}//PreorderTraverse先序遍歷二叉樹的遞歸算法層次遍歷二叉樹的算法用隊(duì)列輔助實(shí)現(xiàn)StatusleverOrderTraverse(BiTree

T,Statut(*Visit)(TElemTypee)){

InitQueue(Q);EnQueue(Q,T);

while(!QueueEmpty(Q)){

DelQueue(Q,p);if(p!=NULL){

visit(p->data);EnQueue(Q,p->lchild);EnQueue(Q,p->rchild);}}//whileReturnOK;}二叉樹遍歷的非遞歸算法一.先序遍歷非遞歸算法先序遍歷的特點(diǎn)是:首先訪問根結(jié)點(diǎn),訪問完根后訪問左子樹,所以對每一個(gè)結(jié)點(diǎn),訪問完該結(jié)點(diǎn)后,沿其左孩子鏈訪問下去,直到左鏈為空.這時(shí),所有訪問過的結(jié)點(diǎn)進(jìn)棧.然后結(jié)點(diǎn)出棧,對于每一個(gè)出棧結(jié)點(diǎn),即表示該結(jié)點(diǎn)和其左子樹已經(jīng)被訪問結(jié)束,按先序遍歷定義,應(yīng)該訪問該結(jié)點(diǎn)的右子樹算法思想:1.當(dāng)前指針指向根結(jié)點(diǎn).2.訪問當(dāng)前結(jié)點(diǎn),并且進(jìn)棧,當(dāng)前指針指向當(dāng)前結(jié)點(diǎn)的左孩子,重復(fù)2>,直到左孩子為空3.依次退棧,將當(dāng)前指針指向出棧結(jié)點(diǎn)的右孩子.4.若棧非空,或者當(dāng)前指針非空,執(zhí)行2>,否則結(jié)束.Statuspreorder(BiTreeT,status(*visit()){

initstack(s);push(s,T);while(!stackempty(s)){while(gettop(s,p)&&p){if(visit(p->data))retureERROR;

push(s,p->lchild);}

pop(s,p);

if(!stackempty(s)){

pop(s,p);

push(s,p->rchild);}//if}//whileReturnOK;}二.中序遍歷非遞歸算法

二.中序遍歷非遞歸算法中序的特點(diǎn)是:首先訪問左子樹,所以對每一個(gè)結(jié)點(diǎn),沿左鏈走下去,直到左鏈為空,所有經(jīng)過的結(jié)點(diǎn)進(jìn)棧.然后結(jié)點(diǎn)出棧,對于每一個(gè)出棧結(jié)點(diǎn),表示該結(jié)點(diǎn)的左子樹訪問結(jié)束.按中序遍歷的定義,應(yīng)該訪問該結(jié)點(diǎn)(根),訪問完該結(jié)點(diǎn)后,訪問該結(jié)點(diǎn)的右子樹.1.當(dāng)前指針指向根結(jié)點(diǎn).2.當(dāng)前結(jié)點(diǎn)進(jìn)棧,當(dāng)前指針指向其左孩子,重復(fù)2>,直到左孩子為空.3.依次退棧,退棧指針成為當(dāng)前指針,訪問當(dāng)前結(jié)點(diǎn).4.將當(dāng)前指針指向右孩子.5.若棧非空或者當(dāng)前指針非空,執(zhí)行2>;否則結(jié)束.Statusinorder(Bitree

T,status(*visit()){

initstack(s);push(s,t);

while(!stackEmpt(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);}//if}//whileReturnOK;}三.后序遍歷非遞歸算法三.后序遍歷非遞歸算法在后序遍歷中,當(dāng)當(dāng)前指針指向某個(gè)結(jié)點(diǎn)時(shí),不能馬上進(jìn)行訪問,而先要遍歷左子樹,所以要求該結(jié)點(diǎn)進(jìn)棧保存.當(dāng)訪問完它的左子樹后,再次搜索該結(jié)點(diǎn)時(shí),還不能進(jìn)行訪問,還要遍歷其右子樹.所以需要再次將此結(jié)點(diǎn)入棧保存.為了區(qū)別同一結(jié)點(diǎn)的兩次入棧,需要引進(jìn)一個(gè)入棧次數(shù)的標(biāo)志.我們約定:標(biāo)志0為該結(jié)點(diǎn)首先入棧,標(biāo)志1為該結(jié)點(diǎn)第二次入棧.為此需要設(shè)兩個(gè)棧:一個(gè)棧用來存放結(jié)點(diǎn)地址,即為結(jié)點(diǎn)棧s1[m],另一個(gè)棧用來存放結(jié)點(diǎn)進(jìn)棧標(biāo)志,即標(biāo)志棧s2[m],棧指針為同一個(gè).1.當(dāng)前指針指向根結(jié)點(diǎn)2.當(dāng)前結(jié)點(diǎn)進(jìn)棧,所對應(yīng)的標(biāo)志為0,當(dāng)前指針其左孩子,重復(fù)2>,直到左孩子為空.3.當(dāng)棧頂標(biāo)志為1時(shí),依次退棧,并且訪問退棧指針?biāo)附Y(jié)點(diǎn),直到標(biāo)志為04.將棧頂標(biāo)志變成為1,將當(dāng)前指針指向棧頂元素的右孩子,準(zhǔn)備遍歷右子樹.5.若棧頂非空或者當(dāng)前指針非空,執(zhí)行2>,否則結(jié)束.Voidpostorder(BiTree

T,status(*visit()){

ints2[m],top=0;

BiTreep,s1[m];p=T;do{while(p!=NULL){s1[top]=p;s2[top++]=0;//p結(jié)點(diǎn)首先入棧p=p->lchild;}//遍歷左子樹

while(top&&s2[top-1]==1){top--;p=s1[top];visit(p->data);}If(top>0){s2[top-1]=1;P=s1[top-1]->rchild;}//修改標(biāo)志,即處理當(dāng)前根結(jié)點(diǎn)的右子樹并且使p指向右子樹}while(top>0);}-bac*表達(dá)式(a*b-c)的二叉樹-bac*12-*abc--**aabbcc遍歷的遞歸執(zhí)行過程，其中紅色，藍(lán)色，綠色分別表示先序，中序，后序遍歷過程中訪問結(jié)點(diǎn)輸出信息方法一：LeftDatarightLeftPDataNright指向前驅(qū)結(jié)點(diǎn)指向某一種遍歷下后繼結(jié)點(diǎn)在二叉鏈表中增加指向某一種遍歷下前驅(qū)和后繼指針(線索）目的：提高查找某一種遍歷下前驅(qū)和后繼結(jié)點(diǎn)效率線索二叉樹方法二：利用二叉鏈表中（n+1個(gè)）空指針域來作為指向某一種遍歷下前趨和后繼結(jié)點(diǎn)的指針域，為了區(qū)別指針的用途，同時(shí)在每個(gè)結(jié)點(diǎn)增加兩個(gè)標(biāo)志域Ltag,Rtag

lchildLtagDataRtagrchild其中：Ltag=0lchild域指示結(jié)點(diǎn)的左孩子1lchild域指示結(jié)點(diǎn)的前驅(qū)Rtag=0rchild域指示結(jié)點(diǎn)的右孩子1rchild域指示結(jié)點(diǎn)的后繼b－/fedc－*a+NILNIL中序線索二叉樹010－00/00+01e11f10*01a10－01b11d11c1thrtbt中序線索鏈表二叉樹的二叉線索存儲(chǔ)表示二叉樹的二叉線索存儲(chǔ)表示：Typedef

enum{Link,Thread}PointerTag;//Link==0:指針，Thread==1;線索Typedef

struct

BiThrNode{

TElemTypedata;

struct

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

PointerTag

Ltag,Rtag;//左右標(biāo)志}BiThrNode,*BiThrTree;a.只要找到序列中第一個(gè)結(jié)點(diǎn)，然后依次找結(jié)點(diǎn)后繼直至其后繼為空為止。如何在中序線索樹中找結(jié)點(diǎn)的后繼的方法：（1）若Rtag=1，則rchild指的是后繼結(jié)點(diǎn)（2）若Rtag=0，則右子樹的最左孩子為其后繼結(jié)點(diǎn)在線索樹上進(jìn)行遍歷的方法

b.或只要找到序列中最后一個(gè)結(jié)點(diǎn)，然后依次找結(jié)點(diǎn)前趨直至其前趨為空為止。如何在中序線索樹中找結(jié)點(diǎn)前趨的方法：（1）若Ltag=1，則lchild指的是前趨結(jié)點(diǎn)（2）若Ltag=0，則左子樹的最右孩子為其前趨結(jié)點(diǎn)在線索樹上進(jìn)行遍歷的方法算法6。5：StatusInOrderTraverse_Thr(BiThrTreeT,Status(*Visit)(TElemTypee)){//T指向頭結(jié)點(diǎn)，頭結(jié)點(diǎn)的左鏈Lchhild指向根結(jié)點(diǎn)//中序遍歷二叉線索樹T的非遞歸算法，

//對每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)VisitP=T->lchild;//P指向根結(jié)點(diǎn)While(P!=T){//空樹或遍歷結(jié)束時(shí)，p==Twhile(p->Ltag==Link)p=p->lchild;

中序遍歷二叉線索樹T的非遞歸算法if(!Visit(p->data))returnERROR;//訪問其左子樹為空的結(jié)點(diǎn)while(p->Rtag==Thread&&p->rchild!=T){

p=p->rchild;Visit(p->data);//訪問后繼結(jié)點(diǎn)}

p=p->rchild;}returnOK;}//InOrderTraverse_Thr在后序線索樹中找結(jié)點(diǎn)后繼，分三種情況：⑴若結(jié)點(diǎn)x是二叉樹的根，則后繼為空；⑵若結(jié)點(diǎn)x是其雙親的右孩子或是其雙親的左孩子且其雙親沒有右子樹，則其后繼即為雙親結(jié)點(diǎn)⑶若結(jié)點(diǎn)x是其雙親的左孩子，且其雙親有右子樹，則其后繼為雙親的右子樹上按后序遍歷列出的第一個(gè)結(jié)點(diǎn)

線索化的實(shí)質(zhì)：是將二叉鏈表中的空指針改為指向前驅(qū)或后繼的線索，而前驅(qū)或后繼的信息只有在遍歷時(shí)才能得到，所以線索化的過程為遍歷過程中修改空指針的過程。設(shè):pre指針,始終指向剛剛訪問過的結(jié)點(diǎn)，若p指向當(dāng)前訪問的結(jié)點(diǎn)，則pre指向其前驅(qū)二叉樹的線索化算法算法6.6：StatusInorderThreading(BiThrTree&Thrt,

BiThrTreeT){//中序遍歷二叉樹T，并將其中中序線索化，Thrt指向頭結(jié)點(diǎn)

if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode))))

exit(OVERFLOW);

Thrt->Ltag=Link;

Thrt->Rtag=Thread;//建頭結(jié)點(diǎn)

Thrt->rchild=Thrt;//右指針回指

if(!T)Thrt->lchild=Thrt;//若二叉樹為空，則左指針回指else{

Thrt->lchild=T;pre=Thrt;

InThreading(T);//中序遍歷進(jìn)行中序線索化pre->rchild=Thrt;pre->RTag=Thread;//最后一個(gè)結(jié)點(diǎn)線索化

Thrt->rchild=pre;}returnOK;}//InOrderThreading算法6.7VoidInThreading(BiThrTreep){if(p){

InThreading(p->lchild);//左子樹線索化

if(!p->lchild){p->Ltag=Thread;p->lchild=pre;};

//前驅(qū)線索

if(!pre->rchild){pre->Rtag=Thread;pre->rchild=p;}//后繼線索

pre=p;//保持pre指向p的前驅(qū)

InThreading(p->rchild);//右子樹線索化}}//InThreading

6.4樹和森林樹的存儲(chǔ)結(jié)構(gòu)⑴雙親表示法以一組連續(xù)空間存儲(chǔ)樹的結(jié)點(diǎn)，同時(shí)在每個(gè)結(jié)點(diǎn)中附設(shè)一個(gè)指示器指示其雙親結(jié)點(diǎn)在鏈表中的位置.樹的雙親表存儲(chǔ)表示：#defineMAX_TREE_SIZE100Typedef

struct

PTNode{

TElemTypedata;

intparent;//雙親位置域}PTNode;Typedef

struct{

PTNodenodes[MAX_TREE_SIZE];

intn;//結(jié)點(diǎn)數(shù)}Ptree;如圖：樹的雙親表示法示例REDBACFKHGR-1A0B0C0D1E1F3G6H6K601234567896-13⑵孩子表示法方法一：多重鏈表法每個(gè)結(jié)點(diǎn)結(jié)構(gòu)DataChild1Child2…childdd樹的度DataDegreeChild1Child2…childdd結(jié)點(diǎn)度方法二：孩子鏈表法為每個(gè)孩子建立一個(gè)孩子鏈表孩子鏈表存儲(chǔ)結(jié)構(gòu)：Typedef

struct

CTNode{//孩子結(jié)點(diǎn)

intchild;

struct

CTNode*next;}*ChildPtr;Typedef

struct{

TElemTypedata;

ChildPtr

firstchild;//孩子鏈表頭指針}CTBox;Typedef

struct{

CTBoxnodes[MAX_TREE_SIZE];

int

n,r;//結(jié)點(diǎn)數(shù)和根的位置}Ctree;如圖:是圖6-13的孩子鏈表表示法AB∧CD∧RE∧FG∧H∧K∧35∧6∧2∧109∧870123456789雙親表示法和孩子表示法結(jié)合如圖：是下圖6-14對應(yīng)的帶雙親的孩子鏈表4A4B∧4C0D∧-1R0E∧2F6G∧6H∧6K∧35∧6∧2∧109∧870123456789REDBACFKHG6-14三.孩子兄弟表示法以二叉鏈表作為樹的存儲(chǔ)結(jié)構(gòu)。鏈表中結(jié)點(diǎn)的兩個(gè)鏈域分別指向該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)孩子結(jié)點(diǎn)，分別命名為firstchild域和nextsibling域。又稱為二叉鏈表表示法存儲(chǔ)表示：Typedef

struct

CSNode{

ElemTypedata;

struct

CSNode*firstchild,*nextsibling;}CSNode,*CSNree;

樹轉(zhuǎn)化為二叉樹方法：左手拉第一個(gè)孩子，右手拉下一個(gè)兄弟AECBDEDCBA樹二叉樹森林與二叉樹的轉(zhuǎn)換森林轉(zhuǎn)化為二叉樹方法：將森林中每棵樹轉(zhuǎn)化為二叉樹,第一棵樹的根為二叉樹的根，森林中各棵樹的根是兄弟關(guān)系.如圖：AJIHGFEDCBADCBFEJIHG森林二叉樹樹遍歷方法：⑴先根(次序)遍歷樹方法：先訪問樹的根結(jié)點(diǎn)，然后依次先根遍歷根的每棵子樹⑵后根(次序)遍歷方法：先依次后根遍歷每棵子樹，然后訪問根結(jié)點(diǎn)樹和森林的遍歷例：對下圖進(jìn)行先根遍歷，得到先根序列為ABCDE對此樹進(jìn)行后根遍歷，得到樹的后根序列為BDCEAADECB⑴先序遍歷森林若森林非空，按下述規(guī)律遍歷：⒈訪問森林中第一棵樹的根結(jié)點(diǎn)；⒉先序遍歷第一棵樹中根結(jié)點(diǎn)的子樹森林；⒊先序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。⑵中序遍歷森林若森林非空：⒈中序遍歷森林中第一棵樹的根接點(diǎn)的子樹森林；⒉訪問第一棵樹的根結(jié)點(diǎn)；⒊中序遍歷除去第一棵樹之后剩余的樹構(gòu)成森林。森林遍歷方法對下圖中森林進(jìn)行先序遍歷和中序遍歷，先序序列為：ABCDEFGHIJ中序序列為：BCDAFEHJIG如圖：AJIHGFEDCBADCBFEJIHG森林二叉樹

6.6赫夫曼樹及其應(yīng)用路徑長度：路徑上的分枝數(shù)目稱為樹的路徑長度樹的路徑長度：從樹根到每一結(jié)點(diǎn)的路徑長度之和樹的帶權(quán)路徑長度：樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和，通常記作：WPL=∑k=1n

wkLk最優(yōu)二叉樹(haffman樹)：帶權(quán)路徑長度WPL最小的二叉樹如圖中的三棵二叉樹，都有4個(gè)葉子結(jié)點(diǎn)a,b,c,d,分別帶權(quán)7,5,2,4abcdcbaddcba752475247524(a)(b)(c)它們的帶權(quán)路徑長度分別為(a)WPL=7×2+5×2+2×2+4×2=36(b)WPL=7×3+5×3+2×1+4×2=46(c)WPL=7×1+5×2+2V3+4×3=35⑴根據(jù)給定的n個(gè)權(quán)值{w1,w2,…,wn}構(gòu)成n棵二叉樹的集合F={T1,T2,…,Tn},其中每棵二叉樹Ti中只有一個(gè)帶權(quán)為wi的根結(jié)點(diǎn)，其左右子樹均空⑵在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，且置新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左，右子樹上根結(jié)點(diǎn)的權(quán)值之和。⑶在F中刪除這兩棵樹，同時(shí)將新得到的二叉樹加入F中⑷重復(fù)(2)和(3)，直到F只含一棵樹為止。赫夫曼樹構(gòu)造算法adcb75245b11a718cd624如圖：展示了構(gòu)造赫夫曼樹的構(gòu)造過程。其中，根結(jié)點(diǎn)上標(biāo)注的數(shù)字是所賦的權(quán)。赫夫曼編碼利用Haffman樹進(jìn)行編碼，各葉子結(jié)點(diǎn)表示待進(jìn)行編碼的字符,約定二叉樹左分枝為0，右分枝為1，從根到葉的編碼串就是這個(gè)葉子結(jié)點(diǎn)字符的Haffman編碼例6-2已知某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)八種字符，其概率分別為0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11,試設(shè)計(jì)赫夫曼編