第 7 講 線索二叉樹

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

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

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

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

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

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

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

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

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

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

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

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

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

14、點前驅(qū)的右線索或后繼的左線索。 【題目分析】算法設(shè)計int TreeThrInsert(BiThrTree T,P,X)在中序全線索二叉樹T的結(jié)點P上，插入以X為根的中序全線索二叉樹，返回插入結(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的左線索(前驅(qū))修改為P else 尋找X的左子樹上按中序遍歷的第一個結(jié)點 q=X-lchild; while(q-ltag=0) q=q-lchild; q-lchil

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