數(shù)據(jù)結(jié)構(gòu)第講線索樹與樹和森林

數(shù)據(jù)結(jié)構(gòu)第講線索樹與樹和森林第一頁(yè)，共四十六頁(yè)，編輯于2023年，星期三6.3.2線索二叉樹1.何謂線索二叉樹？遍歷結(jié)果是求得結(jié)點(diǎn)的一個(gè)線性序列。指向該線性序列“前驅(qū)”和“后繼”的指針，稱“線索”；包含“線索”的存儲(chǔ)結(jié)構(gòu)，稱為“線索鏈表”；與其相應(yīng)的二叉樹，稱為“線索二叉樹”；對(duì)二叉樹以某種次序遍歷，使其變?yōu)榫€索二叉樹的過程，稱為“線索化”。第二頁(yè)，共四十六頁(yè)，編輯于2023年，星期三2.線索鏈表中結(jié)點(diǎn)的結(jié)構(gòu)在二叉鏈表的結(jié)點(diǎn)結(jié)構(gòu)中增加兩個(gè)標(biāo)志域，并規(guī)定：lchildLTagdataRTagrchild其中：LTag=0lchild域指示結(jié)點(diǎn)的左孩子1lchild域指示結(jié)點(diǎn)的前驅(qū)RTag=0rchild域指示結(jié)點(diǎn)的右孩子1rchild域指示結(jié)點(diǎn)的后繼第三頁(yè)，共四十六頁(yè)，編輯于2023年，星期三二叉樹二叉線索存儲(chǔ)表示typedefenum{Link,Thread}PointerThr;

//Link==0:指針，Thread==1:線索typedefstructBiThrNode{TElemTypedata;StructBiThrNode*lchild,*rchild;

//左右孩子指針

PointerThrLTag,RTag;//左右標(biāo)志}BiThrNode,*BiThrTree;第四頁(yè)，共四十六頁(yè)，編輯于2023年，星期三3.線索二叉樹圖例線索二叉樹及其存儲(chǔ)結(jié)構(gòu)（a）中序線索二叉樹（b）中序線索鏈表1234567010020131141050161171thrt0

1第五頁(yè)，共四十六頁(yè)，編輯于2023年，星期三如何在線索樹中找結(jié)點(diǎn)的后繼？結(jié)合中序線索樹若其右標(biāo)志為“1”，右鏈?zhǔn)蔷€索，右鏈直接指示了結(jié)點(diǎn)的后繼；若其右標(biāo)志為“0”，右鏈?zhǔn)侵羔?，其后繼為右子樹中最左下的結(jié)點(diǎn)。1234567第六頁(yè)，共四十六頁(yè)，編輯于2023年，星期三如何在線索樹中找結(jié)點(diǎn)的前驅(qū)？結(jié)合中序線索樹

若其左標(biāo)志為“1”，左鏈為線索，直接指示其前驅(qū)；若其左標(biāo)志為“0”，左子樹中最右下的結(jié)點(diǎn)為其前驅(qū)。1234567第七頁(yè)，共四十六頁(yè)，編輯于2023年，星期三線索鏈表的中序遍歷算法StatusIOTraver_T(BiThrTreeT,Status(*Visit)(TElemTypee)){//T指向頭結(jié)點(diǎn)，頭結(jié)點(diǎn)的左鏈lchild指向根結(jié)點(diǎn)，中序遍歷

//二叉線索樹T的非遞歸算法，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)Visit。p=T->lchild;//p指向根結(jié)點(diǎn)

while(p!=T){//空樹或遍歷結(jié)束時(shí)，p==Twhile(p->LTag==Link)p=p->lchild;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;}//IOTraver_T010020131141050161171T011第八頁(yè)，共四十六頁(yè)，編輯于2023年，星期三4.如何建立線索化鏈表？由于線索化的實(shí)質(zhì)是將二叉鏈表中的空指針改為指向前驅(qū)或后繼的線索，而前驅(qū)或后繼的信息只有在遍歷時(shí)才能得到，因此線索化的過程即為在遍歷的過程中修改空指針的過程。第九頁(yè)，共四十六頁(yè)，編輯于2023年，星期三對(duì)二叉鏈表p進(jìn)行中序線索化的遞歸算法(帶頭結(jié)點(diǎn))StatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT)步驟：1.生成頭結(jié)點(diǎn)Thrt，如果樹非空，頭結(jié)點(diǎn)指向樹根，否則，回指自身；2.pre=Thrt;調(diào)用不帶頭結(jié)點(diǎn)的中序線索化的遞歸算法;3.最后一個(gè)結(jié)點(diǎn)線索化（指向頭結(jié)點(diǎn)）第十頁(yè)，共四十六頁(yè)，編輯于2023年，星期三voidInThreading(BiThrTreep){

if(p){

InThreading(p->lchild);

//左子樹線索化

if(!p->lchild){p->lchild=pre;p->ltag=Thread;}//前驅(qū)線索

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

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

InThreading(p->rchild);

//右子樹線索化

}}InThreading

對(duì)二叉鏈表p進(jìn)行中序線索化的遞歸算法(不帶頭結(jié)點(diǎn))0100203

4050

6

7

pre0

1p第十一頁(yè)，共四十六頁(yè)，編輯于2023年，星期三StatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT){//中序遍歷二叉樹T，并將其中序線索化，Thrt指向頭結(jié)點(diǎn)。

Thrt=(BiThrTree)malloc(sizeof(BiThrNode));if(!Thrt)exit(OVERFLOW);Thrt->ltag=Link;

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

Thrt->rchild=Thrt;if(!T)Thrt->lchild=Thrt;//空樹，左指針回指自身

else{//二叉樹不為空樹，進(jìn)行線索化

Thrt->lchild=T;//頭結(jié)點(diǎn)的lchild指向二叉鏈表根

pre=Thrt;//pre指向前驅(qū)結(jié)點(diǎn)

InThreading(T);

//中序線索化二叉鏈表Tpre->rchild=Thrt;

pre->rtag=Thread;

//最后一個(gè)結(jié)點(diǎn)線索化

Thrt->rchild=pre;}returnOK;}第十二頁(yè)，共四十六頁(yè)，編輯于2023年，星期三StatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT){Thrt=(BiThrTree)malloc(sizeof(BiThrNode));

if(!Thrt)exit(OVERFLOW);Thrt->ltag=Link;Thrt->rtag=Thread;Thrt->rchild=Thrt;if(!T)Thrt->lchild=Thrt;//空樹，Thrt回指自身

ThrtLinkThread第十三頁(yè)，共四十六頁(yè)，編輯于2023年，星期三1else{Thrt->lchild=T;//頭結(jié)點(diǎn)的lchild指向二叉鏈表根

pre=Thrt;//pre指向前驅(qū)結(jié)點(diǎn)

InThreading(T);

//中序線索化二叉鏈表Tpre->rchild=Thrt;

pre->rtag=Thread;

//最后一個(gè)結(jié)點(diǎn)線索化

Thrt->rchild=pre;

}returnOK;}

ThrtABDCEpre輸出：BCAED10111110000preP=nullT第十四頁(yè)，共四十六頁(yè)，編輯于2023年，星期三ABDECFG例：對(duì)下圖的樹按先序、后序、中序線索化第十五頁(yè)，共四十六頁(yè)，編輯于2023年，星期三第6章樹和二叉樹6.1樹的定義和基本術(shù)語(yǔ)6.2二叉樹6.3遍歷二叉樹和線索二叉樹6.4樹和森林

6.4.1樹的存儲(chǔ)結(jié)構(gòu)6.4.2森林與二叉樹的轉(zhuǎn)換6.4.3樹和森林的遍歷6.6赫夫曼樹及其應(yīng)用第十六頁(yè)，共四十六頁(yè)，編輯于2023年，星期三6.4.1樹的存儲(chǔ)結(jié)構(gòu)三種常用的鏈表結(jié)構(gòu)：雙親表示法孩子表示法孩子兄弟表示法第十七頁(yè)，共四十六頁(yè)，編輯于2023年，星期三1.

雙親表示法即以一組連續(xù)空間存儲(chǔ)樹的結(jié)點(diǎn)，同時(shí)在每個(gè)結(jié)點(diǎn)中附設(shè)一個(gè)指示器指示其雙親結(jié)點(diǎn)在鏈表中的位置。DACREBFHGK雙親結(jié)點(diǎn)下標(biāo)9876543210666311000-1KHGFEDCBAR第十八頁(yè)，共四十六頁(yè)，編輯于2023年，星期三樹的雙親表存儲(chǔ)表示#defineMAX_TREE_SIZE100typedefstructPTNode{//結(jié)點(diǎn)結(jié)構(gòu)

Elemdata;intparent;//雙親位置域}PTNode;typedefstruct{//樹結(jié)構(gòu)

PTNodenodes[MAX_TREE_SIZE];intr,n;//根結(jié)點(diǎn)的位置和結(jié)點(diǎn)個(gè)數(shù)}PTree;第十九頁(yè)，共四十六頁(yè)，編輯于2023年，星期三分析：這種存儲(chǔ)結(jié)構(gòu)利用每個(gè)結(jié)點(diǎn)（除根結(jié)點(diǎn)）只有唯一雙親的性質(zhì)，Parent(T,x）操作可在常量時(shí)間內(nèi)實(shí)現(xiàn)。反復(fù)調(diào)用Parent操作，直到遇見無(wú)雙親的結(jié)點(diǎn)時(shí)，便找到了樹的根。但在這種表示方式中，求結(jié)點(diǎn)的孩子時(shí)需遍歷整個(gè)結(jié)構(gòu)。第二十頁(yè)，共四十六頁(yè)，編輯于2023年，星期三2.孩子表示法由于樹中每個(gè)結(jié)點(diǎn)可能有多棵子樹，則考慮用多重鏈表，即結(jié)點(diǎn)有多個(gè)指針域，其中每個(gè)指針指向一棵子樹的根結(jié)點(diǎn)，此時(shí)鏈表中的結(jié)點(diǎn)可以有如下兩種結(jié)點(diǎn)格式：datadegreechild1child2…childdydatachild1child2…childdx第二十一頁(yè)，共四十六頁(yè)，編輯于2023年，星期三采用第一種格式多重鏈表中的結(jié)點(diǎn)是同構(gòu)的，其中dx為樹的度。由于樹中很多結(jié)點(diǎn)的度小于dx，所以鏈表中有很多空鏈域，造成空間浪費(fèi)。datachild1child2…childdx第二十二頁(yè)，共四十六頁(yè)，編輯于2023年，星期三采用第二種格式

多重鏈表中的結(jié)點(diǎn)是不同構(gòu)的，其中

dy為結(jié)點(diǎn)的度，drgee

域的值同dy，此時(shí)可以節(jié)省存儲(chǔ)空間，但操作不方便。datadegreechild1child2…childdy第二十三頁(yè)，共四十六頁(yè)，編輯于2023年，星期三有沒有既能節(jié)省空間又操作方便的辦法呢？第二十四頁(yè)，共四十六頁(yè)，編輯于2023年，星期三另一種方式把每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)排列起來(lái)，看成是一個(gè)線性表，且以單鏈表作存儲(chǔ)結(jié)構(gòu)，則n個(gè)結(jié)點(diǎn)有n個(gè)孩子鏈表（葉子的孩子鏈表為空)。而n個(gè)頭指針又組成一個(gè)線性表，為便于查找，采用順序存儲(chǔ)結(jié)構(gòu)。第二十五頁(yè)，共四十六頁(yè)，編輯于2023年，星期三3^6^51^2078^9^K^H^G^EFR^DC^BA0123456789DACREBFHGK第二十六頁(yè)，共四十六頁(yè)，編輯于2023年，星期三樹的孩子鏈表存儲(chǔ)表示typedefstructCTNode

{//孩子結(jié)點(diǎn)intchild;structCTNode*next;}*ChildPtr;typedefstruct{//雙親結(jié)點(diǎn)結(jié)構(gòu)Elemdata;

ChildPtrfirstchild;//孩子鏈的頭指針}CTBox;typedefstruct{//樹結(jié)構(gòu):

CTBoxnodes[MAX_TREE_SIZE];intn,r;//結(jié)點(diǎn)數(shù)和根結(jié)點(diǎn)的位置}CTree;第二十七頁(yè)，共四十六頁(yè)，編輯于2023年，星期三分析：與雙親表示法相反，孩子表示法便于涉及孩子的操作實(shí)現(xiàn)，卻不適用于Parent(T，x)操作?？筛鶕?jù)某種需要，將二者結(jié)合起來(lái)，即帶雙親的孩子鏈表。第二十八頁(yè)，共四十六頁(yè)，編輯于2023年，星期三3.孩子兄弟表示法或稱二叉樹表示法，或稱二叉鏈表表示法。即以二叉鏈表作樹的存儲(chǔ)結(jié)構(gòu)。鏈表中結(jié)點(diǎn)的兩個(gè)鏈域分別指向該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)。第二十九頁(yè)，共四十六頁(yè)，編輯于2023年，星期三^R^E^^K^^C^FAB^G^H^D^DACREBFHGK3.孩子兄弟表示法例：第三十頁(yè)，共四十六頁(yè)，編輯于2023年，星期三樹的二叉鏈表（孩子-兄弟）存儲(chǔ)表示typedefstructCSNode{Elemdata;structCSNode*firstchild,*nextsibling;}CSNode,*CSTree;第三十一頁(yè)，共四十六頁(yè)，編輯于2023年，星期三分析：這種存儲(chǔ)結(jié)構(gòu)便于實(shí)現(xiàn)各種樹的操作。首先易于實(shí)現(xiàn)找結(jié)點(diǎn)孩子等的操作。如果為每個(gè)結(jié)點(diǎn)增設(shè)一個(gè)(parent)域，則同樣能方便地實(shí)現(xiàn)Parent(T,x)操作。第三十二頁(yè)，共四十六頁(yè)，編輯于2023年，星期三6.4.2森林和二叉樹的轉(zhuǎn)換1.樹和二叉樹的對(duì)應(yīng)關(guān)系由于二叉樹和樹都可用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，則以二叉鏈表作為媒介可導(dǎo)出樹與二叉樹之間的一個(gè)對(duì)應(yīng)關(guān)系。第三十三頁(yè)，共四十六頁(yè)，編輯于2023年，星期三第三十四頁(yè)，共四十六頁(yè)，編輯于2023年，星期三樹轉(zhuǎn)換為二叉樹方法：1）對(duì)每個(gè)孩子進(jìn)行從左到右的排序；2）在兄弟之間加一條連線；3）對(duì)每個(gè)結(jié)點(diǎn)，除了左孩子外，去除其與其余孩子之間的聯(lián)系；4）以根結(jié)點(diǎn)為軸心，將整個(gè)樹順時(shí)針轉(zhuǎn)45°。第三十五頁(yè)，共四十六頁(yè)，編輯于2023年，星期三ABCDEGHFIaABCDEGHFIbABCDEGHFIcABCDEGHFId第三十六頁(yè)，共四十六頁(yè)，編輯于2023年，星期三2.森林和二叉樹的對(duì)應(yīng)關(guān)系從樹的二叉鏈表表示的定義可知，任何一棵和樹對(duì)應(yīng)的二叉樹，其右子樹必空。若把森林中第二棵樹的根結(jié)點(diǎn)看成是第一棵樹的根結(jié)點(diǎn)的兄弟，則同樣可導(dǎo)出森林和二叉樹的對(duì)應(yīng)關(guān)系。第三十七頁(yè)，共四十六頁(yè)，編輯于2023年，星期三第三十八頁(yè)，共四十六頁(yè)，編輯于2023年，星期三BCDEGHFIaBCDEGHFIbBCDEGHFIcBCDEGHFId第三十九頁(yè)，共四十六頁(yè)，編輯于2023年，星期三已知條件：森林和二叉樹的對(duì)應(yīng)關(guān)系設(shè)森林F=(T1,T2,…,Tn);T1=(root，t11,t12,…,t1m);

二叉樹B=(LBT,Node(root),RBT);由森林轉(zhuǎn)換成二叉樹的轉(zhuǎn)換規(guī)則為:若F=Φ，則B=Φ;否則，由Root(T1)對(duì)應(yīng)得到Node(root);

由(t11,t12,…,t1m)對(duì)應(yīng)得到LBT;

由(T2,T3,…,Tn)對(duì)應(yīng)得到RBT。由二叉樹轉(zhuǎn)換為森林的轉(zhuǎn)換規(guī)則為:若B=Φ,則F=Φ;否則，由Node(root)對(duì)應(yīng)得到Root(T1);

由LBT對(duì)應(yīng)得到(t11,t12,…，t1m);T1除根以外所構(gòu)成的森林由RBT對(duì)應(yīng)得到(T2,T3,…,Tn)；除T1之外的森林第四十頁(yè)，共四十六頁(yè)，編輯于2023年，星期三6.4.3樹和森林的遍歷1.樹的遍歷：有三條搜索路徑先根(序)遍歷：若樹不空，則先訪問根結(jié)點(diǎn)，然后依次先根遍歷各棵子樹。后根(序)遍歷：若樹不空，則先依次后根遍歷各棵子樹，然后訪問根結(jié)點(diǎn)。按層次遍歷：若樹不空，則自上而下自左至右訪問樹中每個(gè)結(jié)點(diǎn)。第四十一頁(yè)，共四十六頁(yè)，編輯于2023年，星期三例對(duì)樹進(jìn)行先根遍歷，獲得的先根序列是：對(duì)樹進(jìn)行后根遍歷，獲得的后根序列是：ABCDEGHFIABEFCDGH