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

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

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

//左右孩子指針

PointerThrLTag,RTag;//左右標志}BiThrNode,*BiThrTree;第4頁，共46頁，2023年，2月20日，星期六3.線索二叉樹圖例線索二叉樹及其存儲結(jié)構(gòu)（a）中序線索二叉樹（b）中序線索鏈表1234567010020131141050161171thrt0

1第5頁，共46頁，2023年，2月20日，星期六如何在線索樹中找結(jié)點的后繼？結(jié)合中序線索樹若其右標志為“1”，右鏈是線索，右鏈直接指示了結(jié)點的后繼；若其右標志為“0”，右鏈是指針，其后繼為右子樹中最左下的結(jié)點。1234567第6頁，共46頁，2023年，2月20日，星期六如何在線索樹中找結(jié)點的前驅(qū)？結(jié)合中序線索樹

若其左標志為“1”，左鏈為線索，直接指示其前驅(qū)；若其左標志為“0”，左子樹中最右下的結(jié)點為其前驅(qū)。1234567第7頁，共46頁，2023年，2月20日，星期六線索鏈表的中序遍歷算法StatusIOTraver_T(BiThrTreeT,Status(*Visit)(TElemTypee)){//T指向頭結(jié)點，頭結(jié)點的左鏈lchild指向根結(jié)點，中序遍歷

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

while(p!=T){//空樹或遍歷結(jié)束時，p==Twhile(p->LTag==Link)p=p->lchild;if(!Visit(p->data))returnERROR;//訪問其左子樹為空的結(jié)點while(p->RTag==Thread&&p->rchild!=T){p=p->rchild;Visit(p->data);}//訪問后繼結(jié)點p=p->rchild;}returnOK;}//IOTraver_T010020131141050161171T011第8頁，共46頁，2023年，2月20日，星期六4.如何建立線索化鏈表？由于線索化的實質(zhì)是將二叉鏈表中的空指針改為指向前驅(qū)或后繼的線索，而前驅(qū)或后繼的信息只有在遍歷時才能得到，因此線索化的過程即為在遍歷的過程中修改空指針的過程。第9頁，共46頁，2023年，2月20日，星期六對二叉鏈表p進行中序線索化的遞歸算法(帶頭結(jié)點)StatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT)步驟：1.生成頭結(jié)點Thrt，如果樹非空，頭結(jié)點指向樹根，否則，回指自身；2.pre=Thrt;調(diào)用不帶頭結(jié)點的中序線索化的遞歸算法;3.最后一個結(jié)點線索化（指向頭結(jié)點）第10頁，共46頁，2023年，2月20日，星期六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

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

4050

6

7

pre0

1p第11頁，共46頁，2023年，2月20日，星期六StatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT){//中序遍歷二叉樹T，并將其中序線索化，Thrt指向頭結(jié)點。

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

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

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

else{//二叉樹不為空樹，進行線索化

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

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

InThreading(T);

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

pre->rtag=Thread;

//最后一個結(jié)點線索化

Thrt->rchild=pre;}returnOK;}第12頁，共46頁，2023年，2月20日，星期六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第13頁，共46頁，2023年，2月20日，星期六1else{Thrt->lchild=T;//頭結(jié)點的lchild指向二叉鏈表根

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

InThreading(T);

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

pre->rtag=Thread;

//最后一個結(jié)點線索化

Thrt->rchild=pre;

}returnOK;}

ThrtABDCEpre輸出：BCAED10111110000preP=nullT第14頁，共46頁，2023年，2月20日，星期六ABDECFG例：對下圖的樹按先序、后序、中序線索化第15頁，共46頁，2023年，2月20日，星期六第6章樹和二叉樹6.1樹的定義和基本術(shù)語6.2二叉樹6.3遍歷二叉樹和線索二叉樹6.4樹和森林

6.4.1樹的存儲結(jié)構(gòu)6.4.2森林與二叉樹的轉(zhuǎn)換6.4.3樹和森林的遍歷6.6赫夫曼樹及其應用第16頁，共46頁，2023年，2月20日，星期六6.4.1樹的存儲結(jié)構(gòu)三種常用的鏈表結(jié)構(gòu)：雙親表示法孩子表示法孩子兄弟表示法第17頁，共46頁，2023年，2月20日，星期六1.

雙親表示法即以一組連續(xù)空間存儲樹的結(jié)點，同時在每個結(jié)點中附設一個指示器指示其雙親結(jié)點在鏈表中的位置。DACREBFHGK雙親結(jié)點下標9876543210666311000-1KHGFEDCBAR第18頁，共46頁，2023年，2月20日，星期六樹的雙親表存儲表示#defineMAX_TREE_SIZE100typedefstructPTNode{//結(jié)點結(jié)構(gòu)

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

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

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

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

域的值同dy，此時可以節(jié)省存儲空間，但操作不方便。datadegreechild1child2…childdy第23頁，共46頁，2023年，2月20日，星期六有沒有既能節(jié)省空間又操作方便的辦法呢？第24頁，共46頁，2023年，2月20日，星期六另一種方式把每個結(jié)點的孩子結(jié)點排列起來，看成是一個線性表，且以單鏈表作存儲結(jié)構(gòu)，則n個結(jié)點有n個孩子鏈表（葉子的孩子鏈表為空)。而n個頭指針又組成一個線性表，為便于查找，采用順序存儲結(jié)構(gòu)。第25頁，共46頁，2023年，2月20日，星期六3^6^51^2078^9^K^H^G^EFR^DC^BA0123456789DACREBFHGK第26頁，共46頁，2023年，2月20日，星期六樹的孩子鏈表存儲表示typedefstructCTNode

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

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

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

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

由(t11,t12,…,t1m)對應得到LBT;

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

由LBT對應得到(t11,t12,…，t1m);T1除根以外所構(gòu)成的森林由RBT對應得到(T2,T3,…,Tn)；除T1之外的森林第40頁，共46頁，2023年，2月20日，星期六6.4.3樹和森林的遍歷1.樹的遍歷：有三條搜索路徑先根(序)遍歷：若樹不空，則先訪問根結(jié)點，然后依次先根遍歷各棵子樹。后根(序)遍歷：若樹不空，則先依次后根遍歷各棵子樹，然后訪問根結(jié)點。按層次遍歷：若樹不空，則自上而下自左至右訪問樹中每個結(jié)點。第41頁，共46頁，2023年，2月20日，星期六例對樹進行先根遍歷，獲得的先根序列是：對樹進行后根遍歷，獲得的后根序列是：ABCDEGHFIABEFCDG