【正文】 }。 //線索標(biāo)志 ThreadNodeT *leftChild, *rightChild。對(duì)二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程叫 線索化。 l e f t C h i l d l t a g d a t a r t a g r i g h t C h i l dData Structure— Ch5 Tree 2022/1/4 mayan 線索二叉樹 線索二叉樹的概念 ? 其中，指向結(jié)點(diǎn)前驅(qū)和后繼的指針叫做 線索 。 Data Structure— Ch5 Tree 2022/1/4 mayan 線索二叉樹 線索二叉樹的概念 ? 規(guī)定：若結(jié)點(diǎn)有左子樹，則 leftChild指示其左孩子，否則令 leftChild指示其前驅(qū)；若結(jié)點(diǎn)有右子樹，則其 rightChild域指示其右孩子，否則令 rightChild指示其后繼。就提出了線索二叉樹的概念。 A ABB1 先 序 ： A B 后 序 ： B A2 先 序 ： A B 后 序 ： B A12Data Structure— Ch5 Tree 2022/1/4 mayan 線索二叉樹 線索二叉樹的概念 ? 為什么提出線索二叉樹？ ?遍歷的過程實(shí)質(zhì)上是對(duì)一個(gè)非線性結(jié)構(gòu)進(jìn)行線性化的操作，使每個(gè)結(jié)點(diǎn)（除第一個(gè)和最后一個(gè)）在這個(gè)線性序列中有且僅有一個(gè)直接前驅(qū)和直接后繼。 EBAIFKD HGC先 序 ： E B A D C F H G I K J中 序 ： A B C D E F G H I J KJData Structure— Ch5 Tree 2022/1/4 mayan 二叉樹 ? 例 2：給定一棵二叉樹的中序序列 DCBGEAHFIJK和后序序列 DCEGBFHKJIA，畫出這顆二叉樹。 if (prightChild != NULL) (prightChild)。 visit (p)。 (p)。 QueueBinTreeNodeT * Q。 //繼續(xù)遍歷其他結(jié)點(diǎn) cout endl。 break。 break。 continue1 = 0。 switch () { //判斷棧頂?shù)?tag標(biāo)記 case L: = R。 ! ()) { (w)。 //繼續(xù)循環(huán)標(biāo)記 , 用于 R Data Structure— Ch5 Tree 2022/1/4 mayan 二叉樹 二叉樹遍歷的非遞歸算法 while (continue1 amp。 p = pleftChild。 = L。 BinTreeNodeT * p = root。 Data Structure— Ch5 Tree 2022/1/4 mayan 二叉樹 二叉樹遍歷的非遞歸算法 template class T void BinaryTreeT:: PostOrder (void (*visit) (BinTreeNodeT *p) { StackstkNodeT S。 tag = L, 表示從左子樹退回還要遍歷右子樹 。 //樹結(jié)點(diǎn)指針 enum tag {L, R}。 //遍歷指針進(jìn)到右子女 } } while (p != NULL || ! ())。 visit (p)。 //該子樹沿途結(jié)點(diǎn)進(jìn)棧 p = pleftChild。 BinTreeNodeT *p = root。 //進(jìn)左子樹 else (p)。 //訪問結(jié)點(diǎn) if (prightChild != NULL) (prightChild)。 (NULL)。 //封閉指向空子樹的指針 } } Data Structure— Ch5 Tree 2022/1/4 mayan 二叉樹 二叉樹遍歷的非遞歸算法 ? 利用棧的前序遍歷非遞歸算法 template class T void BinaryTreeT:: PreOrder (void (*visit) (BinTreeNodeT *p) ) { stackBinTreeNodeT* S。 //遞歸建立左子樹 CreateBinTree (in, subTreerightChild)。 exit (1)。 //讀入根結(jié)點(diǎn)的值 if (item != RefValue) { subTree = new BinTreeNodeT(item)。 subTree) { T item。 templateclass T void BinaryTreeT::CreateBinTree (ifstreamamp。 return (i j) ? j+1 : i+1。 //空樹高度為 0 else { int i = Height (subTreeleftChild)。 //空樹 else return 1+Size (subTreeleftChild)+ Size (subTreerightChild)。 //遍歷右子樹 visit (subTree)。 //遍歷右子樹 } } Data Structure— Ch5 Tree 2022/1/4 mayan 二叉樹 二叉樹的遍歷 ? 二叉樹后序遍歷的遞歸算法 template class T void BinaryTreeT::PostOrder (BinTreeNodeT * subTree, void (*visit) (BinTreeNodeT *p ) { if (subTree != NULL ) { PostOrder (subTreeleftChild, visit)。 //訪問根結(jié)點(diǎn) PreOrder (subTreeleftChild, visit)。 //訪問根結(jié)點(diǎn) InOrder (subTreerightChild, visit)。 abcidjehfg中 序 ： e c b h f d j i g a先 序 ： a b c e d f h g i j后 序 ： e c h f j i g d b aData Structure— Ch5 Tree 2022/1/4 mayan 二叉樹 二叉樹的遍歷 ? 二叉樹中序遍歷的遞歸算法 template class T void BinaryTreeT::InOrder (BinTreeNodeT * subTree, void (*visit) (BinTreeNodeT *p)) { if (subTree != NULL) { InOrder (subTreeleftChild, visit)。 ?中序遍歷：中序遍歷左子樹；訪問根結(jié)點(diǎn)；中序遍歷右子樹。 ? 令 L、 R、 V分別代表遍歷一個(gè)結(jié)點(diǎn)的左子樹、右子樹和訪問該結(jié)點(diǎn)的操作，則可能有 VLR, LVR,LRV,VRL,RVL,RLV六種遍歷二叉樹的規(guī)則，若規(guī)定先左后右則有 VLR（前序遍歷）、 LVR（中序遍歷）、 LRV（后序遍歷）三種。 } Data Structure— Ch5 Tree 2022/1/4 mayan 二叉樹 二叉樹的遍歷 ? 二叉樹的 遍歷 （ Binary Tree Traversal）就是按某種次序訪問樹中的結(jié)點(diǎn)，要求每個(gè)結(jié)點(diǎn)訪問一次且僅訪問一次。 Tree) { CreateBinTree (in, )。 operator (istreamamp。 in是輸入流對(duì)象。 Traverse(subTreerightChild,out)。 out){ if(subTree!=NULL){ outsubTreedata? ?。 else return Parent (subTreerightChild, current)。 //找到 , 返回父結(jié)點(diǎn)地址 Data Structure— Ch5 Tree 2022/1/4 mayan 二叉樹 二叉鏈表的函數(shù)實(shí)現(xiàn) BinTreeNode T *p。 //刪除根結(jié)點(diǎn) } } Data Structure— Ch5 Tree 2022/1/4 mayan 二叉樹 二叉鏈表的函數(shù)實(shí)現(xiàn) //從結(jié)點(diǎn) subTree 開始 , 搜索結(jié)點(diǎn) current 的雙親 , //若找到則返回雙親結(jié)點(diǎn)地址 , 否則返回 NULL template class T BinTreeNodeT *BinaryTreeT::Parent (BinTreeNode T *subTree, BinTreeNode T *current) { if (subTree == NULL) return NULL。 //刪除左子樹 destroy (subTreerightChild)。//重載操作：輸出 }。 out, BinaryTreeTamp。//重載操作：輸入 friend ostreamamp。 in, BinaryTreeTamp。 //后序遍歷 friend istreamamp。 //中序遍歷 void postOrder (BinTreeNodeTamp。 //前序遍歷 void inOrder (BinTreeNodeTamp。 //前序遍歷輸出 Data Structure— Ch5 Tree 2022/1/4 mayan 二叉樹 二叉鏈表的類定義 void preOrder (BinTreeNodeTamp。 //搜尋 x void Traverse (BinTreeNodeT *subTree, ostreamamp。 //返回父結(jié)點(diǎn) BinTreeNodeT *Find (BinTreeNodeT *subTree, const Tamp。 //返回樹高度 int Size (BinTreeNodeT *subTree)。 //查找 Data Structure— Ch5 Tree 2022/1/4 mayan 二叉樹 二叉鏈表的類定義 BinTreeNodeT *Copy (BinTreeNodeT *orignode)。 //刪除 bool Find (BinTreeNodeT *subTree, const Tamp。 //插入 void destroy (BinTreeNodeT *amp。 subTree, const Tamp。 subTree)。 //數(shù)據(jù)輸入停止標(biāo)志 void CreateBinTree (istreamamp。 //搜索 Data Structure— Ch5 Tree 2022/1/4 mayan 二叉樹 二叉鏈表的類定義 protected: BinTreeNodeT *root。 //層次序遍歷 int Insert (const T item)。 } //中序遍歷 void postOrder (void (*visit) (BinTreeNodeT *p)) { postOrder (root, visit)。 } //取根 void preOrder (void (*visit) (BinTreeNodeT *p)) { preOrder (root, visit)。 } //求樹高度 int Size () { return Size(root)。 } Data Structure— Ch5 Tree 2022/1/4 mayan 二叉樹 二叉鏈表的類定義 BinTreeNodeT *RightChild (BinTreeNodeT *current) //返回右子女 { return (current != NULL)？ currentrightChild : NULL。} //判二叉樹空否 BinTreeNodeT *Parent (BinTreeNode T *current) //返回雙親結(jié)點(diǎn) { return (root == NULL || root == current) ? NULL : Parent (root, t)。 //復(fù)制構(gòu)造函數(shù)