【正文】 deType * RightChild ( )。 item )。item ) const。 //取得結(jié)點數(shù)據(jù) BinTreeNodeType *GetRoot ( ) const。 template class Type Class BinTreeNode { friend class BinaryTreeType。 BinTreeNodeType * leftChild。 public: BinTreeNode ( ) : leftChild (NULL), rightChild (NULL) { } 二叉樹的類定義 BinTreeNode ( Type item, BinTreeNodeType *left = NULL, BinTreeNodeType *right = NULL ) : data (item), leftChild (left), rightChild (right) { } Type GetData ( ) const { return data。 } BinTreeNodeType * GetRight ( ) const { return rightChild。 item ) { data = item。 } void SetRight ( BinTreeNode Type * R ) { rightChild = R。 template class Type class BinaryTree { private: BinTreeNode Type *root。 void CreateBinTree ( ifstreamamp。 current )。 int Insert ( BinTreeNodeType * amp。item )。out ) const //遍歷 int Find ( BinTreeNodeType *current, const Type amp。 //刪除 public: virtual BinaryTree ( ) : root (NULL) { } virtual BinaryTree ( Type value ) : RefValue (value), root (NULL) { } virtual ~BinaryTree ( ) { destroy ( root )。 } virtual BinTreeNode Type * Parent ( BinTreeNode Type *current ) { return root == NULL || root == current？ NULL : Parent ( root, current )。 } virtual BinTreeNodeType * RightChild ( BinTreeNodeType *current ) //取 current結(jié)點的右子女 { return root != NULL ? currentrightChild : NULL。 item)。 item ) const。 } //取根 friend istreamamp。 Tree) //重載操作：輸入 friend ostreamamp。out, BinaryTreeTypeamp。 destroy ( current rightChild )。 } } templateclass Type void BinaryTree Type :: CreateBinTree ( ifstreamamp。 current ) { //私有函數(shù) : 以遞歸方式建立二叉樹 。 并約定以輸入序列中不可 //能出現(xiàn)的值作為空結(jié)點的值以結(jié)束遞歸 , //此值在 RefValue中 。 Type item。 //讀入根結(jié)點的值 if ( item != RefValue ) { current = new BinTreeNodeType ( item )。 exit (1)。 CreateBinTree ( in, currentrightChild )。 //封閉葉結(jié)點 } } template class Type BinTreeNode Type * BinaryTree Type :: Parent ( BinTreeNode Type * start, BinTreeNode Type * cuurent ) { if ( start == NULL ) return NULL。 BinTreeNode Type *p。 else return Parent(startrightChild, current)。out ) const { //私有函數(shù) : 搜索并輸出根為 current的二叉樹 if ( current != NULL ) { out currentdata ? ?。 Traverse ( currentrightChild, out )。 operator ( filename, BinaryTreeType amp。 in是輸入流對象 Type item。 if ( !fin ) { cerr “文件未發(fā)現(xiàn) !” endl。 } CreateBinTree ( ifstreamamp。 ( )。 operator ( ostreamamp。Tree ) { out “二叉樹的前序遍歷 .\n。 out endl。 } 二叉樹遍歷 樹的遍歷就是按某種次序訪問樹中的結(jié)點，要求每個結(jié)點訪問一次且僅訪問一次。 遍歷結(jié)果 a + b * c d e / f 中序遍歷 (Inorder Traversal) / + * a b c d e f 二叉樹遞歸的中序遍歷算法 template class Type void BinaryTree Type :: InOrder ( BinTreeNode Type *current ) { if ( current != NULL ) { InOrder ( currentleftChild )。 InOrder ( currentrightChild )。 遍歷結(jié)果 + a * b c d / e f 前序遍歷 (Preorder Traversal) / + * a b c d e f 二叉樹遞歸的前序遍歷算法 template class Type void BinaryTreeType :: PreOrder ( BinTreeNode Type * current ) { if ( current != NULL ) { cout currentdata。 PreOrder ( currentrightChild )。 遍歷結(jié)果 a b c d * + e f / 后序遍歷 (Postorder Traversal) / + * a b c d e f 二叉樹遞歸的后序遍歷算法 template class Type void BinaryTree Type :: PostOrder ( BinTreeNode Type * current ) { if ( current != NULL ) { PostOrder ( currentleftChild )。 cout currentdata。 else return 1 + Count ( tleftChild ) + Count ( trightChild )。 else return 1 + Max ( Height ( tleftChild ), Height ( trightChild ) )。 BinTreeNodeType * p = root。 while ( p != NULL ) { cout pdata endl。 //預留右子樹指針在棧中 利用棧的前序遍歷非遞歸算法 if ( pleftChild != NULL ) p = pleftChild。 ( )。 利用棧的中序遍歷非遞歸算法 a b c d e b a a d a a 左空 退棧 訪問 左空 退棧 訪問 退棧 訪問 左空 e c 退棧訪問 c c 右空 退棧訪問 ?？战Y(jié)束 BinTreeNodeType * p = root。 p = pleftChild。 ( )。 //訪問根 p = prightChild。 } 利用棧的后序遍歷非遞歸算法 后序遍歷時使用的棧的結(jié)點定義 template class Type struct stkNode { BinTreeNodeType *ptr。 //該結(jié)點退棧標記 stkNode( BinTreeNodeType* N = NULL ) : ptr (N), tag ( L ) { } //構(gòu)造函數(shù) }。 tag = R, 表示 從右子樹退出 , 訪問根。 stkNodeType w。 do { while ( p != NULL ) { //向左子樹走 = p。 ( w )。 } int continue = 1。amp。 ( )。 switch ( ) { //判斷棧頂 tag標記 case L : = R。 continue = 0。 break。 } } } while ( p != NULL || !( ) )。 } 二叉樹的計數(shù) 由二叉樹的前序序列和中序序列可唯一地確定一棵二叉樹。 6 1 2 3 4 5 7 8 9 6 1 2 3 7 5 8 4 9 固定前序排列 ,選擇所有可能的中序排列 ,可以構(gòu)造多少種不同的二叉樹？ 例如 , 有 3 個數(shù)據(jù) { 1, 2, 3 }，可得 5 種不同的二叉樹。 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 有 0個 , 1個 , 2個 , 3個結(jié)點的不同二叉樹如下 b0 =1 b1 =1 b2 =2 b3 =5 b4 =14 !!)!(211112 nnnnnb C n nn?????計算具有 n 個結(jié)點的不同二叉樹的棵數(shù) Catalan函數(shù) bi bni1 1 ???????101niinin bbb線索化二叉樹 (Threaded Binary Tree) 線索 (Thread) 增加 Pred 指針和 Succ 指針的二叉樹 線索化二叉樹及其二叉鏈表表示 LeftThrea