第8章搜索 试编写程序实现这三个删除方法,并用实例说明哪一个方法最易于达到平衡化。 【解答】 ①在被删结点有两个子女时用左子树T中具最大关键码的结点顶替的算法 template<class Type> BstNode<Type>*BST<Type>: leftReplace( BstNode<Type>*ptr )i BstNode<Type>*temp=ptr->leftChild; ∥进到p的左子树 while(temp-> rightchild=NULL)temp=temp-> rightchild;搜寻中序下最后一个结点 ∥用该结点数据代替根结点数据 ②在被删结点有两个子女时用右子树TR中具最小关键码的结点顶替的算法: template<class Type> BstNode<Type>* BST<Type>: rightReplace( BstNode<Type>*ptr )t BstNode<Type*temp=ptr->righ(Child; /进到p的右子树 while(temp-> leftchild i=NULL)temp=temp-> leftchild;W搜寻中序下最后一个结点 mp->data; ∥用该结点数据代替根结点数据 return temp; (1)用左子树TL上具有最大关键码的结点X顶替,再递归地删除X template <class Type> void BST<Type>: Remove( Type&x, BstNode<Type>*& ptr)( ∥私有函数:在以p为根的二叉搜索树中删除含x的结点。若删除成功则新根通过pt返回 BstNode<Type> *temp: if( ptr I=NULL if (x< ptr->data)Remove(x, ptr->leftChild ) ∥在左子树中执行删除 else if(x> ptr->data )Remove(x, ptr->rightChild ) ∥在右子树中执行删除 else if ptr->left Child I= nULL & ptr->right Child 1= NULL)( ∥p指示关键码为x的结点,它有两个子女 mp=leftReplace( ptr ) ∥在ptr的左子树中搜寻中序下最后一个结点顶替x Remove(ptr-> data, temp);在temp为根的子树中删除该结 else t ∥pr指示关键码为x的结点,它只有一个或零个子女 if( ptr->leftChild==nULL ptr= ptr->rightChild; ∥只有右子女 else if( ptr->rightChild ==NULL ptr=ptr->leftChild; ∥只有左子女 delete temp: (2)交替地用左子树上具有最大关键码的结点和右子树IR上具有最小关键码的结点顶替,再递 归地删除适当的结点。 template <class Type> void BST<Type>: Remove(Type& x, BstNode<Type>*& ptr, int& dir)t ∥私有函数:在以p为根的二叉搜索树中删除含x的结点。若删除成功则新根通过pt返回。在参数表中有一个 ∥引用变量dir,作为调整方向的标记。若dir=0,用左子树上具有最大关键码的结点顶替被删关键码;若dir=1 用右子树上具有最小关键码的结点顶替被删关键码结点,在调用它的程序中设定它的初始值为0。 BstNode<Type>*temp第 8 章 搜索 83 试编写程序实现这三个删除方法，并用实例说明哪一个方法最易于达到平衡化。 【解答】 ① 在被删结点有两个子女时用左子树 TL 中具最大关键码的结点顶替的算法： template<class Type> BstNode<Type> * BST<Type> :: leftReplace ( BstNode<Type> * ptr ) { BstNode<Type> * temp = ptr->leftChild; //进到 ptr 的左子树 while ( temp->rightChild != NULL ) temp = temp->rightChild; //搜寻中序下最后一个结点 ptr->data = temp->data; //用该结点数据代替根结点数据 return temp; } ② 在被删结点有两个子女时用右子树 TR中具最小关键码的结点顶替的算法： template<class Type> BstNode<Type> * BST<Type> :: rightReplace ( BstNode<Type> * ptr ) { BstNode<Type> * temp = ptr->rightChild; //进到 ptr 的右子树 while ( temp->leftChild != NULL ) temp = temp->leftChild; //搜寻中序下最后一个结点 ptr->data = temp->data; //用该结点数据代替根结点数据 return temp; } (1) 用左子树 TL 上具有最大关键码的结点 X 顶替，再递归地删除 X。 template <class Type> void BST<Type> :: Remove ( Type& x, BstNode<Type> *& ptr ) { //私有函数：在以 ptr 为根的二叉搜索树中删除含 x 的结点。若删除成功则新根通过 ptr 返回。 BstNode<Type> * temp; if ( ptr != NULL ) if ( x < ptr->data ) Remove ( x, ptr->leftChild ); //在左子树中执行删除 else if ( x > ptr->data ) Remove ( x, ptr->rightChild ); //在右子树中执行删除 else if ( ptr->leftChild != NULL && ptr->rightChild != NULL ) { // ptr 指示关键码为 x 的结点，它有两个子女 temp = leftReplace ( ptr ); //在 ptr 的左子树中搜寻中序下最后一个结点顶替 x Remove ( ptr->data, temp ); //在 temp 为根的子树中删除该结点 } else { // ptr 指示关键码为 x 的结点，它只有一个或零个子女 temp = ptr; if ( ptr->leftChild == NULL ) ptr = ptr->rightChild; //只有右子女 else if ( ptr->rightChild == NULL ) ptr = ptr->leftChild; //只有左子女 delete temp; } } (2) 交替地用左子树 TL 上具有最大关键码的结点和右子树 TR 上具有最小关键码的结点顶替，再递 归地删除适当的结点。 template <class Type> void BST<Type> :: Remove ( Type& x, BstNode<Type> *& ptr, int& dir ) { //私有函数：在以 ptr 为根的二叉搜索树中删除含 x 的结点。若删除成功则新根通过 ptr 返回。在参数表中有一个 //引用变量 dir, 作为调整方向的标记。若 dir = 0, 用左子树上具有最大关键码的结点顶替被删关键码; 若 dir = 1, //用右子树上具有最小关键码的结点顶替被删关键码结点, 在调用它的程序中设定它的初始值为 0。 BstNode<Type> * temp;