樹和森林的概念二叉樹二叉樹遍歷二叉樹的計數線索化二叉(編輯修改稿)

　

【文章內容簡介】 template class Type int BinaryTreeType :: Height ( const BinTreeNode Type * t ) const { if ( t == NULL ) return 1。 else return 1 + Max ( Height ( tleftChild ), Height ( trightChild ) )。 } 利用棧的前序遍歷非遞歸算法 a b c d e c d c c 訪問 a 進棧 c 左進 b 訪問 b 進棧 d 左進 空 退棧 d 訪問 d 左進 空 退棧 c 訪問 c 左進 e 訪問 e 左進 空 棧空 結束 template class Type void BinaryTreeType :: PreOrder( ) { stack TreeNodeType* S。 BinTreeNodeType * p = root。 //初始化 ( NULL )。 while ( p != NULL ) { cout pdata endl。 if ( prightChild != NULL ) ( prightChild )。 //預留右子樹指針在棧中 利用棧的前序遍歷非遞歸算法 if ( pleftChild != NULL ) p = pleftChild。 //進左子樹 else { p = ( )。 ( )。 } //左子樹為空 , 進右子樹 } } 利用棧的中序遍歷非遞歸算法 template class Type void BinaryTreeType :: InOrder ( ) { stack TreeNodeType* S。 利用棧的中序遍歷非遞歸算法 a b c d e b a a d a a 左空 退棧 訪問 左空 退棧 訪問 退棧 訪問 左空 e c 退棧訪問 c c 右空 退棧訪問 棧空結束 BinTreeNodeType * p = root。 //初始化 do { while ( p != NULL ) { (p)。 p = pleftChild。 } if ( !( ) ) { //棧非空 p = ( )。 ( )。 //退棧 cout pdata endl。 //訪問根 p = prightChild。 //向右鏈走 } } while ( p != NULL || !( ) )。 } 利用棧的后序遍歷非遞歸算法 后序遍歷時使用的棧的結點定義 template class Type struct stkNode { BinTreeNodeType *ptr。 enum tag{ L, R }。 //該結點退棧標記 stkNode( BinTreeNodeType* N = NULL ) : ptr (N), tag ( L ) { } //構造函數 }。 根結點的 tag = L，表示從左子樹退出 , 訪問右子樹。 tag = R, 表示 從右子樹退出 , 訪問根。 ptr tag{L,R} a b c d e aL bL aL bR aL dL bR aL dR bR aL bR aL aL aR eL cL aR eR cL aR cL aR cR aR aR template class Type void BinaryTreeType :: PostOrder ( ) { stack stkNodeType S。 stkNodeType w。 BinTreeNodeType * p = root。 do { while ( p != NULL ) { //向左子樹走 = p。 = L。 ( w )。 p = pleftChild。 } int continue = 1。 //繼續循環標記 while ( continue amp。amp。 !( ) ) { w = ( )。 ( )。 p = 。 switch ( ) { //判斷棧頂 tag標記 case L : = R。 ( w )。 continue = 0。 p = prightChild。 break。 case R : cout pdata endl。 } } } while ( p != NULL || !( ) )。 cout endl。 } 二叉樹的計數 由二叉樹的前序序列和中序序列可唯一地確定一棵二叉樹。 例 前序序列 { ABHFDECKG } 和中序序列 { HBDFAEKCG }, 構造二叉樹過程如下： HBDF EKCG A EKCG A B H DF KCG 前序序列 { ABHFDECKG } EKCG A B H DF EKCG A B H F D E A B H F D E A B H F D C K G 如果前序序列固定不變，給出不同的中序序列，可得到不同的二叉樹。 6 1 2 3 4 5 7 8 9 6 1 2 3 7 5 8 4 9 固定前序排列 ,選擇所有可能的中序排列 ,可以構造多少種不同的二叉樹？ 例如 , 有 3 個數據 { 1, 2, 3 }，可得 5 種不同的二叉樹。它們的前序排列均為 123， 中序序列可能是 123， 132， 213， 231， 321。 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 有 0個 , 1個 , 2個 , 3個結點的不同二叉樹如下 b0 =1 b1 =1 b2 =2 b3 =5 b4 =14 !!)!(211112 nnnnnb C n nn?????計算具有 n 個結點的不同二叉樹的棵數 Catalan函數 bi bni1 1 ???????101niinin bbb線索化二叉樹 (Threaded Binary Tree) 線索 (Thread) 增加 Pred 指針和 Succ 指針的二叉樹 線索化二叉樹及其二叉鏈表表示 LeftThread=0, LeftChild為 左子女指針 LeftThread=1, LeftChild為 前驅線索 RightThread=0, RightChild為 右子女指針 RightThread=1, RightChild為 后繼指針 LeftChild RightChild data LeftThread RightThread 中序線索化二叉樹的類定義 template class Type class ThreadTree。 template class Type class ThreadNode { friend class ThreadTreeType。 private: int leftThread, rightThread。 ThreadNodeType *leftChild, *rightChild。 Type data。 public: ThreadNode ( const Type item ) : data (item), leftChild (NULL), rightChild (NULL), leftThread (0), rightThread (0) { } }。 template class Type class ThreadTree { private: ThreadNodeType * root。 //根 InThread ( ThreadNode Type * current, ThreadNode Type * pre )。 //建樹 public: ThreadTree ( ) : root (NULL) { }。 //構造函數 ThreadNodeType * First ( ThreadNode Type * current )。 ThreadNodeType * Last ( ThreadNode Type * current )。 ThreadNodeType * Next ( ThreadNode Type * current )。 ThreadNodeType * Prior ( ThreadNode Type * current )。 ………… } 通過中序遍歷建立中序線索化二叉樹 template class Type void ThreadTreeType :: InThread ( ThreadNodeType * current, ThreadNodeType *amp。 pre ) { if ( current != NULL ) { InThread ( currentleftChild, pre )。 //遞歸 , 左子樹線索化 if ( currentleftChild == NULL ) { currentleftChild = pre。 currentleftThread = 1。 } //建立當前結點的前驅線索 if ( pre != NULL amp。amp。 prerightChild == NULL ) { prerightChild = current。 prerightThread = 1。 } //建立前驅結點的后繼線索 pre = current。 //前驅跟上當前指針 InThread ( currentrightChild, pre )。 //遞歸 , 右子樹線索化 } } template class Type void ThreadTreeType :: CreateInThread ( ) { ThreadNodeType *pre = NULL。 //前驅指針 if ( root != NULL ) { //非空二叉樹 , 線索化 InThread ( root, pre )。 //中序遍歷線索化二叉樹 prerightChild = NULL。 prerightThread = 1。 //后處理 , 中序最后一個結點 } } 0 A 0 ? 0 B 0 0 C 0 ? ? 0 D 0 ? ?