數(shù)據(jù)結(jié)構(gòu)第六章樹和二叉樹(編輯修改稿)
2025-07-16 16:40 本頁面
【文章內(nèi)容簡介】 rchild) else if ( !StackEmpty(S )) t = Pop(S)。 // 退棧 else t = NULL。 // ?？毡砻鞅闅v結(jié)束 } // while } t = GoFarLeft(trchild, S)。 四 、 遍歷算法的應(yīng)用舉例 統(tǒng)計二叉樹中葉子結(jié)點的個數(shù) 求二叉樹的深度 (后序遍歷 ) 建立二叉樹的存儲結(jié)構(gòu) 查詢二叉樹中某個結(jié)點 1. 在二叉樹不空的前提下 ,和根結(jié)點的元素進行比較 ,若相等 ,則找到返回 TRUE。 2. 否則在左子樹中進行查找 ,若找到 , 則返回 TRUE。 3. 否則繼續(xù)在右子樹中進行查找 ,若找到 ,則返回 TRUE,否則返回 FALSE。 Status Preorder (BiTree T, ElemType x) { // 若二叉樹中存在和 x 相同的元素，則 p 指向該結(jié)點并返回 OK, // 否則返回 FALSE } if (T) { if (Tdata==x) { p = T。 return OK,} }//if else return FALSE。 else { if (Preorder(Tlchild, x) return OK。 else return(Preorder(Trchild, x)) 。 }//else 統(tǒng)計二叉樹中葉子結(jié)點的個數(shù) int count=0。 int CountLeaf (BiTree T,count){ if( T ) { if ((!Tlchild)amp。amp。 (!Trchild)) count++。 // 對葉子結(jié)點計數(shù) CountLeaf( Tlchild, count)。 CountLeaf( Trchild, count)。 return count。 } else return 0。 } // CountLeaf 求二叉樹的深度 (后序遍歷 ) 算法基本思想 : 從二叉樹深度的定義可知， 二叉樹的深度應(yīng)為其左、右子樹深度的最大值加 1。由此， 需先分別求得左、右子樹的深度，算法中 “訪問結(jié)點”的操作為 :求得左、右子樹深度的最大值，然后加 1 。 首先分析 二叉樹的深度 和它的 左 、 右子樹深度 之間的關(guān)系。 int Depth (BiTree T ){ // 返回二叉樹的深度 if ( !T ) depthval = 0。 else { depthLeft = Depth( Tlchild )。 depthRight= Depth( Trchild )。 depthval = 1 + (depthLeft depthRight ? depthLeft : depthRight)。 } return depthval。 } 建立二叉樹的存儲結(jié)構(gòu) 不同的定義方法相應(yīng)有不同的存儲結(jié)構(gòu)的建立算法 以字符串的形式 “ 根 左子樹 右子樹 ” 定義一棵二叉樹 例如 : 以空白字符“ ”表示 A B C D AB C D 空樹 只含一個根結(jié)點的二叉樹 A 以字符串“ A ” 表示 以下列字符串表示 int CreateBiTree(BiTree amp。T) { scanf(amp。ch)。 if (ch==39。 39。) T = NULL。 else { if (!(T = new BiTNode)) exit(OVERFLOW)。 Tdata = ch。 // 生成根結(jié)點 CreateBiTree(Tlchild)。 // 構(gòu)造左子樹 CreateBiTree(Trchild)。 // 構(gòu)造右子樹 } return 1。 } // CreateBiTree A B C D B 上頁算法執(zhí)行過程舉例如下 : A T B C D ^ ^ ^ ^ ^ scanf(amp。ch)。 if (ch==39。 39。) T = NULL。 else { if (!(T = new BiTNode)) exit(OVERFLOW)。 Tdata = ch。 CreateBiTree(Tlchild)。 CreateBiTree(Trchild)。 僅知二叉樹的先序序列“ abcdefg” 能否唯一確定一棵二叉樹？ 由二叉樹的先序和中序序列建樹 如果同時已知二叉樹的中序序列“ cbdaegf”,則會如何？ 二叉樹的先序序列 二叉樹的中序序列 左子樹 左子樹 右子樹 右子樹 根 根 a b c d e f g c b d a e g f 例如 : a a b b c c d d e e f fg a b c d e f g ^ ^ ^ ^ ^ ^ ^ ^ 先序序列中序序列 線索二叉樹 ? 何謂線索二叉樹？ ? 線索鏈表的遍歷算法 一、 何謂線索二叉樹？ 遍歷二叉樹的結(jié)果是， 求得結(jié)點的一個線性序列。 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)的二叉樹，稱作 “ 線索二叉樹 ” 包含 “線索” 的存儲結(jié)構(gòu)，稱作 “ 線索鏈表 ” A B C D E F G H K ^ D ^ C ^ ^ B E ^ 對 線索鏈表 中結(jié)點的約定： 在二叉鏈表的結(jié)點中 增加兩個標(biāo)志域 ， 并作如下規(guī)定： 若該結(jié)點的左子樹不空， 則 Lchild域的指針指向其左子樹， 且左標(biāo)志域的值為“ 0”； 否則， Lchild域的指針指向其“前驅(qū)”， 且左標(biāo)志的值為“ 1” 。 若該結(jié)點的右子樹不空， 則 rchild域的指針指向其右子樹， 且右標(biāo)志域的值為 “ 0”； 否則， rchild域的指針指向其“后繼”， 且右標(biāo)志的值為“ 1”。 如此定義的二叉樹的存儲結(jié)構(gòu)稱作“ 線索鏈表 ” 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:線索 二、線索鏈表的遍歷算法 : for ( p = firstNode(T)。 p。 p = Succ(p) ) Visit (p)。 由于在線索鏈表中添加了遍歷中得到的“前驅(qū)”和“后繼”的信息，從而簡化了遍歷的算法。 例如 : 對中序線索化鏈表的遍歷算法 ※ 中序遍歷的第一個結(jié)點 ？ ※ 在中序線索化鏈表中結(jié)點的后繼 ？ 左子樹上處于 “最左下” （沒有左子樹）的結(jié)點 若 無右子樹， 則為 后繼線索 所指結(jié)點 否則為 對其 右子樹 進行中序 遍歷 時訪問的 第一個結(jié)點 void InOrderTravers
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1