【文章內容簡介】 } } 、遍歷二叉樹 66 例 計算二叉樹結點個數的遞歸算法 int c=0。 void count ( BiTree T ) { if ( T!= NULL ) {count(Tlchild)。 c++。 count(Trchild)。 } } *** 、遍歷二叉樹 67 例 計算二叉樹葉結點個數遞歸算法 int c=0。 void count ( BiTree T ) { if ( T!= NULL ) {count(Tlchild)。 if (Tlchild==NULL amp。amp。Trchild==NULL) c++。 count(Trchild)。 } } *** 、遍歷二叉樹 68 中根遍歷的非遞歸算法 void NINORDER(BiTree BT) {STACK S。BiTree T=BT。 InitStack(S)。 while(T) {PUSH(T,S)。T=LCHILD(T)。} while(!IsEmpty(S)) {POP(S,e)。visit(e)。 e=RCHILD(e)。 while(!IsEmpty(e)) {PUSH(S,e)。e=LCHILD(e)。} }} A B C D F E G I k j *** 、遍歷二叉樹 69 表達式的樹型表示： a+b*(cd)e/f 表達式的二叉樹表示與求值 把每個操作數作為葉結點 ， 操作符作為非葉結點： a b c d e f * + / 70 表達式的二叉樹表示與求值 a b c d e f * + / 前序序列 +a*bcd/ef 前綴表示（波蘭式） 中序序列 a+b*cde/f 中綴表示 后序序列 abcd*+ef/ 后綴表示（逆波蘭式） 71 表達式的二叉樹表示與求值 a b c d e f * + / abcd*+ef/ 用棧實現后綴表達式 的過程 設置棧； 遇操作數進棧； 遇操作符時根據操作 符的性質從棧中取若干個 操作數操作后再入棧； 最后結果就是棧中值。 * 72 樹的定義和基本術語 二叉樹 二叉樹的定義 二叉樹的性質 二叉樹的存儲結構 遍歷二叉樹與線索二叉樹 遍歷二叉樹 線索二叉樹 樹和森林 ** 樹與等價問題 赫夫曼樹及其應用 ** 回溯法與樹的遍歷 ** 樹的計數 第 6章 樹和二叉樹 73 何謂線索二叉樹？ 線索鏈表的遍歷算法 如何建立線索鏈表？ 、線索二叉樹 74 n個結點的二叉鏈表結構中有多少個鏈域 ?多少個空鏈域 ? 有 2n個鏈域 ， n+1個空鏈域； 利用這些空鏈域來存放某種遍歷后結點的 前驅和后繼 信息 。 這就是線索二叉樹構成的思想 。 這里的前驅和后繼是指采用某種遍歷時的前驅和后繼 。 采用既可以指示其前驅又可以指示后繼的雙鏈結構的二叉樹被稱為線索二叉樹 。 、線索二叉樹 75 1． 規(guī)定 ， 則其 lchild域指示其左孩子 ， 否則令 lchild域指示其前驅； ， 則其 rchild域指示其右孩子 ， 否則令 rchild域指示其后繼 。 、線索二叉樹 76 2． 結點結構 lchild LTag data RTag rchild 其中： ltag， rtag為兩個標志域 、線索二叉樹 LTag= 0 1 lchild 指向結點的左孩子 lchild 指向結點的前驅 RTag= 0 1 rchild 指向結點的右孩子 rchild 指向結點的后繼 77 線索二叉樹結點類型定義： 、線索二叉樹 typedef struct BiThrNod { TElemType data。 struct BiThrNode *lchild, *rchild。 // 左右指針 PointerThr LTag, RTag。 // 左右標志 } BiThrNode, *BiThrTree。 typedef enum { Link, Thread } PointerThr。 // Link==0:指針， Thread==1:線索 78 在非線索二叉樹與線索二叉樹中 結點 T是否有左右孩子的不同表示方法： 、線索二叉樹 在非線索二叉樹中： 在線索二叉樹中： if(Tlchild) if(Trchild) if(TLTag) if(TRTag) 有左子樹 有右子樹 無左子樹 無右子樹 79 3． 幾個概念 (1)線索鏈表：上述結點結構構成的二叉鏈表作為二叉樹的存儲結構 ， 叫做線索鏈表； (2)線索：指向某遍歷次序的前驅或后繼的指針 。 (3)線索二叉樹：采用線索鏈表表示的二叉樹 。 (4)線索化：對二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程 。 、線索二叉樹 80 4． 線索二叉樹以及空線索二叉樹的表示方法： (1)給出根結點的指針 T。 若 T為空 ， 則表示是空線索二叉樹 。 A B C D E F 0 0 0 0 0 1 1 1 1 1 1 1 NULL NULL 、線索二叉樹 81 設一個指針 pre始終指向剛剛訪問過的結點 ，指針 p指示當前正在訪問的結點 。 (1)若結點 p有空指針域 ， 則將相應的標志域置 1；否則 0。 ① 若結點 pre的右線索標志為 1， 令 prerchild指向其中序后繼結點 p。 ② 若結點 p的左線索標志為 1， 則令 plchild指向其中序前趨結點 pre； (3)將 pre指向剛剛訪問過的結點 p， 、線索二叉樹 82 BiThrTree pre=NULL,p=T。 void InOrderThreading(BiThrTree p) {if(p!=NULL) {InOrderThreading(plchild)。 if (plchild==NULL) pLTag=Thread。 else pLTag=Link。 if (prchild==NULL) pRTag=Thread。 else prtag=Link。 if (pre!=NULL) if (preRTag==Thread) prerchild=p。 if (pltag==Thread) plchild=pre。 pre=p。 InOrderThreading (prchild)。 }}//算法結束 、線索二叉樹 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。 Thrtrchild是一個線索 ， 指向線索化中最后一個結點 。 Thrtltag=0。 Thrtrtag=1。 、線索二叉樹 85 Thrtlchild=Thrt。 Thrtrchild=Thrt。 Thrtltag=0。 Thrtrtag=1。 0 1 帶頭結點的空線索二叉樹的表示 、線索二叉樹 86 ：中序線索化過程： A B C D E F 0 1 Thrt 、線索二叉樹 pre=Thrt 87 、線索二叉樹 Status InOrderThreading(BiThrTree amp。Thrt, BiThrTree T) if (!(Thrt = (BiThrTree)malloc(sizeof( BiThrNode)))) exit (OVERFLOW)。 ThrtLTag = Link。 ThrtRTag =Thread。 Thrtrchild = Thrt。 // 添加頭結點 return OK。 } // InOrderThreading … … 88 、線索二叉樹 if (!T) Thrtlchild = Thrt。 else { Thrtlchild = T。 pre = Thrt。 InThreading(T)。 prerchild = Thrt。 // 處理最后一個結點 preRTag = Thread。 Thrtrchild = pre。 } 89 、線索二叉樹 void InThreading(BiThrTree p) { if (p) { // 對以 p為根的非空二叉樹進行線索化 InThreading(plchild)。 // 左子樹線索化 if (!plchild) // 建前驅線索 { pLTag = Thread。 plchild = pre。 } if (!prerchild) // 建后繼線索 { preRTag = Thread。 prerchild = p。 } pre = p。 // 保持 pre 指向 p 的前驅 InThreading(prchild)。 // 右子樹線索化 } // if } // InThreading 90 、線索二叉樹 中序線索化鏈表的非遞歸遍歷算法 ※ 中序遍歷的第一個結點 ？ ※ 在中序線索化鏈表中結點的后繼 ？ 左子樹上處于“最左下”（沒有左子樹）的結點。 若無右子樹，則為后繼線索所指結點； 否則為對其右子樹進行中序遍歷時訪問的第一個結點。 91 、線索二叉樹 void InOrderTraverse_Thr(BiThrTree T, void (*Visit)(TElemType e)) { p = Tlchild。 // p指向根結點 while (p != T) { // 空樹或遍歷結束時， p==T while (pLTag==Link) p = plchild。 if(!Visit(pdata)) return error。 while (pRTag==Thread amp。amp。 prchild!=T) {