《数据结构A》第07章

《《数据结构A》第07章》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构DataStructuresinC++南京邮电大学计算机学院陈慧南2006年9月第7章动态集和搜索树南京邮电大学计算机学院陈慧南2006年9月7.1  二叉搜索树7.2  二叉平衡树7.3B-树南京邮电大学计算机学院陈慧南2006年9月7.1二叉搜索树南京邮电大学计算机学院陈慧南2006年9月7.1.1二叉搜索树的定义定义7.1设结点由关键字值表征，假定所有结点的关键字值各不相同，二叉搜索树或者是一棵空二叉树，或者是具有下列性质的二叉树：（1）若左子树不空，则左子树上所有结点的关键字值均小于根结点的关键字值；（2）若右子树不空，则右子树上所有结点的关键字值

2、均大于根结点的关键字值；（3）左、右子树也分别是二叉搜索树。南京邮电大学计算机学院陈慧南2006年9月性质7.1若以中序遍历一棵二叉搜索树，将得到一个以关键字值递增排列的有序序列。南京邮电大学计算机学院陈慧南2006年9月二叉搜索树类templateclassBSTree:publicDynamicSet{public:BSTree(){root=NULL;}ResultCodeSearch(T&x)const;ResultCodeInsert(T&x);ResultCodeRemove(T&x);protected:BTNode*r

3、oot;private:ResultCodeSearch(BTNode*p,T&x)const;};南京邮电大学计算机学院陈慧南2006年9月7.1.2二叉搜索树的搜索二叉搜索树搜索递归算法templateResultCodeBSTree::Search(T&x)const{returnSearch(root,x);}南京邮电大学计算机学院陈慧南2006年9月templateResultCodeBSTree::Search(BTNode*p,T&x)const{if(!p)returnNotPresent;

4、elseif(xelement)returnSearch(p->lChild,x);elseif(x>p->element)returnSearch(p->rChild,x);else{x=p->element;returnSuccess;}}南京邮电大学计算机学院陈慧南2006年9月二叉搜索树搜索迭代算法templateResultCodeBSTree::Search(T&x)const{BTNode*p=root;while(p)if(xelement)p=p->lChild;elseif(x>p->element)

5、p=p->rChild;else{x=p->element;returnSuccess;}returnNotPresent;}南京邮电大学计算机学院陈慧南2006年9月7.1.3二叉搜索树的插入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;}}南京邮电大

6、学计算机学院陈慧南2006年9月p=newBTNode(x);if(!root)root=p;elseif(xelement)q->lChild=p;elseq->rChild=p;returnSuccess;}南京邮电大学计算机学院陈慧南2006年9月南京邮电大学计算机学院陈慧南2006年9月7.1.4二叉搜索树的删除若结点*p有两棵非空子树需搜索*p的中序遍历次序下的直接后继（或直接前驱）结点，设为*s，将*s的值复制到*p中，称为替代，因为*s最多只有一棵非空子树，这样一来，问题转化为“被删除的结点最多只有一棵非空子树”的情形。南京邮电大学计算

7、机学院陈慧南2006年9月若结点*p只有一棵非空子树或*p是叶子以*p的惟一孩子（设为*c）或空子树（c＝NULL）取代*p，链接至*p的双亲结点*q。若被删除的结点*p是根结点，则删除后，结点*c成为新的根；若*p是其双亲*q的左孩子，则*c也应成为*q的左孩子，否则*c成为*q的右孩子。最后释放结点*p所占用的空间。南京邮电大学计算机学院陈慧南2006年9月删除28南京邮电大学计算机学院陈慧南2006年9月南京邮电大学计算机学院陈慧南2006年9月templateResultCodeBSTree::Remove(T&x){BTNode

8、>*c,*