数据结构 第7章-搜索树ppt课件.ppt

《数据结构 第7章-搜索树ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、引言集合可以采用树形结构表示，比如，用二叉搜索树、二叉平衡树、B-树等表示，通常称这些为搜索树。搜索树有较高的搜索效率，又能有效地插入和删除元素，因而更适合表示动态集。本课程讨论2种常见的用于表示动态集的树形数据结构：二叉搜索树和B-树。第7章搜索树DATASTRUCTURE数据结构内容提要1.二叉搜索树的定义；2.二叉搜索树的搜索、插入、删除运算及其分析；3.m叉搜索树的定义；4.B-树的定义；5.B-树的搜索、插入和删除运算。7.1二叉搜索树二叉搜索树也称二叉排序树，是一种最容易实现的搜索树。课堂提

2、要第7章搜索树7.1二叉搜索树7.1.1二叉搜索树的定义7.1.2二叉搜索树的搜索7.1.3二叉搜索树的插入7.1.4二叉搜索树的删除7.3B树7.1.1二叉搜索树的定义定义7.1设结点由关键字值表征，假定所有结点的关键字值各不相同，二叉搜索树或者是一棵空二叉树，或者是具有下列性质的二叉树：(1)若左子树不空，则左子树上所有结点的关键字值均小于根结点关键字值；(2)若右子树不空，则右子树上所有结点的关键字值均大于根结点关键字值；(3)左、右子树也分别是二叉搜索树。给出二叉搜索树的递归定义课堂提要第7章搜

3、索树7.1二叉搜索树7.1.1二叉搜索树的定义7.1.2二叉搜索树的搜索7.1.3二叉搜索树的插入7.1.4二叉搜索树的删除7.3B树性质7.1若以中序遍历一棵二叉搜索树，将得到一个以关键字值递增排列的有序序列。6354874569762335图7-1二叉搜索树程序7.1二叉搜索树类templateclassBSTree:publicDynamicSet{public:BSTree(){root=NULL;}ResultCodeSearch(T&x)const;ResultCode

4、Insert(T&x);ResultCodeRemove(T&x);…protected:BTNode*root;private:ResultCodeSearch(BTNode*p,T&x)const;…};7.1.2二叉搜索树的搜索第7章搜索树7.1二叉搜索树7.1.1二叉搜索树的定义7.1.2二叉搜索树的搜索7.1.3二叉搜索树的插入7.1.4二叉搜索树的删除7.3B树二叉搜索树搜索的递归算法二叉搜索树搜索的迭代算法课堂提要第7章搜索树7.1二叉搜索树7.1.1二叉搜索树的定义7.1.2

5、二叉搜索树的搜索7.1.3二叉搜索树的插入7.1.4二叉搜索树的删除7.3B树(1)若二叉树为空，则搜索失败。(2)否则，将x与根结点比较，若x小于该结点的值，则以同样的方法搜索左子树，而不必搜索右子树；若x大于该结点的值，则以同样的方法搜索右子树，而不必搜索左子树；若x等于该结点的值，则搜索成功终止。1.二叉搜索树搜索的递归算法在一棵二叉搜索树上，查找与x的关键字值相同的元素的递归算法可描述如下：程序7.2二叉搜索树搜索的递归算法//publictemplateResultCodeBS

6、Tree::Search(T&x)const{returnSearch(root,x);}//privatetemplateResultCodeBSTree::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->elemen

7、t;returnSuccess;}}2.二叉搜索树的迭代算法二叉搜索树的迭代算法使用while循环，从根结点开始搜索，将待查元素x与当前元素比较。若x等于该结点的值，则搜索成功终止；若x小于该结点的值，则继续搜索左子树；否则继续搜索右子树。只有搜索到空子树时，才失败终止。程序7.3二叉搜索树搜索的迭代算法templateResultCodeBSTree::Search(T&x)const{BTNode*p=root;while(p){if(xelement)p=p->

8、lChild;elseif(x>p->element)p=p->rChild;else{x=p->element;returnSuccess;}}returnNotPresent;}63548745697623357.1.3二叉搜索树的插入第7章搜索树7.1二叉搜索树7.1.1二叉搜索树的定义7.1.2二叉搜索树的搜索7.1.3二叉搜索树的插入7.1.4二叉搜索树的删除7.3B树二叉搜索树的插入步骤与单链表的插入步骤类似。(1)查找插入元素