1樹的定義和基本術(shù)語

1、6.1 樹的定義和基本術(shù)語,6.2 二叉樹,6.3 遍歷二叉樹和線索二叉樹,6.4 樹和森林,6.6 哈夫曼樹及其應(yīng)用,樹和二叉樹,何謂線索二叉樹？ 線索鏈表的遍歷算法 如何建立線索鏈表？,￡6.3.2 二叉樹的線索化,6.3 遍歷二叉樹和線索二叉樹,一、何謂線索二叉樹？,遍歷二叉樹的結(jié)果是， 求得結(jié)點的一個線性序列。,A,B,C,D,E,F,G,H,K,,,,,,,,,例如:,先序序列: A B C D E F

2、 G H K,中序序列: B D C A H G K F E,后序序列: D C B H K G F E A,指向該線性序列中的“前驅(qū)”和 “后繼” 的指針，稱作“線索”,與其相應(yīng)的二叉樹，稱作 “線索二叉樹”,包含 “線索” 的存儲結(jié)構(gòu)，稱作 “線索鏈表”,A B C D E F G H K,,,^ D ^,C ^,^ B,,,,,,,,,,E ^,,,,對線索鏈表中結(jié)點的約定：,在二叉鏈

3、表的結(jié)點中增加兩個標志域，并作如下規(guī)定：,若該結(jié)點的左子樹不空，則Lchild域的指針指向其左子樹， 且左標志域的值為“指針 Link”； 否則，Lchild域的指針指向其“前驅(qū)”， 且左標志的值為“線索 Thread” 。,若該結(jié)點的右子樹不空，則rchild域的指針指向其右子樹， 且右標志域的值為 “指針 Link”；否則，rchild域的指針指向其“后繼”， 且右標志的值為“線索 Thread”。

4、,如此定義的二叉樹的存儲結(jié)構(gòu)稱作“線索鏈表”,￡6.3.2 二叉樹的線索化,當以二叉鏈表作為存儲結(jié)構(gòu)時，只能找到結(jié)點的左、右孩子信息，而不能直接得到結(jié)點在任一序列（先序、中序或后序序列）中的前驅(qū)和后繼信息，這種信息只有在遍歷的動態(tài)過程中才能得到。為了保存這種在遍歷過程中得到的信息，我們利用二叉鏈表中的空鏈域（由于結(jié)點沒有左子樹或右子樹），來存放結(jié)點的前驅(qū)和后繼信息。,作如下規(guī)定： ①若結(jié)點有左子樹，則其lchild域

5、指示其左孩子，否則令lchild域指示其前驅(qū)； ②若結(jié)點有右子樹，則其rchild域指示其右孩子，否則令rchild域指示其后繼。,（1）線索鏈表的結(jié)點結(jié)構(gòu),其中：data：數(shù)據(jù)域； lchild：左指針域，指向該結(jié)點的左孩子； rchild：右指針域，指向該結(jié)點的右孩子；,（2）線索鏈表的定義 線索鏈表：以上述結(jié)點結(jié)構(gòu)構(gòu)成的二叉鏈表作為二叉樹的存儲結(jié)構(gòu)，稱

6、之為線索鏈表。,（3）相關(guān)術(shù)語,線索化：對二叉樹以某種次序遍歷使其變?yōu)榫€性二叉樹的過程。,線索二叉樹（Threaded Binary Tree）：加上線索的二叉樹。,線索：在線索鏈表中指向結(jié)點前驅(qū)和后繼的指針。,（4）圖形表示,(a) ( a + b * (c－d)－e / f )表達式的二叉樹,(b) 中序線索二叉樹,圖6.11線索二叉樹及其存儲結(jié)構(gòu),(c) 中序線索鏈表,圖中，實線為指針（指向左、右子樹），虛線為線索（指向

7、前驅(qū)和后繼）。,typedef struct BiThrNod { TElemType data; struct BiThrNode *lchild, *rchild; // 左右指針 PointerThr LTag, RTag; // 左右標志} BiThrNode, *BiThrTree;,線索鏈表的類型描述：,typedef enum { Link, Thread } P

8、ointerThr; // Link==0:指針，Thread==1:線索,二、線索鏈表的遍歷算法:,for ( p = firstNode(T); p; p = Succ(p) ) Visit (p);,由于在線索鏈表中添加了遍歷中得到的“前驅(qū)”和“后繼”的信息，從而簡化了遍歷的算法。,例如: 對中序線索化鏈表的遍歷算法,※ 中序遍歷的第一個結(jié)點 ？,※ 在中序線索化鏈表中結(jié)點的后繼 ？,左子樹上處于

9、“最左下”（沒有左子樹）的結(jié)點,若無右子樹，則為后繼線索所指結(jié)點,否則為對其右子樹進行中序遍歷時訪問的第一個結(jié)點,void InOrderTraverse_Thr(BiThrTree T, void (*Visit)(TElemType e)) { //T指向結(jié)點，頭結(jié)點的左鏈lchild指向根結(jié)點，可參照線索化算法。//中序遍歷二叉線索樹T的非遞歸算法，對每個數(shù)據(jù)元素調(diào)用函數(shù)visit p = T->lchild;

10、 // p指向根結(jié)點 while (p != T) { // 空樹或遍歷結(jié)束時，p==T while (p->LTag==Link) p = p->lchild; // 第一個結(jié)點 if (!visit(p->data) return ERROR;//訪問其左子樹為空的結(jié)點 while (p->RTag==Thread && p->rc

11、hild!=T) { p = p->rchild; Visit(p->data); // 訪問后繼結(jié)點 } p = p->rchild; // p進至其右子樹根 }} // InOrderTraverse_Thr,在中序遍歷過程中修改結(jié)點的左、右指針域，以保存當前訪問結(jié)點的“前驅(qū)”和“后繼”信息。遍歷過程中，附設(shè)指針pre, 并始終保持指

12、針pre指向當前訪問的、指針p所指結(jié)點的前驅(qū)。,三、如何建立線索鏈表？,void InThreading(BiThrTree p) { if (p) { // 對以p為根的非空二叉樹進行線索化 InThreading(p->lchild); // 左子樹線索化 if (!p->lchild) // 建前驅(qū)線索 { p->LTag = Thread; p

13、->lchild = pre; } if (!pre->rchild) // 建后繼線索 { pre->RTag = Thread; pre->rchild = p; } pre = p; // 保持 pre 指向 p 的前驅(qū) InThreading(p->rchild); // 右子樹線索化 } // if} // In

14、Threading,Status InOrderThreading(BiThrTree &Thrt, BiThrTree T) { // 構(gòu)建中序線索鏈表 if (!(Thrt = new BiThrNode) ) exit (OVERFLOW); Thrt->LTag = Link; Thrt->RTag =Thread; Thrt-&g

15、t;rchild = Thrt; // 添加頭結(jié)點 return OK;} // InOrderThreading,… …,if (!T) Thrt->lchild = Thrt; else { Thrt->lchild = T; pre = Thrt; InThreading(T); pre->rchild