数据结构数据结构DataStructuresinC++DataStructuresinC++第第77章章动态集和搜索树动态集和搜索树7.1二叉搜索树7.2二叉平衡树7.3B-树7.17.1二叉搜索树二叉搜索树7.1.17.1.1二叉搜索树的定义二叉搜索树的定义定义定义7.17.1设结点由关键字值表征，假定所有结点的关键字值各不相同，二叉搜索树或者是一棵空二叉树，或者是具有下列性质的二叉树：（1）若左子树不空，则左子树上所有结点的关键字值均小于根结点的关键字值；（2）若右子树不空，则右子树上所有结点的关键字值均大于根结点的关键字值；（3）左、右子树也分别是二叉搜索树。性质性质7.17.1若以中序遍历一棵二叉搜索树，将得到一个以关键字值递增排列的有序序列。例：对图对图7.17.1所示所示二叉搜索树，按中序遍历后得到的序列为：23、35、45、54、63、69、76、87二叉搜索树也称二叉排序树二叉搜索树类二叉搜索树类template
templateclassBSTree:publicDynamicSetclassBSTree:publicDynamicSet{{public:public:BSTree(){root=NULL;}ResultCodeSearch(T&x)const;ResultCodeInsert(T&x);ResultCodeRemove(T&x);protected:BTNode*root;private:private:ResultCodeSearch(BTNode*p,T&x)const;};};7.1.2二叉搜索树的搜索•二叉搜索树搜索递归算法templateResultCodeBSTree::Search(T&x)const{returnSearch(root,x);}templateResultCodeBSTree::Search(BTNode*p,T&x)const{if(!p)returnNotPresent;elseif(xelement)returnSearch(p->lChild,x);elseif(x>p->element)returnSearch(p->rChild,x);else{x=p->element;returnSuccess;}}二叉搜索树搜索迭代算法templateResultCodeBSTree::Search(T&x)const{BTNode*p=root;while(p)if(xelement)p=p->lChild;elseif(x>p->element)p=p->rChild;else{x=p->element;returnSuccess;}returnNotPresent;}7.1.37.1.3二叉搜索树的插入二叉搜索树的插入二叉搜索树的插入步骤与单链表的插入步骤类似。(1)查找插入元素的位置；(2)生成新结点；(3)插入新结点(有可能修改root指针)在二叉搜索树上插入一个新元素，首先应搜索新元素的插入位置。搜索方法与Search函数的做法类似，但需要在自根结点相下搜索过程中，记录下当前结点的双亲结点，使得最终得到新结点的双亲结点q。如果二叉树中有重复元素，应返回Duplicate。搜索到达空子树，则表明树中不包含重复元素。此时，算法构造一个新结点p存放新元素x，连至结点q，成为q的孩子。至于p是q的左孩子还是右孩子，这取决于x与q关键字值的大小。如果原二叉搜索树是空树，则新结点p成为新二叉搜索树的根。在二叉搜索树中插入43的执行过程:282136332543q=∧pq43p=∧p二叉搜索树的插入二叉搜索树的插入templateResultCodeBSTree::Insert(T&x){BTNode*p=root,*q=NULL;while(p){q=p;if(xelement)p=p->lChild;elseif(x>p->element)p=p->rChild;else{x=p->element;returnDuplicate;}}查找插入位置p=newBTNode(x);p=newBTNode(x);if(!root!root)root=p;elseif(xelement)q->lChild=p;elseq->rChild=p;returnSuccess;}生成新结点插入新结点在二叉搜索树中插入43的执行过程:213633432528下图显示了从空树开始通过依次插入元素，构造一棵二叉搜索树的过程。(a)空树(b)插入28(c)插入21(d)插入25(e)插入36(f)插入33(g)插入437.1.4二叉搜索树的删除在二叉搜索树上删除一个结点也很容易。与插入运算类似，应先搜索被删除结点p，并记录p的双亲结点q。7.1.4二叉搜索树的删除若结点若结点*p*p有两棵非空子树有两棵非空子树需搜索*p的中序遍历次序下的直接后继（或直接前驱）结点，设为*s，将*s的值复制到*p中，称为替代替代，因为*s最多只有一棵非空子树，这样一来，问题转化为“被删除的结点最多只有一棵非空子树”的情形。如果不存在指定删除的元素，应返回NotPresent。删除结点p的操作由下列几步组成：若结点若结点*p*p只有一棵非空子树或只有一棵非空子树或*p*p是叶是叶子子以*p的惟一孩子（设为*c）或空子树（c＝NULL）取代*p，链接至*p的双亲结点*q。若...
