第7章集合与搜索 7-18在二叉搜索树上删除一个有两个子女的结点时,可以采用以下三种方法 (1)用左子树T上具有最大关键码的结点X顶替,再递归地删除X (2)交替地用左子树T上具有最大关键码的结点和右子树TR上具有最小关键码的结点顶替,再递归 地删除适当的结点 (3)用左子树T上具有最大关键码的结点或者用右子树TR上具有最小关键码的结点顶替,再递归地 删除适当的结点。可随机选择其中一个方案。 试编写程序实现这三个删除方法,并用实例说明哪一个方法最易于达到平衡化 【解答】 ①在被删结点有两个子女时用左子树TL中具最大关键码的结点顶替的算法: emplate<class Type> BsiNode<Type>* BST<Type>: leftReplace( BstNode<Type>*ptr)( /进到pm的左子树 hile(lemp-> righIChild=NULL)lemp=temp-> righIChild:搜寻中序下最后一个结点 ptr->data= temp->data; 用该结点数据代替根结点数据 return temp: ②在被删结点有两个子女时用右子树TR中具最小关键码的结点顶替的算法 template<class Type> BstNode<Type>* BST<Type>:: rightReplace( BsINodesType>*ptr)t BsINode<type>*temp=ptr->righIChild ∥进到pr的右子树 while( temp->lefi Child I= NULL)temp= temp->lefichild ∥搜寻中序下最后一个结点 ptr->data= temp->data; ∥用该结点数据代替根结点数据 return temp: (1)用左子树T上具有最大关键码的结点X顶替,再递归地删除X template <class Type> void BST<Type>: Remore( Type& x, BstNode<Type>*& ptr)i 私有函数:在以p为根的二叉搜索树中删除含x的结点。若删除成功则新根通过p返回 if(ptr I=NULL) if(x < ptr->data)Remove(x, ptr->lefi child); ∥在左子树中执行删除 else if (x> ptr->data )Remove(x, ptr->right Child); ∥在右子树中执行删除 else if plr->lefiChild I= NULL & ptr->right Child I= NUll)t ∥pm指示关键码为x的结点,它有两个子女 lemp= firePlace(p);在p的左子树中搜寻中序下最后一个结点顶替x Remove(p->daa,lemp);M在lemp为根的子树中删除该结点 ∥pm指示关键码为x的结点,它只有一个或零个子女 if ptr->lefiChild== NULL) ptr= ptr->righr Child; ∥只有右子女 lse if( ptr->righI Child==NULL )ptr= ptr->lefiChild; ∥只有左子女 delete temp (2)交替地用左子树上具有最大关键码的结点和右子树TR上具有最小关键码的结点顶替,再递归第 7 章 集合与搜索 63 7-18 在二叉搜索树上删除一个有两个子女的结点时，可以采用以下三种方法： (1) 用左子树 TL上具有最大关键码的结点 X 顶替，再递归地删除 X。 (2) 交替地用左子树 TL上具有最大关键码的结点和右子树 TR 上具有最小关键码的结点顶替，再递归 地删除适当的结点。 (3) 用左子树 TL上具有最大关键码的结点或者用右子树 TR 上具有最小关键码的结点顶替，再递归地 删除适当的结点。可随机选择其中一个方案。 试编写程序实现这三个删除方法，并用实例说明哪一个方法最易于达到平衡化。 【解答】 ① 在被删结点有两个子女时用左子树 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 上具有最小关键码的结点顶替，再递归