【正文】 E G H I k j 97 A B C D F E G H I k j 三、線索二叉樹 (穿線樹 ) 例 p的前序前趨和前序后繼 : (2)查找后繼： a、 若 p沒有右子樹； b、 若 p有右子樹； 98 前序查找后繼： BiThrTree Preordernext(BiThrTree p) { if (pLTag==0) return (plchild)。 while (qltag==0) q=qlchild。 if (prtag==1) return (prchild)。 return(q)。 else {q=plchild。 // p進至其右子樹根 } } // InOrderTraverse_Thr 92 例 p的中序前趨和中序后繼 : (1)查找前趨： a、 若 p沒有左子樹； b、 若 p有左子樹； 三、線索二叉樹 (穿線樹 ) A B C D F E G H I k j 93 中序查找前趨： BiThrTree Inorderpre(BiThrTree p) {BiThrTree q。 Visit(pdata)。amp。 if(!Visit(pdata)) return error。 91 、線索二叉樹 void InOrderTraverse_Thr(BiThrTree T, void (*Visit)(TElemType e)) { p = Tlchild。 // 右子樹線索化 } // if } // InThreading 90 、線索二叉樹 中序線索化鏈表的非遞歸遍歷算法 ※ 中序遍歷的第一個結點 ？ ※ 在中序線索化鏈表中結點的后繼 ？ 左子樹上處于“最左下”（沒有左子樹）的結點。 } pre = p。 } if (!prerchild) // 建后繼線索 { preRTag = Thread。 // 左子樹線索化 if (!plchild) // 建前驅線索 { pLTag = Thread。 Thrtrchild = pre。 prerchild = Thrt。 pre = Thrt。 } // InOrderThreading … … 88 、線索二叉樹 if (!T) Thrtlchild = Thrt。 Thrtrchild = Thrt。 ThrtLTag = Link。 0 1 帶頭結點的空線索二叉樹的表示 、線索二叉樹 86 ：中序線索化過程： A B C D E F 0 1 Thrt 、線索二叉樹 pre=Thrt 87 、線索二叉樹 Status InOrderThreading(BiThrTree amp。 Thrtltag=0。 、線索二叉樹 85 Thrtlchild=Thrt。 Thrtltag=0。 }}//算法結束 、線索二叉樹 83 增加頭結點 Thrt A B C D E F 0 0 0 0 0 1 1 1 1 1 1 1 NULL NULL 0 1 、線索二叉樹 84 4． 空線索二叉樹的表示方法： 增加一個頭結點： Thrtlchild=T。 pre=p。 if (pre!=NULL) if (preRTag==Thread) prerchild=p。 if (prchild==NULL) pRTag=Thread。 if (plchild==NULL) pLTag=Thread。 ② 若結點 p的左線索標志為 1， 則令 plchild指向其中序前趨結點 pre； (3)將 pre指向剛剛訪問過的結點 p， 、線索二叉樹 82 BiThrTree pre=NULL,p=T。 (1)若結點 p有空指針域 ， 則將相應的標志域置 1；否則 0。 若 T為空 ， 則表示是空線索二叉樹 。 (4)線索化：對二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程 。 // Link==0:指針， Thread==1:線索 78 在非線索二叉樹與線索二叉樹中 結點 T是否有左右孩子的不同表示方法： 、線索二叉樹 在非線索二叉樹中： 在線索二叉樹中： if(Tlchild) if(Trchild) if(TLTag) if(TRTag) 有左子樹 有右子樹 無左子樹 無右子樹 79 3． 幾個概念 (1)線索鏈表：上述結點結構構成的二叉鏈表作為二叉樹的存儲結構 ， 叫做線索鏈表； (2)線索：指向某遍歷次序的前驅或后繼的指針 。 // 左右標志 } BiThrNode, *BiThrTree。 struct BiThrNode *lchild, *rchild。 、線索二叉樹 75 1． 規(guī)定 ， 則其 lchild域指示其左孩子 ， 否則令 lchild域指示其前驅； ， 則其 rchild域指示其右孩子 ， 否則令 rchild域指示其后繼 。 這里的前驅和后繼是指采用某種遍歷時的前驅和后繼 。 * 72 樹的定義和基本術語 二叉樹 二叉樹的定義 二叉樹的性質 二叉樹的存儲結構 遍歷二叉樹與線索二叉樹 遍歷二叉樹 線索二叉樹 樹和森林 ** 樹與等價問題 赫夫曼樹及其應用 ** 回溯法與樹的遍歷 ** 樹的計數(shù) 第 6章 樹和二叉樹 73 何謂線索二叉樹？ 線索鏈表的遍歷算法 如何建立線索鏈表？ 、線索二叉樹 74 n個結點的二叉鏈表結構中有多少個鏈域 ?多少個空鏈域 ? 有 2n個鏈域 ， n+1個空鏈域； 利用這些空鏈域來存放某種遍歷后結點的 前驅和后繼 信息 。e=LCHILD(e)。 e=RCHILD(e)。} while(!IsEmpty(S)) {POP(S,e)。 while(T) {PUSH(T,S)。BiTree T=BT。 count(Trchild)。amp。 void count ( BiTree T ) { if ( T!= NULL ) {count(Tlchild)。 count(Trchild)。 void count ( BiTree T ) { if ( T!= NULL ) {count(Tlchild)。 CreateBtree ( T → rchild ) 。 T → data = ch 。 if ( ch == ‘ ’ ) T = NULL 。 return(tltr? tl+1: tr+1)。 else { tl=height(tlchild)。 A B C E D F I H 、遍歷二叉樹 63 int height(BiTree t) { int tl,tr。 } } 、按層遍歷二叉樹 *** 62 例 1 以二叉鏈表作存儲結構，試編寫求二叉樹高度的算法。 if (Elchild) EnQueue(Q,Elchild)。E)。 if (T) Enqueue(Q,T)。 // 訪問結點 } } 61 Status LevelOrderTraverse(BiTree T, Status (*Visit)(TElemType e)) {Queue Q。 // 遍歷左子樹 Postorder(Trchild, visit)。// 遍歷右子樹 } } 60 、遍歷二叉樹 void Postorder (BiTree T, void( *visit)(TElemType amp。 // 遍歷左子樹 visit(Tdata)。// 遍歷右子樹 } } 59 、遍歷二叉樹 void Inorder (BiTree T, void( *visit)(TElemType amp。 // 訪問結點 Preorder(Tlchild, visit)。 、遍歷二叉樹 58 、遍歷二叉樹 void Preorder (BiTree T, void( *visit)(TElemType amp。 8,9,4,10,11,5,2,12,6,7,3,1 后序遍歷中第一個結點和最后一個結點各是什么 ? 、遍歷二叉樹 54 討論： 給出一種遍歷次序是否能 唯一 確定一棵二叉樹 不能：前序 12，中序 12，后序 12 給出前序和后序是否能唯一確定一棵二叉樹 不能：前序 12，后序 21。 8,4,9,2,10,5,11,1,12,6,3,7 中序遍歷中第一個結點和最后一個結點各是什么 ? 根結點處于什么位置 ? 、遍歷二叉樹 53 (a)后序遍歷 (后根遍歷 ) 若二叉樹為空，則退出；若不空： 后序遍歷左子樹； 后序遍歷右子樹 。 要討論的三種操作分別為： ① 先根順序 DLR，②中根順序 LDR，③后根順序 LRD D L R 、遍歷二叉樹 50 先序 (先根 )遍歷 中序 (中根 )遍歷 后序 (后根 )遍歷 層次遍歷： 、遍歷二叉樹 51 (a)前序遍歷 (先根遍歷 ) 若二叉樹為空，則返回；若不空： 訪問根結點； 前序遍歷左子樹； 前序遍歷右子樹。 “ 訪問 ” 的含義很多，如：輸出結點的信息、查找、記數(shù)等等。 DeleteChild(T, p, LR)。 DestroyBiTree(amp。 二叉樹的基本操作 46 ClearBiTree(amp。T, definition)。e, value)。T)。 LevelOrderTraverse(T, Visit())。 InOrderTraverse(T, Visit())。 BiTreeDepth(T)。 RightSibling(T, e)。 RightChild(T, e)。 Parent(T, e)。T) Status PreOrderTraverse(BiTree T, Status (*Visit)(TElemType e)) Status InOrderTraverse(BiTree T, Status (*Visit)(TElemType e)) Status PostOrderTraverse(BiTr