DS06樹和二叉樹03線索二叉樹樹和森林

1、DS06樹和二叉樹03線索二叉樹樹和森林DBCEFAECBDF二叉鏈表lchilddatarchildA何謂線索二叉樹？Threaded Binary Tree線索二叉樹：指加上線索的，原有的空左孩子域指向前驅，原有的空右孩子指向后繼的二叉樹指向結點“前驅和“后繼的指針，稱“線索；對二叉樹以某種次序遍歷，使其變?yōu)榫€索二叉樹的過程，稱為“線索化。在二叉鏈表的結點構造中增加兩個標志域，并規(guī)定：lchildLTagdataRTagrchild其中：LTag =0 lchild 域指向左孩子1 lchild 域指向前驅RTag =0 rchild 域指向右孩子1 rchild 域指向后繼二叉樹的二叉線

2、索存儲表示/ Link=0:指針，Thread=1:線索typedef enum Link, Thread PointerTag; typedef struct BiThrNode TElemType data; struct BiThrNode *lchild, *rchild; / 左右孩子指針 PointerTag LTag, RTag; / 左右標志 BiThrNode, *BiThrTree; 二叉樹的遍歷方式有4種，故有4種意義下的前驅和后繼，相應的有4種線索二叉樹： 前序線索二叉樹 中序線索二叉樹 后序線索二叉樹 層序線索二叉樹線索二叉樹a中序線索二叉樹 b中序線索鏈表12345

3、670 1 00 2 01 3 11 4 10 5 01 6 11 7 1thrt0 1中序序列：4 2 6 5 7 1 3頭指針 頭結點添加頭結點后，好比為二叉樹建立了一個雙向線索鏈表，即可以從第一個結點起順后繼進展遍歷，也可以從最后一個結點起順前驅進展遍歷。NULLNULL為使算法設計方便，增加一個頭結點。如何在中序線索樹中找結點的后繼？ 假設其右標志為“1，右鏈是線索，右鏈直接指向后繼；比方4、6、7 假設其右標志為“0，右鏈是指針，其后繼應為遍歷其右子樹時第一個訪問的結點，即右子樹中最左下的結點。比方2的后繼為61234567如何在中序線索樹中找結點的前驅？ 假設其左標志為“1，左鏈為

4、線索，直接指向前驅；比方3、6、7 假設其左標志為“0，前驅應為遍歷左子樹時最后訪問的一個結點，即左子樹中最右下的結點。比方1的前驅為7、2的前驅為4、5的前驅為61234567如何在后序線索樹中找結點的后繼或者如何在前序線索樹中找結點的前驅？在后序線索樹中找結點后繼較復雜，P133，需知道結點雙親，即需帶指向其雙親結點的指針域的三叉鏈表作存儲構造。同理，在前序線索樹中找結點前驅也需知道結點雙親。根據(jù)剛剛的分析，可以看出，在中序線索鏈表上遍歷二叉樹，要比在二叉鏈表上中序遍歷高效，雖時間還是O (n)，但常數(shù)因子比上節(jié)的非遞歸遍歷算法小，且不需設棧。 Status InOrderTraver_T

5、hr( BiThrTree T,Status (*Visit)(TElemType e) ) / 中序遍歷二叉線索樹T的非遞歸算法，對每個數(shù)據(jù)元素調用函數(shù)Visit。/ T指向頭結點，頭結點的左鏈lchild指向根結點， p = T-lchild; /p指向根結點 while (p != T) /空樹或遍歷完畢時，p = = T while (p-LTag=Link) p = p-lchild; / p指向最左下結點， /即中序遍歷的第一個結點 if (!Visit(p-data) return ERROR; /訪問第一個結點 while (p-RTag=Thread & p-rchild!=

6、T) p = p-rchild; Visit(p-data); /順線索訪問后繼結點 p = p-rchild; return OK; 0 1 00 2 01 3 11 4 10 5 01 6 11 7 1T0 1 1 Thrt空樹01分析：建立線索鏈表，本質上就是在遍歷的過程中將二叉鏈表中的空指針改為指向前驅或后繼的線索。4.如何建立線索化鏈表？對二叉鏈表T進展中序線索化的遞歸算法(帶頭結點)Status InOrderThreading(BiThrTree &Thrt, BiThrTree T)步驟：1. 生成頭結點Thrt，假設樹非空，左孩子指向樹根，否那么，回指自身；2. pre =

7、Thrt; 調用不帶頭結點的中序線索化的遞歸算法;3. 最后一個結點線索化指向頭結點1 A B D C E111110000T/中序遍歷二叉鏈表T，并將其中序線索化，Thrt指向頭結點。Status InOrderThreading(BiThrTree &Thrt, BiThrTree T) / 建立頭結點Thrt = (BiThrTree)malloc(sizeof(BiThrNode); if (!Thrt) exit(OVERFLOW); Thrt-ltag = Link; Thrt-rtag = Thread; Thrt-rchild = Thrt; / 右指針回指 if (!T) /

8、空樹，左指針回指Thrt-lchild = Thrt; ThrtLinkThread011else / 非空樹，進展線索化 Thrt-lchild = T;/ 頭結點的lchild指向二叉鏈表根 pre = Thrt; / pre指向T的前驅 InThreading(T);/ 中序線索化二叉鏈表T pre-rchild = Thrt; / 最后一個結點線索化pre-rtag = Thread; Thrt-rchild = pre; return OK; Thrt A B D C Epre輸出：B C A E D10111110000preTvoid InThreading(BiThrTree

9、p)if (p)InThreading(p-lchild); /左子樹線索化 / 此時p所指結點的左子樹不存在或已線索化if (!p-lchild) /左孩子為空，建立p所指結點的前驅線索 p-lchild=pre; p-ltag=Thread; if (!pre-rchild) /右孩子為空，建立pre所指結點的后繼線索 pre-rchild=p;pre-rtag=Thread; pre = p; /保持pre指向p的前驅 InThreading(p-rchild); /右子樹線索化 對二叉鏈表p進展中序線索化的遞歸算法(不帶頭結點)1 Thrt A B D C Epre1011111000

10、0prepABDECFG例：對以以下圖的樹按先序、后序、中序線索化第6章 樹和二叉樹6.1 樹的定義和根本術語6.2 二叉樹6.3 遍歷二叉樹和線索二叉樹6.4 樹和森林 6.4.1 樹的存儲構造 6.4.2 森林與二叉樹的轉換 6.4.3 樹和森林的遍歷6.6 赫夫曼樹及其應用6.4.1 樹的存儲構造三種常用的鏈表構造：雙親表示法孩子表示法孩子兄弟表示法1. 雙親表示法即以一組連續(xù)空間存儲樹的結點，同時在每個結點中附設一個指示器指示其雙親的下標。DACREBFHGK雙親結點下標9876543210666311000-1KHGFEDCBAR樹的雙親表存儲表示#define MAX_TREE_S

11、IZE 100 typedef struct PTNode / 結點構造 TElemType data; int parent; / 雙親位置域 PTNode;typedef struct /樹構造 PTNode nodesMAX_TREE_SIZE; int r, n; / 根結點的位置和結點個數(shù) PTree;分析： 這種存儲構造利用每個結點除根結點只有唯一雙親的性質，parent(T,x操作可在常量時間內實現(xiàn)。反復調用parent操作，直到遇見無雙親的結點時，便找到了樹的根。但在這種表示方式中，求結點的孩子時需遍歷整個構造。2. 孩子表示法 多重鏈表+孩子鏈表 多重鏈表 由于樹中每個結點可

12、能有多棵子樹，那么考慮用多重鏈表，即結點有多個指針域，其中每個指針指向一個孩子，此時有兩種結點格式：datadegreechild1child2childddatachild1child2childd采用第一種格式：指針域的個數(shù)等于樹的度 多重鏈表中的結點是同構的，其中 d 為樹的度。由于樹中很多結點的度小于 d，所以鏈表中有很多空鏈域，造成空間浪費。datachild1child2childdn個結點度為k的樹中必有n*(k-1)+1個空鏈域。采用第二種格式：指針域的個數(shù)等于結點的度 結點是不同構的，其中 d 為結點的度，degree 域的值同 d ，此時可以節(jié)省存儲空間，但結點構造不一致，

13、操作不方便。datadegreechild1child2childdA 2B 3C 2E 1I 0G 0H 0F 0D 0ACBHFEDGI有沒有既能節(jié)省空間又操作方便的方法呢？另一種方式：孩子鏈表表示法把每個結點的孩子結點用一個單鏈表表示。那么 n個結點有 n 個孩子鏈表葉子的孩子鏈表為空)。而 n 個頭指針又組成一個線性表，為便于查找，采用順序存儲構造。365120789KHGEFRDCBA0123456789DACREBFHGK表結點孩子結點樹的孩子鏈表存儲表示typedef struct CTNode / 孩子結點int child; / 孩子對應表結點的下標 struct CTNod

14、e *next;/ 指向下一個孩子結點的指針CTNode，*ChildPtr;typedef struct / 表結點 TElemType data; ChildPtr firstchild;/ 孩子鏈的頭指針，指向第一個孩子結點CTBox;typedef struct / 樹構造 CTBox nodesMAX_TREE_SIZE; int n, r; / 結點數(shù)和根結點的位置 CTree;分析： 與雙親表示法相反，孩子表示法便于涉及孩子的操作實現(xiàn)，卻不適用于parent(T，x)操作?？筛鶕?jù)某種需要，將二者結合起來，即帶雙親的孩子鏈表。3. 孩子兄弟表示法或稱二叉鏈表表示法。即以二叉鏈表作樹

15、的存儲構造。鏈表中結點的兩個鏈域分別指向該結點的第一個孩子結點和下一個兄弟結點。樹的二叉鏈表孩子 - 兄弟存儲表示typedef struct CSNode TElemType data; struct CSNode *firstchild , *nextsibling; CSNode, *CSTree;結點構造 firstchild data nextsiblingREKCFABGHDDACREBFHGK二叉鏈表孩子兄弟表示法例：分析： 這種存儲構造便于實現(xiàn)各種樹的操作。首先易于實現(xiàn)找結點孩子等的操作。假設為每個結點增設一個(parent)域，那么同樣能方便地實現(xiàn)parent(T,x)操作。

16、6.4.2 森林和二叉樹的轉換 樹、森林與二叉樹之間可以互相進展轉換， 即任何一個森林或一棵樹都可以唯一地對應一棵二叉樹，而任何一棵二叉樹也能唯一地對應到一個森林或一棵樹上。 正是由于這樣的一一對應關系，可以把樹的處理問題轉化為二叉樹的處理問題，從而把問題簡化。 下面介紹樹、森林與二叉樹的互相轉換。1. 樹和二叉樹的對應關系加線.樹轉換為二叉樹方法ABCDEFG2.保存雙親與第一孩子連線,刪去與其他孩子的連線.轉動45oGDABECFABCDEGHFI(a)ABCDEGHFI(b)ABCDEGHFI(c)ABCDEGHFI(d)例：2. 森林和二叉樹的對應關系 從樹的二叉鏈表表示的定義可知，任

17、何一棵和樹對應的二叉樹，其右子樹必空。 那么，假設把森林中第二棵樹的根結點看成是第一棵樹的根結點的兄弟，那么同樣可導出森林和二叉樹的對應關系。1森林轉換成二叉樹假設F=T1，T2，Tm是森林，那么可以按如下規(guī)那么轉換成一棵二叉樹B=ROOT，LB，RB1 假設F為空，即m=0，那么B為空二叉樹。2 假設F非空，即m0，那么B的根ROOT即為森林中第一棵樹的根ROOTT1，B的左子樹LB是從第一棵樹T1的子樹森林F1=T11，T12，T1m1轉換而成的二叉樹；其右子樹RB是從其余樹的森林F=T2，T3，Tm轉換而成的二叉樹。轉換方法： 將森林中的每棵樹轉換成二叉樹； 從第二棵二叉樹開場，依次把后

18、一棵二叉樹的根結點作為前一棵二叉樹根結點的右孩子，當所有二叉樹連起來后，此時所得到的二叉樹就是由森林轉換得到的二叉樹。 12BCDEGHFI（a）BCDEGHFI（b）BCDEGHFI（c）BCDEGHFI（d）二叉樹轉換成森林、樹 假設B=ROOT，LB，RB是一棵二叉樹，那么可以按如下原那么轉換成森林F=T1，T2，Tm1 假設B為空，那么F為空；2 假設B非空，那么F中第一棵樹T1的根ROOTT1為二叉樹B的根ROOT；第一棵樹T1的子樹森林F1是由B的左子樹LB轉換而成的森林；F中除了T1之外的其余樹組成的森林F=T2，T3，Tm是由B的右子樹RB轉換而成的森林。轉換方法： 加線假設某結點x是其雙親y的左孩子，那么把結點x的右孩子、右孩子的右孩子、，都與結點y用線連起來； 去線刪去原二叉樹中所有的雙親結點與右孩子結點的連線； 層次調整 FHGEAICDBFHGDCEBAIFEDCBAHGI加線去線層次調整IHGBCDAFE6.4.3 樹和森林的遍歷1. 樹的遍歷：有兩種次序先根(序)遍歷：假設樹不空，那么先訪問根結點，然后依次先根遍歷各棵子樹。后根(序)遍歷：假設樹不空，那么先依次后根遍歷各棵子樹，然后訪問根結點。例：對樹進展先根遍歷，獲得的先根序列是：對樹進展后根遍歷，獲得的后根序列是：ABCDEGHFIA B E