数据结构——C++实现 作者 缪淮扣 顾训穰 沈俊 数据结构-第六章.pptVIP

树的概念 2．中序线索化二叉树中的部分成员函数的实现 在中序线索树中寻找中序序列中的最后一个结点的算法如下： template class Type ThreadBinTreeNodeType*ThreadInorderTreeType:: ThreadInOrderLast( ) { if (T.root→leftTag == 0) { current = T.root→GetLeftChild( ); while ( current→rightTag == 0 ) current = current→GetRightChild( ); return current; } else return NULL; } 中序线索树中寻找当前结点CURRENT的中序后继结点的算法如下： template class Type ThreadBinTreeNodeType*ThreadInorderTreeType:: ThreadInOrderNext(){ //在线索树中寻找CURRENT的中序后继 ThreadBinTreeNodeType *p = current→GetRightChild( ); if ( current→rightTag == 0 ) //CURRENT有右孩子 while ( p→leftTag == 0 ) p = p→GetLeftChild( ); current = p; if ( current == T.root ) return NULL; else return current; } 在中序线索树中进行中序遍历，可以通过从第一个结点开始依次找当前结点的后继来完成。算法的描述如下： template class Type void ThreadInorderTreeType ::Inorder ( ) { ThreadBinTreeNodeType * p; for( p = T.root→GetLeftChild( )); p != NULL; p = ThreadInOrderNext ( ) ) cout p.GetData endl; } 3. 在中序线索二叉树上插入结点 在中序线索二叉树上插入结点有两种方法：一种是将新结点插入到二叉树中作为某结点的左孩子结点；另一种方法是将新结点插入到二叉树中作为某结点的右孩子结点。在此讨论后一种情况。 假设指针p指向线索二叉树中的某一结点，指针x指向要插入的新结点，新结点x将插入到二叉树中作为结点p的右孩子。此时，将有两种情况 第一种情况：结点p没有右孩子，则插入过程很简单，下图 (a)、(b)给出了这种情况下插入前后二叉树的两种形态。这时结点P原来的后继结点变为结点x的后继结点，结点p为结点x的前驱结点，结点 x成为结点p的右孩子。 第二种情况：若结点P有右子树，结点x插入后，令结点p原来的右子树成为结点x的右子树，x为P的右孩子。此时，结点p成为结点x的前驱结点，根据中序线索二叉树的定义，这时还需修改结点p原来右子树中最左下结点的左指针，使它由原来指向结点p改为指向结点x。下图 (c)、(d)给出了这种情况下插入前后二叉树的两种形态。 插入结点的算法如下： templateclass type void ThreadBinTreetype:: insertRight(ThreadBinTreeNodetype *p, ThreadBinTreeNodetype* x){ ThreadBinTreeNodetype*q x→SetRightChild( p.GetRightChild() ); x→rightTag = p→rightTag; x→SetLeftChild( p ); x→leftTag=1; p→SetRightChild( x ); p→rightTag=0; if (x→rightTag==0){ q=x→GetRightChild( ); q= ThreadInOrderFirst (q); q→SetLeftChild( x ); } } 二叉树的应用 二叉树结构在实际问题中有着广泛的应用。二叉排序树、堆排序、哈夫曼树等是最典