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