树和森林的概念二叉树二叉树遍历二叉树的计数线索化二叉

树和森林的概念二叉树二叉树遍历二叉树的计数线索化二叉内容摘要：

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  。