數據結構第講線索樹與樹和森林

數據結構第講線索樹與樹和森林第1頁，共46頁，2023年，2月20日，星期六6.3.2線索二叉樹1.何謂線索二叉樹？遍歷結果是求得結點的一個線性序列。指向該線性序列“前驅”和“后繼”的指針，稱“線索”；包含“線索”的存儲結構，稱為“線索鏈表”；與其相應的二叉樹，稱為“線索二叉樹”；對二叉樹以某種次序遍歷，使其變?yōu)榫€索二叉樹的過程，稱為“線索化”。第2頁，共46頁，2023年，2月20日，星期六2.線索鏈表中結點的結構在二叉鏈表的結點結構中增加兩個標志域，并規(guī)定：lchildLTagdataRTagrchild其中：LTag=0lchild域指示結點的左孩子1lchild域指示結點的前驅RTag=0rchild域指示結點的右孩子1rchild域指示結點的后繼第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.線索二叉樹圖例線索二叉樹及其存儲結構（a）中序線索二叉樹（b）中序線索鏈表1234567010020131141050161171thrt0

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

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

//二叉線索樹T的非遞歸算法，對每個數據元素調用函數Visit。p=T->lchild;//p指向根結點

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

if(p){

InThreading(p->lchild);

//左子樹線索化

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

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

pre=p;//保持pre指向p的前驅

InThreading(p->rchild);

//右子樹線索化

}}InThreading

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

4050

6

7

pre0

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

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

Thrt->rtag=Thread;//建立頭結點

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

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

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

pre=Thrt;//pre指向前驅結點

InThreading(T);

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

pre->rtag=Thread;

//最后一個結點線索化

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;//頭結點的lchild指向二叉鏈表根

pre=Thrt;//pre指向前驅結點

InThreading(T);

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

pre->rtag=Thread;

//最后一個結點線索化

Thrt->rchild=pre;

}returnOK;}

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

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

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

Elemdata;intparent;//雙親位置域}PTNode;typedefstruct{//樹結構

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

多重鏈表中的結點是不同構的，其中

dy為結點的度，drgee

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

{//孩子結點intchild;structCTNode*next;}*ChildPtr;typedefstruct{//雙親結點結構Elemdata;

ChildPtrfirstchild;//孩子鏈的頭指針}CTBox;typedefstruct{//樹結構:

CTBoxnodes[MAX_TREE_SIZE];intn,r;//結點數和根結點的位置}CTree;第27頁，共46頁，2023年，2月20日，星期六分析：與雙親表示法相反，孩子表示法便于涉及孩子的操作實現，卻不適用于Parent(T，x)操作。可根據某種需要，將二者結合起來，即帶雙親的孩子鏈表。第28頁，共46頁，2023年，2月20日，星期六3.孩子兄弟表示法或稱二叉樹表示法，或稱二叉鏈表表示法。即以二叉鏈表作樹的存儲結構。鏈表中結點的兩個鏈域分別指向該結點的第一個孩子結點和下一個兄弟結點。第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日，星期六分析：這種存儲結構便于實現各種樹的操作。首先易于實現找結點孩子等的操作。如果為每個結點增設一個(parent)域，則同樣能方便地實現Parent(T,x)操作。第32頁，共46頁，2023年，2月20日，星期六6.4.2森林和二叉樹的轉換1.樹和二叉樹的對應關系由于二叉樹和樹都可用二叉鏈表作為存儲結構，則以二叉鏈表作為媒介可導出樹與二叉樹之間的一個對應關系。第33頁，共46頁，2023年，2月20日，星期六第34頁，共46頁，2023年，2月20日，星期六樹轉換為二叉樹方法：1）對每個孩子進行從左到右的排序；2）在兄弟之間加一條連線；3）對每個結點，除了左孩子外，去除其與其余孩子之間的聯(lián)系；4）以根結點為軸心，將整個樹順時針轉45°。第35頁，共46頁，2023年，2月20日，星期六ABCDEGHFIaABCDEGHFIbABCDEGHFIcABCDEGHFId第36頁，共46頁，2023年，2月20日，星期六2.森林和二叉樹的對應關系從樹的二叉鏈表表示的定義可知，任何一棵和樹對應的二叉樹，其右子樹必空。若把森林中第二棵樹的根結點看成是第一棵樹的根結點的兄弟，則同樣可導出森林和二叉樹的對應關系。第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);由森林轉換成二叉樹的轉換規(guī)則為:若F=Φ，則B=Φ;否則，由Root(T1)對應得到Node(root);

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

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

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