第 7 講 線(xiàn)索二叉樹(shù)

1、第7講 線(xiàn)索二叉樹(shù)馮廣慧 講授第6章 樹(shù)6.1 樹(shù)的概念及操作6.2 二叉樹(shù) 6.2.1 二叉樹(shù)的概念及操作 6.2.2 二叉樹(shù)的性質(zhì)6.2.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)6.3 二叉樹(shù)的遍歷6.4 線(xiàn)索二叉樹(shù)6.5 樹(shù)和森林 6.5.1 樹(shù)的存儲(chǔ)結(jié)構(gòu) 6.5.2 森林、樹(shù)、二叉樹(shù)的相互轉(zhuǎn)換 6.5.3 樹(shù)和森林的遍歷6.6 哈夫曼樹(shù)及其應(yīng)用 6.6.1 最優(yōu)二叉樹(shù)(哈夫曼樹(shù)) 6.6.2 哈夫曼編碼 *6.7算法設(shè)計(jì)舉例主要內(nèi)容 知識(shí)點(diǎn)樹(shù)和二叉樹(shù)定義二叉樹(shù)的性質(zhì)，存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的遍歷及遍歷算法的應(yīng)用* 線(xiàn)索二叉樹(shù)二叉樹(shù)和樹(shù)及森林的關(guān)系Huffman樹(shù)與Huffman編碼重點(diǎn)難點(diǎn)二叉樹(shù)的性質(zhì)及應(yīng)用二叉樹(shù)

2、的遍歷算法及應(yīng)用* 線(xiàn)索二叉樹(shù)的算法Huffman樹(shù)的構(gòu)造方法樹(shù)的算法線(xiàn)索二叉樹(shù) 線(xiàn)索二叉樹(shù)的提出： 1、遍歷的實(shí)質(zhì)：非線(xiàn)性結(jié)構(gòu)線(xiàn)性化（前驅(qū)、后繼）; 2、前驅(qū)和后繼是在遍歷中得到的; 3、知道前驅(qū)和后繼，再遍歷時(shí)就不需要棧; 4、可以在二叉鏈表結(jié)構(gòu)中增加前驅(qū)和后繼兩個(gè)指針域; 5、n個(gè)結(jié)點(diǎn)的二叉樹(shù)有n1個(gè)空指針，可以利用。線(xiàn)索二叉樹(shù) n個(gè)結(jié)點(diǎn)的二叉鏈表中含有n+1個(gè)空指針域，可以利用這些空指針域來(lái)存放結(jié)點(diǎn)的前驅(qū)和后繼的信息,這樣的指針?lè)Q為“線(xiàn)索”，加上了線(xiàn)索的二叉鏈表稱(chēng)為線(xiàn)索鏈表，加上線(xiàn)索的二叉樹(shù)就是線(xiàn)索二叉樹(shù)（Threaded Binary Tree）。將二叉樹(shù)變?yōu)榫€(xiàn)索二叉樹(shù)的過(guò)程稱(chēng)為線(xiàn)索

3、化。 lchildltagdata rtag rchildltag= rtag= 線(xiàn)索二叉樹(shù) 線(xiàn)索化只有空指針才能加線(xiàn)索前序前驅(qū)線(xiàn)索化前序前驅(qū)線(xiàn)索化ABECFGHIDABECFGHID中序（全）線(xiàn)索二叉樹(shù)NULLACFEDBNULLA00E11C01D11F11B00NULLA 為方便起見(jiàn)，在線(xiàn)索鏈表中增加一個(gè)頭結(jié)點(diǎn)，令其lchild域指向二叉樹(shù)的根結(jié)點(diǎn)，rchild域指向訪(fǎng)問(wèn)序列的最后一個(gè)結(jié)點(diǎn)，這樣，就建立了一個(gè)雙向線(xiàn)索鏈表。后序（全）線(xiàn)索化線(xiàn)索鏈表的類(lèi)型定義typedef struct BiThrNode ElemTyte data; struct BiThrNode *lchild, *

4、rchild;左、右孩子指針 int ltag, rtag; BiThrNode，*BiThrTree 后面將討論以下三方面的算法：一、 線(xiàn)索化二、遍歷三、查找前驅(qū)和后繼算法舉例6.7 中序線(xiàn)索化BiThrTree pre=null;/設(shè)置前驅(qū)void InOrderThreat(BiThrTree T)if (T) InOrderThreat(T-lchild); /左子樹(shù)中序線(xiàn)索化 if (T-lchild=null) T-ltag=1; T-lchild=pre; /左線(xiàn)索為pre; if (T-rchild=null) T-rtag=1; /置右標(biāo)記，為右線(xiàn)索作準(zhǔn)備 if (pre!=

5、null & pre-rtag=1) pre-rchild=T; /給前驅(qū)加后繼線(xiàn)索 pre=T; /前驅(qū)指針后移 InOrderThreat(T-rchild); /右子樹(shù)中序線(xiàn)索化 /結(jié)束InOrderThreat 算法舉例6.8 前序線(xiàn)索化BiThrTree pre=null;/設(shè)置前驅(qū)void PreOrderThreat(BiThrTree T)if (T!=null) if (T-lchild=null) T-ltag=1; T-lchild=pre; /設(shè)置左線(xiàn)索 if (T-rchild=null) T-rtag=1; /為建立右鏈作準(zhǔn)備 if (pre!=null & pre

6、-rtag=1) pre-rchild=T; /設(shè)置前驅(qū)的右線(xiàn)索； pre=T; /前驅(qū)后移 if (T-ltag=0) PreOrderThreat(T-lchild); /左子樹(shù)前序線(xiàn)索化 PreOrderThreat(BT-rchild); /右子樹(shù)前序線(xiàn)索化 算法舉例6.9 后序線(xiàn)索化BiThrTree pre=null;/設(shè)置前驅(qū)void PostOrderThreat(BiThrTree T)if (T) PostOrderThreat(T-lchild); /左子樹(shù)后序線(xiàn)索化 PostOrderThreat(T-rchild); /右子樹(shù)后序線(xiàn)索化 if (T-lchild=nu

7、ll) T-ltag=1; T-lchild=pre; /左線(xiàn)索為pre; if (T-rchild=null) T-rtag=1;/置右標(biāo)記，為右線(xiàn)索作準(zhǔn)備 if (pre!=null & pre-rtag=1) pre-rchild=T; /給前驅(qū)加后繼線(xiàn)索 pre=T; /前驅(qū)指針后移 /結(jié)束PostOrderThreat 線(xiàn)索二叉樹(shù)的中序非遞歸遍歷中序線(xiàn)索二叉樹(shù)的中序非遞歸遍歷帶頭結(jié)點(diǎn)的中序線(xiàn)索二叉樹(shù)的中序非遞歸遍歷算法舉例6.10中序線(xiàn)索二叉樹(shù)的中序遍歷/遍歷即找結(jié)點(diǎn)的后繼的過(guò)程，非遞歸！void InorderTraverseThr(BiThrTree p) while(p) 二叉

8、樹(shù)非空 while (p-ltag=0) 找中序序列的開(kāi)始結(jié)點(diǎn) p=p-lchild; printf(p-data); while(p&p-rtag= =1) p=p-rchild; printf(p-data);/找P的中序后繼結(jié)點(diǎn) if(p) p=p-rchild; /右子樹(shù)的最左孩子是p的后繼 /while InorderTraverseThr算法舉例6.11 帶頭結(jié)點(diǎn)的線(xiàn)索二叉樹(shù) 的中序遍歷/頭結(jié)點(diǎn)的lchild域指向二叉樹(shù)的根結(jié)點(diǎn)/rchild域指向訪(fǎng)問(wèn)序列的最后一個(gè)結(jié)點(diǎn)void InorderTraverseThr(BiThrTree thrt)p=thrt-lchild; p指向

9、根結(jié)點(diǎn) while(p!=thrt) 二叉樹(shù)非空 while (p-ltag=0) 找中序序列的開(kāi)始結(jié)點(diǎn) p=p-lchild; printf(p-data); while(p-rtag=1 & p-rchild!=thrt) p=p-rchild; printf(p-data);/找P的中序后繼結(jié)點(diǎn) p=p-rchild; / while(p!=thrt) InorderTraverseThr線(xiàn)索樹(shù)上查找前驅(qū)和后繼前序線(xiàn)索樹(shù)上找前驅(qū)和后繼(DLR)中序線(xiàn)索樹(shù)上找前驅(qū)和后繼(LDR)后序線(xiàn)索樹(shù)上找前驅(qū)和后繼(LRD)前序線(xiàn)索樹(shù)上找前驅(qū)和后繼找前驅(qū)： 困難找后繼（DLR）： 若結(jié)點(diǎn)有左子女，則左

10、子女是后繼；否則，rchild指向后繼。算法舉例6.12 前序線(xiàn)索樹(shù)上找后繼BiThrTree PreorderNext(BiThrTree p) if (p-ltag= =0) 結(jié)點(diǎn)有左子女 return(p-lchild); 結(jié)點(diǎn)的左子女為其前序后繼 else return(p-rchild) ; PreorderNext中序線(xiàn)索樹(shù)上找前驅(qū)和后繼 中序的前驅(qū)和后繼都往上指向祖先找前驅(qū)： 若左標(biāo)記為1，則lchild指向其前驅(qū)；否則，其前驅(qū)是其左子樹(shù)上按中序遍歷的最后一個(gè)結(jié)點(diǎn)。找后繼： 若右標(biāo)記為1，則rchild指向其后繼；否則，其后繼是其右子樹(shù)上按中序遍歷的第一個(gè)結(jié)點(diǎn)。算法舉例6.13

11、中序線(xiàn)索樹(shù)上找前驅(qū)BiThrTree InorderPre(BiThrTree p) BiThrTree q; if (p-ltag= =1) 結(jié)點(diǎn)的左子樹(shù)為空 q=p-lchild 結(jié)點(diǎn)的左指針域?yàn)樽缶€(xiàn)索，指向其前驅(qū) else q=p-lchild; p結(jié)點(diǎn)的中序前驅(qū)是左子樹(shù)中最右邊結(jié)點(diǎn) while (q-rtag=0 ) q=q-rchild; if return (q); InorderPre算法舉例6.14 中序線(xiàn)索樹(shù)上找后繼BiThrTree InorderNext(BiThrTree p) BiThrTree q; if (p-rtag= =1) 結(jié)點(diǎn)的右子樹(shù)為空 q=p-rchi

12、ld 結(jié)點(diǎn)的右指針域?yàn)橛揖€(xiàn)索，指向其后繼 else q=p-rchild; P結(jié)點(diǎn)的中序后繼是其右子樹(shù)中最左邊結(jié)點(diǎn) while (q-ltag=0 ) q=q-lchild; if return (q); InorderNext后序線(xiàn)索樹(shù)上找前驅(qū)和后繼找前驅(qū)(LRD)： 若結(jié)點(diǎn)有右子女，則右子女是其前驅(qū)；否則，lchild指向其前驅(qū)。找后繼： 困難，需要知道其雙親。算法舉例6.15 后序線(xiàn)索樹(shù)上找前驅(qū)BiThrTree PostorderPre(BiThrTree p) if (p-rtag= =0) 結(jié)點(diǎn)有右子女 return(p-rchild); 結(jié)點(diǎn)的右子女為其后序前驅(qū) else ret

13、urn(p-lchild) ; PreorderPre線(xiàn)索樹(shù)上結(jié)點(diǎn)的插入與刪除除修改結(jié)點(diǎn)指針外，還需要修改線(xiàn)索。請(qǐng)編寫(xiě)在中序全線(xiàn)索二叉樹(shù)T中的結(jié)點(diǎn)P下插入一棵根為X的中序全線(xiàn)索二叉樹(shù)的算法。如果P左右孩子都存在，則插入失敗并返回FALSE；如果P沒(méi)有左孩子，則X作為P的左孩子插入；否則X作為P的右孩子插入。插入完成后要求二叉樹(shù)保持中序全線(xiàn)索并返回TRUE。 題目要求中序全線(xiàn)索化T樹(shù)P結(jié)點(diǎn)的度不能是2。因此：以X為根的中序全線(xiàn)索化二叉樹(shù)只能做為P的右子樹(shù)或左子樹(shù)插入。若X無(wú)左（右）子樹(shù)，要修改X的左（右）線(xiàn)索；若X有左（右）子樹(shù)，則修改X左(右)子樹(shù)上最左結(jié)點(diǎn)和最右結(jié)點(diǎn)的線(xiàn)索。還可能要修改原P結(jié)

14、點(diǎn)前驅(qū)的右線(xiàn)索或后繼的左線(xiàn)索。 【題目分析】算法設(shè)計(jì)int TreeThrInsert(BiThrTree T,P,X)在中序全線(xiàn)索二叉樹(shù)T的結(jié)點(diǎn)P上，插入以X為根的中序全線(xiàn)索二叉樹(shù)，返回插入結(jié)果信息。 if(P-ltag=0 & P-rtag=0) printf(“P有左右子女，插入失敗n”)； return(0); if(P-ltag=0) P有左子女，將X插為P的右子女 if(X-ltag=1) q=X;記住X，后邊將X的左線(xiàn)索(前驅(qū))修改為P else 尋找X的左子樹(shù)上按中序遍歷的第一個(gè)結(jié)點(diǎn) q=X-lchild; while(q-ltag=0) q=q-lchild; q-lchil

15、d=P; q(指向X子樹(shù)的最左結(jié)點(diǎn))的左線(xiàn)索(前驅(qū))是P if(X-rtag=1) q=X;記住X，后邊將X的右線(xiàn)索(后繼)修改為P的后繼 else 尋找X的右子樹(shù)上按中序遍歷的最后一個(gè)結(jié)點(diǎn) q=X-rchild; while(q-rtag=0) q=q-rchild; q-rchild=P-rchild; q(指向x的最右結(jié)點(diǎn))的右線(xiàn)索(后繼) 修改為P的后繼 if(P-rchild-ltag=1) P-rchild-lchild=q; 修改P結(jié)點(diǎn)后繼的左線(xiàn)索? P-rtag=0; P-rchild=X; P結(jié)點(diǎn)的右子女為X,右標(biāo)記置0 結(jié)束了X插為P的右子女 else P無(wú)左子女，將X插為P的左子女 if(X-ltag=1) q=X;記住X，X無(wú)左子女，將P的左線(xiàn)索改為X的左線(xiàn)索 else X有左子女，找X左子樹(shù)上按中序遍歷的第一個(gè)結(jié)點(diǎn) q=X-lchild; while(q-ltag=0) q=q-lchild; q-lchild=P-lc