第7章集合与搜索 地删除适当的结点 template <class Type> void BST<Type>: Remove( Type& x, BstNode<Type> * pir, int& dir)i 私有函数:在以pm为根的二叉搜索树中删除含x的结点。若删除成功则新根通过p返回。在参数表中有一个 ∥引用变量dir,作为调整方向的标记。若dir=0,用左子树上具有最大关键码的结点顶替被删关键码;若dir=1 ∥用右子树上具有最小关键码的结点顶替被删关键码结点,在调用它的程序中设定它的初始值为0。 BsINode<type> *temp; if(ptr I=NULL) if(x<ptr->data)Remove(x, ptr->lefi Child, dir )i ∥在左子树中执行删除 else if( x> ptr->data ) Remove(x, ptr->righ/Child, dir ) ∥在右子树中执行删除 else if plr->lefi Child I= NULL & ptr->righI Child 1= NULL)( ∥pm指示关键码为x的结点,它有两个子女 (d=0){ emp= lefReplace(p);d=1;Mpm的左子树中搜寻中序下最后一个结点顶替x emp= rightReplace(p);dr=0;在p的右子树中搜寻中序下第一个结点顶替x Remove(ptr->data, temp, dir ) ∥在lemp为根的子树中删除该结点 ∥pm指示关键码为x的结点,它只有一个或零个子女 只有右子女 else if( ptr->righIChild== NULL ) ptr= ptr->lefiChild; ∥只有左子女 (3)用左子树上具有最大关键码的结点或者用右子树TR上具有最小关键码的结点顶替,再递归地 删除适当的结点。可随机选择其中一个方案 template <class Type> void BST<Type>:: Remove( Type& x, BstNode<Type>*& ptr)i ∥私有函数:在以pm为根的二叉搜索树中删除含x的结点。若删除成功则新根通过p返回。在程序中用到一个 ∥随机数发生器rand(),产生0~32767之间的随机数,将它除以16384,得到0-2之间的浮点数。若其大于1,用左 ∥子树上具有最大关键码的结点顶替被删关键码;若其小于或等于1,用右子树上具有最小关键码的结点顶替被删 ∥关键码结点,在调用它的程序中设定它的初始值为0 BstNode<type> temp; f(ptr I=NULL) if(x<ptr->data )Remove(x, ptr->lefi child); ∥在左子树中执行删除 else if(x> ptr->data ) Remove(x, ptr->rightChild ) ∥在右子树中执行删除 else if( ptr-> lefiChild I= NULL & pir->righI Child I= NULL)& ∥pm指示关键码为x的结点,它有两个子女 if((float)( rand(/16384)>1)i firePlace(pr);d=1;M在pm的左子树中搜寻中序下最后一个结点顶替 temp= rightreplace(p);dr=0;Mp的右子树中搜寻中序下第一个结点顶替x第 7 章 集合与搜索 64 地删除适当的结点。 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; if ( ptr != NULL ) if ( x < ptr->data ) Remove ( x, ptr->leftChild, dir ); //在左子树中执行删除 else if ( x > ptr->data ) Remove ( x, ptr->rightChild, dir ); //在右子树中执行删除 else if ( ptr->leftChild != NULL && ptr->rightChild != NULL ) { // ptr 指示关键码为 x 的结点，它有两个子女 if ( dir == 0 ) { temp = leftReplace ( ptr ); dir = 1; //在 ptr 的左子树中搜寻中序下最后一个结点顶替 x } else { temp = rightReplace ( ptr ); dir = 0; //在 ptr 的右子树中搜寻中序下第一个结点顶替 x } Remove ( ptr->data, temp, dir ); //在 temp 为根的子树中删除该结点 } else { // ptr 指示关键码为 x 的结点，它只有一个或零个子女 temp = ptr; if ( ptr->leftChild == NULL ) ptr = ptr->rightChild; //只有右子女 else if ( ptr->rightChild == NULL ) ptr = ptr->leftChild; //只有左子女 delete temp; } } (3) 用左子树 TL上具有最大关键码的结点或者用右子树 TR 上具有最小关键码的结点顶替，再递归地 删除适当的结点。可随机选择其中一个方案。 #include <stdlib.h> template <class Type> void BST<Type> :: Remove ( Type& x, BstNode<Type> *& ptr ) { //私有函数：在以 ptr 为根的二叉搜索树中删除含 x 的结点。若删除成功则新根通过 ptr 返回。在程序中用到一个 //随机数发生器 rand( ), 产生 032767 之间的随机数, 将它除以 16384, 得到 02 之间的浮点数。若其大于 1, 用左 //子树上具有最大关键码的结点顶替被删关键码; 若其小于或等于 1, 用右子树上具有最小关键码的结点顶替被删 //关键码结点, 在调用它的程序中设定它的初始值为 0。 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 的结点，它有两个子女 if ( (float) ( rand ( ) / 16384 ) > 1 ) { temp = leftReplace ( ptr ); dir = 1; //在 ptr 的左子树中搜寻中序下最后一个结点顶替 x } else { temp = rightReplace ( ptr ); dir = 0; //在 ptr 的右子树中搜寻中序下第一个结点顶替 x