【正文】 void levelOrder (void (*visit)(BinTreeNodeT *p))。 //層次序遍歷 , visit是訪問(wèn)函數(shù) }。 Data Structure— Ch5 Tree 2022/1/4 mayan 二叉樹(shù) 二叉樹(shù)的數(shù)組存儲(chǔ)表示 ab cd fe gh ij ka b c d e f g h i j1 2 3 4 5 6 7 8 9 1 0完 全 二 叉 樹(shù) 的 數(shù) 組 存 儲(chǔ)ab cd e fgha b c d e f g1 2 3 4 5 6 7 8 9 1 0一 般 二 叉 樹(shù) 的 數(shù) 組 存 儲(chǔ)k1 1h1 1acfa c f1 2 3 4 5 6 7極 端 情 形 單 支 樹(shù)Data Structure— Ch5 Tree 2022/1/4 mayan 二叉樹(shù) 二叉樹(shù)的鏈表存儲(chǔ)表示 ? 二叉鏈表和三叉鏈表的概念 ?二叉樹(shù)結(jié)點(diǎn)定義：每個(gè)結(jié)點(diǎn)有 3個(gè)域， data域存儲(chǔ)結(jié)點(diǎn)數(shù)據(jù)， leftChild和 rightChild分別存放指向左子女和右子女的指針。 ?二叉鏈表如下圖所示： l e f t C h i l d d a t a r i g h t C h i l dl e f t C h i l dd a t ar i g h t C h i l d二 叉 鏈 表Data Structure— Ch5 Tree 2022/1/4 mayan 二叉樹(shù) 二叉樹(shù)的鏈表存儲(chǔ)表示 ?每個(gè)結(jié)點(diǎn)增加一個(gè)指向雙親的指針 parent，使得查找雙親也很方便。 l e f t C h i l d d a t a p a r e n tl e f t C h i l dd a t ar i g h t C h i l d三 叉 鏈 表r i g h t C h i l dp a r e n tData Structure— Ch5 Tree 2022/1/4 mayan 二叉樹(shù) 二叉樹(shù)的鏈表存儲(chǔ)表示 ? 整個(gè)二叉樹(shù)的鏈表有一個(gè)表頭指針，他指向二叉樹(shù)的根結(jié)點(diǎn)。 ? 在含有 n個(gè)結(jié)點(diǎn)的二叉鏈表中有 n+1個(gè)空鏈指針域，三叉鏈表則有 n+2個(gè)空鏈指針域。 2n(n1)=n+1 n+1+1=n+2 Data Structure— Ch5 Tree 2022/1/4 mayan 二叉樹(shù) 二叉樹(shù)的鏈表存儲(chǔ)表示 ABC DE F二 叉 樹(shù)A∧BC∧ ∧ DE∧ ∧ F∧ ∧二 叉 鏈 表r o o tA∧BC∧ DE∧ F∧三 叉 鏈 表r o o t∧∧∧ ∧二叉樹(shù)的鏈表表示 Data Structure— Ch5 Tree 2022/1/4 mayan 二叉樹(shù) 二叉鏈表的類(lèi)定義 template class T struct BinTreeNode {//二叉樹(shù)結(jié)點(diǎn)類(lèi)定義 T data。 //數(shù)據(jù)域 BinTreeNodeT *leftChild, *rightChild。 //左子女、右子女鏈域 BinTreeNode ():leftChild(NULL),rightChild(NULL){} //構(gòu)造函數(shù) BinTreeNode (T x, BinTreeNodeT *l = NULL, BinTreeNodeT *r = NULL) { data = x。 leftChild = l。 rightChild = r。 }}。 Data Structure— Ch5 Tree 2022/1/4 mayan 二叉樹(shù) 二叉鏈表的類(lèi)定義 template class T class BinaryTree { //二叉樹(shù)類(lèi)定義 public: BinaryTree () : root (NULL) { } //構(gòu)造函數(shù) BinaryTree (T value) : RefValue(value), root(NULL) { } //構(gòu)造函數(shù) BinaryTree (BinaryTreeTamp。 s)。 //復(fù)制構(gòu)造函數(shù) ~BinaryTree () { destroy(root)。 } //析構(gòu)函數(shù) Data Structure— Ch5 Tree 2022/1/4 mayan 二叉樹(shù) 二叉鏈表的類(lèi)定義 bool IsEmpty () { return root == NULL。} //判二叉樹(shù)空否 BinTreeNodeT *Parent (BinTreeNode T *current) //返回雙親結(jié)點(diǎn) { return (root == NULL || root == current) ? NULL : Parent (root, t)。 } BinTreeNodeT *LeftChild (BinTreeNodeT *current) //返回左子女 { return (current != NULL)?currentleftChild : NULL。 } Data Structure— Ch5 Tree 2022/1/4 mayan 二叉樹(shù) 二叉鏈表的類(lèi)定義 BinTreeNodeT *RightChild (BinTreeNodeT *current) //返回右子女 { return (current != NULL)？ currentrightChild : NULL。 } int Height () { return Height(root)。 } //求樹(shù)高度 int Size () { return Size(root)。 } //求結(jié)點(diǎn)數(shù) BinTreeNodeT *getRoot () const { return root。 } //取根 void preOrder (void (*visit) (BinTreeNodeT *p)) { preOrder (root, visit)。 } //前序遍歷 Data Structure— Ch5 Tree 2022/1/4 mayan 二叉樹(shù) 二叉鏈表的類(lèi)定義 void inOrder (void (*visit) (BinTreeNodeT *p)) { inOrder (root, visit)。 } //中序遍歷 void postOrder (void (*visit) (BinTreeNodeT *p)) { postOrder (root, visit)。 } //后序遍歷 void levelOrder (void (*visit)(BinTreeNodeT *p))。 //層次序遍歷 int Insert (const T item)。 //插入新元素 BinTreeNodeT *Find (T item) const。 //搜索 Data Structure— Ch5 Tree 2022/1/4 mayan 二叉樹(shù) 二叉鏈表的類(lèi)定義 protected: BinTreeNodeT *root。 //二叉樹(shù)的根指針 T RefValue。 //數(shù)據(jù)輸入停止標(biāo)志 void CreateBinTree (istreamamp。 in,BinTreeNodeT *amp。 subTree)。 //從文件讀入建樹(shù) bool Insert (BinTreeNodeT *amp。 subTree, const Tamp。 x)。 //插入 void destroy (BinTreeNodeT *amp。 subTree)。 //刪除 bool Find (BinTreeNodeT *subTree, const Tamp。 x)。 //查找 Data Structure— Ch5 Tree 2022/1/4 mayan 二叉樹(shù) 二叉鏈表的類(lèi)定義 BinTreeNodeT *Copy (BinTreeNodeT *orignode)。 //復(fù)制 int Height (BinTreeNodeT *subTree)。 //返回樹(shù)高度 int Size (BinTreeNodeT *subTree)。 //返回結(jié)點(diǎn)數(shù) BinTreeNodeT *Parent (BinTreeNodeT * subTree, BinTreeNodeT *current)。 //返回父結(jié)點(diǎn) BinTreeNodeT *Find (BinTreeNodeT *subTree, const Tamp。 x) const。 //搜尋 x void Traverse (BinTreeNodeT *subTree, ostreamamp。 out)。 //前序遍歷輸出 Data Structure— Ch5 Tree 2022/1/4 mayan 二叉樹(shù) 二叉鏈表的類(lèi)定義 void preOrder (BinTreeNodeTamp。 subTree, void (*visit) (BinTreeNodeT *p))。 //前序遍歷 void inOrder (BinTreeNodeTamp。 subTree, void (*visit) (BinTreeNodeT *p))。 //中序遍歷 void postOrder (BinTreeNodeTamp。 Tree, void (*visit) (BinTreeNodeT *p))。 //后序遍歷 friend istreamamp。 operator (istreamamp。 in, BinaryTreeTamp。 Tree)。//重載操作：輸入 friend ostreamamp。 operator (ostreamamp。 out, BinaryTreeTamp。 Tree)。//重載操作：輸出 }。 Data Structure— Ch5 Tree 2022/1/4 mayan 二叉樹(shù) 二叉鏈表的函數(shù)實(shí)現(xiàn) //私有函數(shù) : 刪除根為 subTree的子樹(shù) templateclass T void BinaryTreeT::destroy (BinTreeNodeT * subTree) { if (subTree != NULL) { destroy (subTreeleftChild)。 //刪除左子樹(shù) destroy (subTreerightChild)。 //刪除右子樹(shù) delete subTree。 //刪除根結(jié)點(diǎn) } } Data Structure— Ch5 Tree 2022/1/4 mayan 二叉樹(shù) 二叉鏈表的函數(shù)實(shí)現(xiàn) //從結(jié)點(diǎn) subTree 開(kāi)始 , 搜索結(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。 if (subTreeleftChild == current || subTreerightChild == current ) return subTree。 //找到 , 返回父結(jié)點(diǎn)地址 Data Structure— Ch5 Tree 2022/1/4 mayan 二叉樹(shù) 二叉鏈表的函數(shù)實(shí)現(xiàn) BinTreeNode T *p。 if ((p = Parent (subTreeleftChild, current)) != NULL) //遞歸在左子樹(shù)中搜索 return p。 else return Parent (subTreerightChild, current)。 //遞歸在右子樹(shù)中搜索 } Data Structure— Ch5 Tree 2022/1/4 mayan 二叉樹(shù) 二叉鏈表的函數(shù)實(shí)現(xiàn) //前序遍歷輸出 template class T void Traverse (BinTreeNodeT *subTree, ostreamamp。 out){ if(subTree!=NULL){ outsubTreedata? ?。 Traverse(subTreeleftChild,o