1、會計學1數據結構線索數據結構線索(xin su)樹與樹和森林樹與樹和森林第一頁，共46頁。稱為稱為“線索化線索化”。第1頁/共46頁第二頁，共46頁。lchildLTagdataRTag rchild其中其中(qzhng)(qzhng)：LTag =LTag =0 lchild 0 lchild 域指示結點的左孩子域指示結點的左孩子1 lchild 1 lchild 域指示結點的前驅域指示結點的前驅RTag =RTag =0 rchild 0 rchild 域指示結點的右孩子域指示結點的右孩子1 rchild 1 rchild 域指示結點的后繼域指示結點的后繼第2頁/共46頁第三頁，共46頁。

2、第3頁/共46頁第四頁，共46頁。3.3.線索線索(xin su)(xin su)二二叉樹圖例叉樹圖例 線索二叉樹及其存儲線索二叉樹及其存儲(cn ch)(cn ch)結構結構 （a a）中序線索二叉樹）中序線索二叉樹 （b b）中序線索鏈表）中序線索鏈表12345670 1 00 2 01 3 11 4 10 5 01 6 11 7 1thrt0 1第4頁/共46頁第五頁，共46頁。結合中序線索結合中序線索(xin su)(xin su)樹樹 若其右標志為若其右標志為“1”“1”，右鏈是線索，右鏈是線索(xin su)(xin su)，右鏈直接指示了結點的后繼；，右鏈直接指示了結點的后繼；

3、若其右標志為若其右標志為“0”“0”，右鏈是指針，其后繼為，右鏈是指針，其后繼為右子樹中最左下的結點。右子樹中最左下的結點。1234567第5頁/共46頁第六頁，共46頁。結合結合(jih)(jih)中序線索樹中序線索樹 若其左標志為若其左標志為“1”“1”，左鏈為線索，直接指示，左鏈為線索，直接指示其前驅；其前驅； 若其左標志為若其左標志為“0”“0”，左子樹中最右下的結點，左子樹中最右下的結點為其前驅。為其前驅。1234567第6頁/共46頁第七頁，共46頁。線索鏈表的中序遍歷算法線索鏈表的中序遍歷算法Status IOTraver_T( BiThrTree T,Status Status

4、 IOTraver_T( BiThrTree T,Status ( (* *Visit)(TElemType e) )Visit)(TElemType e) ) /T /T指向頭結點，頭結點的左鏈指向頭結點，頭結點的左鏈lchildlchild指向根結點，中指向根結點，中序遍歷序遍歷 / /二叉線索樹二叉線索樹T T的非遞歸算法，對每個數據元素調用函數的非遞歸算法，對每個數據元素調用函數VisitVisit。 p = T-lchild; /p p = T-lchild; /p指向根結點指向根結點 while (p != T) / while (p != T) /空樹或遍歷結束時，空樹或遍歷結束

5、時，p = = Tp = = T while (p-LTag=Link) p = p-lchild; while (p-LTag=Link) p = p-lchild; if (!Visit(p-data) return ERROR; / if (!Visit(p-data) return ERROR; /訪問訪問(fngwn)(fngwn)其左子樹為空的結點其左子樹為空的結點 while (p-RTag=Thread & p-rchild!=T) while (p-RTag=Thread & p-rchild!=T) p = p-rchild; Visit(p-data);

6、/ p = p-rchild; Visit(p-data); /訪問訪問(fngwn)(fngwn)后繼結點后繼結點 p = p-rchild; p = p-rchild; return OK; return OK; / IOTraver_T / IOTraver_T0 1 00 2 01 3 11 4 10 5 01 6 11 7 1T0 1 1第7頁/共46頁第八頁，共46頁。第8頁/共46頁第九頁，共46頁。1. 1. 生成頭結點生成頭結點(ji din)Thrt(ji din)Thrt，如果樹非空，頭結點，如果樹非空，頭結點(ji (ji din)din)指向樹根，否則，回指自身；指向

7、樹根，否則，回指自身；2. pre = Thrt; 2. pre = Thrt; 調用不帶頭結點的中序線索化的遞歸算法調用不帶頭結點的中序線索化的遞歸算法; ;3.3.最后一個結點線索化（指向頭結點）最后一個結點線索化（指向頭結點）第9頁/共46頁第十頁，共46頁。0 1 00 2 0 3 40 5 0 6 7 pre0 1p第10頁/共46頁第十一頁，共46頁。第11頁/共46頁第十二頁，共46頁。 ThrtLinkThread第12頁/共46頁第十三頁，共46頁。1 Thrt A B D C Epre輸出輸出(shch)：B C A E D1 10111110000preP=nullT第1

8、3頁/共46頁第十四頁，共46頁。ABDECFG例：對下圖的樹按先序、后序例：對下圖的樹按先序、后序(hu x)、中序、中序線索化線索化第14頁/共46頁第十五頁，共46頁。第第6 6章章 樹和二叉樹樹和二叉樹6.1 6.1 樹的定義和基本樹的定義和基本(jbn)(jbn)術語術語6.2 6.2 二叉樹二叉樹6.3 6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹6.4 6.4 樹和森林樹和森林 樹的存儲結構樹的存儲結構 森林與二叉樹的轉換森林與二叉樹的轉換 樹和森林的遍歷樹和森林的遍歷6.6 6.6 赫夫曼樹及其應用赫夫曼樹及其應用第15頁/共46頁第十六頁，共46頁。第16頁/共46頁

9、第十七頁，共46頁。1. 1. 雙親表示法雙親表示法即以一組連續空間存儲樹的結點，即以一組連續空間存儲樹的結點，同時在每個結點中附設一個同時在每個結點中附設一個(y )(y )指示指示器器指示其雙親結點在鏈表中的位置。指示其雙親結點在鏈表中的位置。D DA AC CR RE EB BF FH HG GK K雙親雙親結點結點下標下標9 98 87 76 65 54 43 32 21 10 06 66 66 63 31 11 10 00 00 0-1-1K KH HG GF FE ED DC CB BA AR R第17頁/共46頁第十八頁，共46頁。樹的雙親表存儲樹的雙親表存儲(cn ch)(cn

10、 ch)表示表示#define MAX_TREE_SIZE 100 #define MAX_TREE_SIZE 100 typedef struct PTNode /typedef struct PTNode /結點結構結點結構 Elem data; Elem data; int parent; / int parent; / 雙親位置域雙親位置域 PTNode; PTNode;typedef struct /typedef struct /樹結構樹結構 PTNode nodesMAX_TREE_SIZE; PTNode nodesMAX_TREE_SIZE; int r, n; / int

11、r, n; / 根結點的位置和結點個根結點的位置和結點個數數 PTree; PTree;第18頁/共46頁第十九頁，共46頁。分析：分析： 這種存儲結構利用每個結點這種存儲結構利用每個結點(ji din)(ji din)（除根結點除根結點(ji din)(ji din)）只有唯一雙親的性質，）只有唯一雙親的性質，Parent(T,xParent(T,x）操作可在常量時間內實現。反復）操作可在常量時間內實現。反復調用調用ParentParent操作，直到遇見無雙親的結點操作，直到遇見無雙親的結點(ji (ji din)din)時，便找到了樹的根。但在這種表示方時，便找到了樹的根。但在這種表示方式

12、中，求結點式中，求結點(ji din)(ji din)的孩子時需遍歷整個的孩子時需遍歷整個結構。結構。第19頁/共46頁第二十頁，共46頁。2. 2. 孩子表示法孩子表示法 由于樹中每個結點可能有多棵子樹，則由于樹中每個結點可能有多棵子樹，則考慮用多重鏈表，即結點有多個指針考慮用多重鏈表，即結點有多個指針(zhzhn)(zhzhn)域，其中每個指針域，其中每個指針(zhzhn)(zhzhn)指向指向一棵子樹的根結點，此時鏈表中的結點可以一棵子樹的根結點，此時鏈表中的結點可以有如下兩種結點格式：有如下兩種結點格式：datadatadegreedegreechild1child1child2chi

13、ld2childchildd dy ydatadatachild1child1child2child2childchildd dx x第20頁/共46頁第二十一頁，共46頁。采用采用(ciyng)(ciyng)第一種格式第一種格式 多重鏈表中的結點是同構的，其中多重鏈表中的結點是同構的，其中 dx dx 為樹的度。為樹的度。由于樹中很多結點的度小于由于樹中很多結點的度小于 dx dx ，所以鏈表中有很多空，所以鏈表中有很多空鏈域，造成空間浪費。鏈域，造成空間浪費。datadatachild1child1child2child2childchildd dx x第21頁/共46頁第二十二頁，共46

14、頁。采用第二種格式采用第二種格式 多重鏈表中的結點是不同構的，其中多重鏈表中的結點是不同構的，其中(qzhng) dy (qzhng) dy 為結點的度，為結點的度，drgee drgee 域的值同域的值同 dy dy ，此時可以節省存儲，此時可以節省存儲空間，但操作不方便。空間，但操作不方便。datadatadegreedegreechild1child1child2child2childchildd dy y第22頁/共46頁第二十三頁，共46頁。有沒有既能節省有沒有既能節省(jishng)空間空間又操作方便的辦法呢？又操作方便的辦法呢？第23頁/共46頁第二十四頁，共46頁。另一種方式另

15、一種方式(fngsh)(fngsh) 把每個結點的孩子結點排列起來，看成是一個線把每個結點的孩子結點排列起來，看成是一個線性表，且以單鏈表作存儲結構，則性表，且以單鏈表作存儲結構，則 n n個結點有個結點有 n n 個個孩子鏈表（葉子的孩子鏈表為空孩子鏈表（葉子的孩子鏈表為空) )。而。而 n n 個頭指針又個頭指針又組成一個線性表，為便于查找，采用順序存儲結構。組成一個線性表，為便于查找，采用順序存儲結構。第24頁/共46頁第二十五頁，共46頁。3 36 65 51 12 20 07 78 89 9K KH HG GE EF FR RD DC CB BA A0 01 12 23 34 45

16、56 67 78 89 9D DA AC CR RE EB BF FH HG GK K第25頁/共46頁第二十六頁，共46頁。樹的孩子鏈表存儲表示樹的孩子鏈表存儲表示(biosh)(biosh)typedef struct CTNode /typedef struct CTNode /孩子結點孩子結點 int child; int child; struct CTNode struct CTNode * *next; next; * *ChildPtr;ChildPtr;typedef struct typedef struct / /雙親結點結構雙親結點結構 Elem data; Elem

17、data; ChildPtr firstchild; / ChildPtr firstchild; / 孩子鏈的頭指針孩子鏈的頭指針 CTBox; CTBox;typedef struct /typedef struct /樹結構樹結構: : CTBox nodesMAX_TREE_SIZE; CTBox nodesMAX_TREE_SIZE; int n, r; / int n, r; / 結點數和根結點的位置結點數和根結點的位置 CTree; CTree;第26頁/共46頁第二十七頁，共46頁。分析：分析： 與雙親表示法相反，孩子表示法便于涉及孩子與雙親表示法相反，孩子表示法便于涉及孩子的

18、操作實現的操作實現(shxin)(shxin)，卻不適用于，卻不適用于Parent(TParent(T，x)x)操作?？筛鶕撤N需要，將二者結合起來，即帶雙操作?？筛鶕撤N需要，將二者結合起來，即帶雙親的孩子鏈表。親的孩子鏈表。第27頁/共46頁第二十八頁，共46頁。3. 3. 孩子兄弟表示法孩子兄弟表示法 或稱二叉樹表示法，或稱二叉鏈表表示法?；蚍Q二叉樹表示法，或稱二叉鏈表表示法。即以二叉鏈表作樹的存儲結構。鏈表中結點的兩即以二叉鏈表作樹的存儲結構。鏈表中結點的兩個個(lin )(lin )鏈域分別指向該結點的第一個孩子鏈域分別指向該結點的第一個孩子結點和下一個兄弟結點。結點和下一個兄弟結點

19、。第28頁/共46頁第二十九頁，共46頁。REKCFABGHDD DA AC CR RE EB BF FH HG GK K3. 3. 孩子孩子(hi zi)(hi zi)兄弟兄弟表示法表示法例：例：第29頁/共46頁第三十頁，共46頁。樹的二叉鏈表（孩子樹的二叉鏈表（孩子 - - 兄弟）存儲兄弟）存儲(cn ch)(cn ch)表表示示typedef struct CSNode typedef struct CSNode Elem data; Elem data; struct CSNode struct CSNode * *firstchild ,firstchild , * *nextsi

20、bling;nextsibling; CSNode, CSNode, * *CSTree;CSTree;第30頁/共46頁第三十一頁，共46頁。分析：分析： 這種存儲結構便于實現各種樹的操作。首先易于這種存儲結構便于實現各種樹的操作。首先易于實現找結點孩子等的操作。如果為每個結點增設一個實現找結點孩子等的操作。如果為每個結點增設一個(parent)(parent)域，則同樣域，則同樣(tngyng)(tngyng)能方便地實現能方便地實現Parent(T,x)Parent(T,x)操作。操作。第31頁/共46頁第三十二頁，共46頁。關系。關系。第32頁/共46頁第三十三頁，共46頁。第33頁/

21、共46頁第三十四頁，共46頁。樹轉換樹轉換(zhunhun)(zhunhun)為二叉為二叉樹方法：樹方法：1 1）對每個孩子進行從左到右的排序；）對每個孩子進行從左到右的排序；2 2）在兄弟之間加一條連線；）在兄弟之間加一條連線；3 3）對每個結點，除了左孩子外，去除其與其余）對每個結點，除了左孩子外，去除其與其余孩子之間的聯系孩子之間的聯系(linx)(linx)； 4 4）以根結點為軸心，將整個樹順時針轉）以根結點為軸心，將整個樹順時針轉4545。第34頁/共46頁第三十五頁，共46頁。ABCDEGHFIa aABCDEGHFIb bABCDEGHFIc cABCDEGHFId d第35頁

22、/共46頁第三十六頁，共46頁。2. 2. 森林和二叉樹的對應關系森林和二叉樹的對應關系 從樹的二叉鏈表表示從樹的二叉鏈表表示(biosh)(biosh)的定義可的定義可知，任何一棵和樹對應的二叉樹，其右子樹知，任何一棵和樹對應的二叉樹，其右子樹必空。必空。 若把森林中第二棵樹的根結點看成是第若把森林中第二棵樹的根結點看成是第一棵樹的根結點的兄弟，則同樣可導出森林一棵樹的根結點的兄弟，則同樣可導出森林和二叉樹的對應關系。和二叉樹的對應關系。第36頁/共46頁第三十七頁，共46頁。第37頁/共46頁第三十八頁，共46頁。BCDEGHFIa aBCDEGHFIb bBCDEGHFIc cBCDEGHFId d第38頁/共46頁第三十九頁，共46頁。第39頁/共46頁第四十頁，共46頁。后訪問根結點。后訪問根結點。按層次按層次(cngc)(cngc)遍歷：遍歷：若樹若樹不空，則自上而下自左至不空，則自上而下自左至右訪問樹中每右訪問樹中每個結點。個結點。第40頁/共46頁第四十一頁，共46頁。例例對樹進行對樹進行(jnxng)(jnxng)先根遍歷，獲得的先先根遍歷，獲得的先根序列是：根序列是：對樹進行對樹進行(jnxng)(jnxng)后