【正文】 樹的后根遍歷可以借助對應(yīng)二叉樹的中序遍歷算法實現(xiàn)。樹的先根遍歷結(jié)果與其對應(yīng)二叉樹表示的前序遍歷結(jié)果相同。 ? 若 F 不空 ， 則 i. 二叉樹 B 的根是 F 第一棵樹 T1 的根； ii. 其左子樹為 B (T11, T12, … , T1m)， 其中 ， T11, T12, … , T1m 是 T1 的根的子樹； iii. 其右子樹為 B (T2, T3, … , Tn)， 其中 ， T2, T3, … , Tn 是除 T1 外其它樹構(gòu)成的森林 。 } return result。} else{ TreeNodeT *q=pfirstChild。 return Find(root,target)。 return true。 return false。amp。 return true。 //遞歸搜索以 *q為根的子樹 q = qnextSibling。 //*q是 *t長子 bool succ。 if (current == NULL || current == root) { current = NULL。 return false。 //將當(dāng)前結(jié)點的下一個兄弟置為當(dāng)前結(jié)點 bool Parent ()。 } //構(gòu)造函數(shù) bool Root ()。 //根指針及當(dāng)前指針 int Find (TreeNodeT *p, T value)。 d a t a f i r s t C h i l d n e x t S i b l i n gData Structure— Ch5 Tree 2022/1/4 mayan 樹與森林 樹的存儲表示 ? 孩子兄弟表示法（子女 兄弟鏈表表示法） A∧BE∧F∧ ∧C∧D∧G∧ ∧子 女 兄 弟 鏈 表 表 示 法EBAFDGC樹Data Structure— Ch5 Tree 2022/1/4 mayan 樹與森林 樹的子女 兄弟表示的類定義 template class T struct TreeNode { //樹的結(jié)點類 T data。每個結(jié)點由三個域組成： ? firstChild 指向該結(jié)點的第一個子女結(jié)點。 ? 這種存儲表示適合需要頻繁尋找子女的應(yīng)用。p = Next (p)) visit (p)。 //rtag == 0, 表示有右子女 else return p。 while (pltag == 0) p = pleftChild。 prertag = 1。 currentltag = 1。 //后處理中序最后一個結(jié)點 } Data Structure— Ch5 Tree 2022/1/4 mayan 線索二叉樹 通過中序遍歷建立中序線索化二叉樹 //通過中序遍歷 , 對二叉樹進行線索化 template class T void ThreadTreeT::createInThread (ThreadNodeT *current, ThreadNodeT *amp。 線索二叉樹 通過中序遍歷建立中序線索化二叉樹 Data Structure— Ch5 Tree 2022/1/4 mayan 線索二叉樹 通過中序遍歷建立中序線索化二叉樹 template class T void ThreadTreeT::createInThread () { ThreadNodeT *pre = NULL。 //中序遍歷 void preorder(void (*visit)(ThreadNodeT* p))。 //尋找中序下第一個結(jié)點 ThreadNodeT *Last (ThreadNodeT *current)。 pre)。 //線索或子女指針 T data。加上線索的二叉樹稱為 線索二叉樹 。 ?又因為 n個結(jié)點的二叉鏈表中有 n+1個空鏈域，從而得到線索二叉樹的存儲結(jié)構(gòu)如下。 中 序 ： D C B G E A H F I J K后 序 ： D C E G B F H K J I AABCKIFG JHD EData Structure— Ch5 Tree 2022/1/4 mayan 二叉樹 ? 例 3：給定一棵二叉樹的先序和后序序列不能確定一棵二叉樹。 if (pleftChild != NULL) (pleftChild)。 BinTreeNodeT *p = root。 } } } while (! ())。 p = prightChild。 p = 。 } int continue1 = 1。 //p是遍歷指針 do { while (p != NULL) { = p。 tag = R，表示從右子樹退回要訪問根結(jié)點。 } Data Structure— Ch5 Tree 2022/1/4 mayan 二叉樹 二叉樹遍歷的非遞歸算法 ? 利用棧的后序遍歷非遞歸算法 template class T struct stkNode { BinTreeNodeT *ptr。 } if (!()) { //棧不空時退棧 (p)。 //左子樹為空 } } Data Structure— Ch5 Tree 2022/1/4 mayan 二叉樹 二叉樹遍歷的非遞歸算法 ? 利用棧的中序遍歷非遞歸算法 template class T void BinaryTreeT:: InOrder (void (*visit) (BinTreeNodeT *p)) { stackBinTreeNodeT* S。 Data Structure— Ch5 Tree 2022/1/4 mayan 二叉樹 二叉樹遍歷的非遞歸算法 while (p != NULL) { visit(p)。 //遞歸建立右子樹 } else subTree = NULL。 //建立根結(jié)點 Data Structure— Ch5 Tree 2022/1/4 mayan 二叉樹 以遞歸方式建立二叉樹 if (subTree == NULL) {cerr “存儲分配錯 !” endl。 in, BinTreeNodeT *amp。 int j = Height (subTreerightChild)。 //訪問根結(jié)點 }} Data Structure— Ch5 Tree 2022/1/4 mayan 二叉樹 二叉樹遍歷的應(yīng)用 //利用二叉樹后序遍歷算法計算二叉樹的結(jié)點個數(shù) template class T int BinaryTreeT::Size (BinTreeNodeT * subTree) const { if (subTree == NULL) return 0。 //遍歷左子樹 PreOrder (subTreerightChild, visit)。 //遍歷左子樹 visit (subTree)。 Data Structure— Ch5 Tree 2022/1/4 mayan 二叉樹 二叉樹的遍歷 ? 三種遍歷算法： ?先序遍歷：訪問根結(jié)點；先序遍歷左子樹；先序遍歷右子樹。 //建立二叉樹 return in。 templateclass T istreamamp。 Traverse(subTreeleftChild,out)。 if ((p = Parent (subTreeleftChild, current)) != NULL) //遞歸在左子樹中搜索 return p。 //刪除右子樹 delete subTree。 Tree)。 Tree)。 Tree, void (*visit) (BinTreeNodeT *p))。 subTree, void (*visit) (BinTreeNodeT *p))。 x) const。 //復(fù)制 int Height (BinTreeNodeT *subTree)。 subTree)。 //從文件讀入建樹 bool Insert (BinTreeNodeT *amp。 //二叉樹的根指針 T RefValue。 } //后序遍歷 void levelOrder (void (*visit)(BinTreeNodeT *p))。 } //求結(jié)點數(shù) BinTreeNodeT *getRoot () const { return root。 } BinTreeNodeT *LeftChild (BinTreeNodeT *current) //返回左子女 { return (current != NULL)?currentleftChild : NULL。 s)。 leftChild = l。 ? 在含有 n個結(jié)點的二叉鏈表中有 n+1個空鏈指針域，三叉鏈表則有 n+2個空鏈指針域。 //層次序遍歷 , visit是訪問函數(shù) }。 //取根 void preOrder (void (*visit) (BinTreeNodeT *p))。 item)const。 //求結(jié)點 current 的左子女 BinTreeNodeT *RightChild (BinTreeNodeT *current)。 //求樹深度或高度 int Size ()。 12 34 65 78 91 0 1 1 1 2 1 3 1 4 1 5滿 二 叉 樹12 34 65 78 91 0完 全 二 叉 樹Data Structure— Ch5 Tree 2022/1/4 mayan 二叉樹 二叉樹的性質(zhì) ? 性質(zhì) 4 具有 n (n≥0) 個結(jié)點的完全二叉樹的深度為 ?log2(n+1)?。 ? 證明：因為每一層最少要有 1個結(jié)點 ， 因此 ， 最少結(jié)點數(shù)為 k。 //遍歷以 p 為根的子樹 }。 //在結(jié)點 p 下插入值為 value 的新子女 , 若插 //入失敗 , 函數(shù)返回 false, 否則返回 true Data Structure— Ch5 Tree 2022/1/4 mayan 樹 樹的抽象數(shù)據(jù)類型 bool DeleteChild (position p, int i)。 //返回 p 下一兄弟地址 , 若無下一兄弟返回 0 position Parent(position p)。 BuildRoot (const Tamp。 AB C DE F G H I JK L M1 層2 層3 層4 層d e p t h h e i g h tData Structure— Ch5 Tree 2022/1/4 mayan 樹 樹的抽象數(shù)據(jù)類型 template class T class Tree { //在類界面中的 position 是樹中結(jié)點的地址。 ?樹的高度 ：等于根結(jié)點的高度，即根結(jié)點所有子女高度的最大值加一。 ?結(jié)點的層次 ：規(guī)定根結(jié)點在第一層，其子女結(jié)點的層次等于它的層次加一。 ? 分支結(jié)點： 度不為 0的結(jié)點即為分支結(jié)點 ， 亦稱為非終端結(jié)點 。 ??????00n,T,... ,T,Tr,n,Tm21 }{ΦData Structure— Ch5 Tree 2022/1/4 mayan 樹 樹的定義和術(shù)語 ? 相關(guān)術(shù)語 ? 子女 ：若結(jié)點的子樹非空 ， 結(jié)點子樹的根即為該結(jié)點的子女 。 ? 自由樹： 一棵自由樹 Tf 可定義為一個二元組 Tf = (V, E)，其中 V = {v1, ..., vn} 是由 n (n＞ 0) 個元素組成的有限非空集合，稱為頂點（ vertex）集合。E = {(vi, vj) | vi, vj V, 1≤i, j≤n} 是 n1個序?qū)Φ募希Q為邊集合， E 中的元