【文章內(nèi)容簡(jiǎn)介】 iTree( Tlchild)。 //構(gòu)造左子樹(shù) CreateBiTree( Trchild)。 //構(gòu)造右子樹(shù) } return(OK)。 } // CreateBiTree 統(tǒng)計(jì)二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù) 算法基本思想 : 先序 (或中序或后序 )遍歷二叉樹(shù)，在遍歷過(guò)程中查找葉子結(jié)點(diǎn)，并計(jì)數(shù)。 由此， 需在遍歷算法中增添一個(gè)“計(jì)數(shù)”的參數(shù) ，并將算法中“ 訪問(wèn)結(jié)點(diǎn) ”的操作改為： 若是葉子，則計(jì)數(shù)器增 1。 void CountLeaf (BiTree T, intamp。 count){ if ( T ) { if ((!Tlchild)amp。amp。 (!Trchild)) count++。 // 對(duì)葉子結(jié)點(diǎn)計(jì)數(shù) CountLeaf( Tlchild, count)。 CountLeaf( Trchild, count)。 } // if } // CountLeaf 求二叉樹(shù)的深度 (后序遍歷 ) 算法基本思想 : 從二叉樹(shù)深度的定義可知， 二叉樹(shù)的深度應(yīng)為其左、右子樹(shù)深度的最大值加 1。由此， 需先分別求得左、右子樹(shù)的深度， 算法中 “訪問(wèn)結(jié)點(diǎn)”的操作為： 求得左、右子樹(shù)深度的最大值，然后加 1 。 首先分析 二叉樹(shù)的深度 和它的 左 、 右子樹(shù)深度 之間的關(guān)系。 int Depth (BiTree T ){ // 返回二叉樹(shù)的深度 if ( !T ) depthval = 0。 else { depthLeft = Depth( Tlchild )。 depthRight= Depth( Trchild )。 depthval = 1 + (depthLeft depthRight ? depthLeft : depthRight)。 } return depthval。 } 線索二叉樹(shù) ? 何謂線索二叉樹(shù)？ ? 線索鏈表的遍歷算法 ? 如何建立線索鏈表？ 一、何謂線索二叉樹(shù)？ 遍歷二叉樹(shù)的結(jié)果是， 求得結(jié)點(diǎn)的一個(gè)線性序列。 A B C D E F G H K 例如 : 先序 序列 : A B C D E F G H K 中序 序列 : B D C A H G K F E 后序 序列 : D C B H K G F E A 指向該線性序列中的“前驅(qū)”和 “后繼” 的 指針 ，稱作“ 線索 ” 與其相應(yīng)的二叉樹(shù)，稱作 “ 線索二叉樹(shù) ” 包含 “線索” 的存儲(chǔ)結(jié)構(gòu)，稱作 “ 線索鏈表 ” A B C D E F G H K ^ D ^ C ^ ^ B E ^ 對(duì) 線索鏈表 中結(jié)點(diǎn)的約定： 在二叉鏈表的結(jié)點(diǎn)中 增加兩個(gè)標(biāo)志域 ， 并作如下規(guī)定： 若該結(jié)點(diǎn)的左子樹(shù)不空， 則 Lchild域的指針指向其左子樹(shù)， 且左標(biāo)志域的值為“ 指針 Link”或 0； 否則， Lchild域的指針指向其“前驅(qū)”， 且左標(biāo)志的值為“ 線索 Thread”或 1 。 若該結(jié)點(diǎn)的右子樹(shù)不空， 則 rchild域的指針指向其右子樹(shù)， 且右標(biāo)志域的值為 “ 指針 Link”或 0； 否則， rchild域的指針指向其“后繼”， 且右標(biāo)志的值為“ 線索 Thread”或 1。 如此定義的二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)稱作“ 線索鏈表 ”。 線索鏈表的結(jié)點(diǎn)結(jié)構(gòu) ltag和 rtag是增加的兩個(gè)標(biāo)志域，用來(lái)區(qū)分結(jié)點(diǎn)的左、右指針域是指向其左、右孩子的指針，還是指向其前驅(qū)或后繼的線索。 lchild LTag data RTag rchild ??????0 l c h i l dL T ag =1 l c h i l d0 r c h i l dRT ag =1 r c h i l d域指向結(jié)點(diǎn)的左孩子域指向結(jié)點(diǎn)的前驅(qū)域指向結(jié)點(diǎn)的右孩子域指向結(jié)點(diǎn)的后繼typedef struct BiThrNod { TElemType data。 struct BiThrNode *lchild, *rchild。 // 左右指針 PointerThr LTag, RTag。 // 左右標(biāo)志 } BiThrNode, *BiThrTree。 線索鏈表 的類(lèi)型描述： typedef enum { Link, Thread } PointerThr。 // Link==0:指針， Thread==1:線索 ABCDEFGHI 例如： 二、線索鏈表的遍歷算法 : for ( p = firstNode(T)。 p。 p = Succ(p) ) Visit (p)。 由于在線索鏈表中添加了遍歷中得到的“前驅(qū)”和“后繼”的信息，從而簡(jiǎn)化了遍歷的算法。 例如 : 對(duì)中序線索化鏈表的遍歷算法 ※ 中序遍歷的第一個(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)。 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。 // 第 一個(gè)結(jié)點(diǎn) Visit(pdata)。 while (pRTag==Thread amp。amp。 prchild!=T) { p = prchild。 Visit(pdata)。 } // 訪問(wèn)后繼結(jié)點(diǎn) p = prchild。 // p進(jìn)至其右子樹(shù)根 } } // InOrderTraverse_Thr 在中序遍歷過(guò)程中修改結(jié)點(diǎn)的 左、右指針域，以保存當(dāng)前訪問(wèn)結(jié) 點(diǎn)的“前驅(qū)”和“后繼”信息。遍歷過(guò) 程中，附設(shè)指針 pre, 并始終保持指 針 pre指向當(dāng)前訪問(wèn)的、指針 p所指 結(jié)點(diǎn)的前驅(qū)。 三、如何建立線索鏈表？ 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 Status InOrderThreading(BiThrTree amp。Thrt, BiThrTree T) { // 構(gòu)建中序線索鏈表 if (!(Thrt = (BiThrTree)malloc(sizeof( BiThrNode)))) exit (OVERFLOW)。 ThrtLTag = Link。 ThrtRTag =Thread。 Thrtrchild = Thrt。 if (!T) Thrtlchild = Thrt。 else { Thrtlchild = T。 pre = Thrt。 InThreading(T)。 prerchild = Thrt。 preRTag = Thread。 Thrtrchild = pre。 } return OK。 } // InOrderThreading 樹(shù)和森林 的表示方法 樹(shù)的三種存儲(chǔ)結(jié)構(gòu) 一、 雙親表示法 二、 孩子鏈表表示法 三、 樹(shù)的二叉鏈表 (孩子 兄弟） 存儲(chǔ)表示法 A B C D E F G 0 A 1 1 B 0 2 C 0 3 D 0 4 E 2 5 F 2 6 G 5 r=0 n=7 data parent 一、雙親表示法 : typedef struct PTNode { Elem data。 int parent。 // 雙親位置域 } PTNod