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

1、6.1 樹(shù)的定義和基本術(shù)語(yǔ),6.2 二叉樹(shù),6.3 遍歷二叉樹(shù)和線索二叉樹(shù),6.4 樹(shù)和森林,6.6 哈夫曼樹(shù)及其應(yīng)用,樹(shù)和二叉樹(shù),何謂線索二叉樹(shù)？ 線索鏈表的遍歷算法 如何建立線索鏈表？,￡6.3.2 二叉樹(shù)的線索化,6.3 遍歷二叉樹(shù)和線索二叉樹(shù),一、何謂線索二叉樹(shù)？,遍歷二叉樹(shù)的結(jié)果是， 求得結(jié)點(diǎn)的一個(gè)線性序列。,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ū)”和 “后繼” 的指針，稱(chēng)作“線索”,與其相應(yīng)的二叉樹(shù)，稱(chēng)作 “線索二叉樹(shù)”,包含 “線索” 的存儲(chǔ)結(jié)構(gòu)，稱(chēng)作 “線索鏈表”,A B C D E F G H K,,,^ D ^,C ^,^ B,,,,,,,,,,E ^,,,,對(duì)線索鏈表中結(jié)點(diǎn)的約定：,在二叉鏈

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

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

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

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

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

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

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

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

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

12、針pre指向當(dāng)前訪問(wèn)的、指針p所指結(jié)點(diǎn)的前驅(qū)。,三、如何建立線索鏈表？,void InThreading(BiThrTree p) { if (p) { // 對(duì)以p為根的非空二叉樹(shù)進(jìn)行線索化 InThreading(p->lchild); // 左子樹(shù)線索化 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); // 右子樹(shù)線索化 } // 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é)點(diǎn) return OK;} // InOrderThreading,… …,if (!T) Thrt->lchild = Thrt; else { Thrt->lchild = T; pre = Thrt; InThreading(T); pre->rchild