欢迎来到三一办公! | 帮助中心 三一办公31ppt.com(应用文档模板下载平台)
三一办公
全部分类
  • 办公文档>
  • PPT模板>
  • 建筑/施工/环境>
  • 毕业设计>
  • 工程图纸>
  • 教育教学>
  • 素材源码>
  • 生活休闲>
  • 临时分类>
  • ImageVerifierCode 换一换
    首页 三一办公 > 资源分类 > PPT文档下载  

    数据结构与程序设计(王丽苹)25二分查找树.ppt

    • 资源ID:4980257       资源大小:349KB        全文页数:33页
    • 资源格式: PPT        下载积分:15金币
    快捷下载 游客一键下载
    会员登录下载
    三方登录下载: 微信开放平台登录 QQ登录  
    下载资源需要15金币
    邮箱/手机:
    温馨提示:
    用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)
    支付方式: 支付宝    微信支付   
    验证码:   换一换

    加入VIP免费专享
     
    账号:
    密码:
    验证码:   换一换
      忘记密码?
        
    友情提示
    2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,就可以正常下载了。
    3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
    4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰。
    5、试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。

    数据结构与程序设计(王丽苹)25二分查找树.ppt

    5/27/2023,数据结构与程序设计,1,数据结构与程序设计(25)Chapter10.2 Binary Search Tree,王丽苹,5/27/2023,数据结构与程序设计,2,Binary Search Trees P444,P445 DEFINITION:A binary search tree(二分查找树)is a binary tree that is either empty or in which the data entry of every node has a key and satisfies the conditions:1.The key of the left child of a node(if it exists)is less than the key of its parent node.2.The key of the right child of a node(if it exists)is greater than the key of its parent node.3.The left and right subtrees of the root are again binary search trees.,5/27/2023,数据结构与程序设计,3,Binary Search Trees,No two entries in a binary search tree may have equal keys.We may regard binary search trees as a specialization of binary trees.同时二分查找树主要用于构建ordered List。方便对关键码的查找。P446,5/27/2023,数据结构与程序设计,4,Binary Search Trees数据结构,template class Search_tree:public Binary_tree public:Error_code insert(const Record,5/27/2023,数据结构与程序设计,5,Implement of Binary Search Trees10.2.2 Tree search 查找操作,Error_code tree_search(Record 方法:将target与树根节点比较,如果相等则找到,程序结束。如果比根节点大,则进入右子树继续查找。如果比根节点小,则进入左子树继续查找。,5/27/2023,数据结构与程序设计,6,Implement of Binary Search Trees10.2.2 Tree search 查找操作 P447,Example:查找Kim的过程,5/27/2023,数据结构与程序设计,7,Implement of Binary Search TreesTree search 查找操作 实现,#include Binary_tree.cpptemplate class Search_tree:public Binary_tree public:Error_code insert(const Record,5/27/2023,数据结构与程序设计,8,Tree search 查找操作 实现,Binary_node*search_for_node(Binary_node*sub_root,const Record P448search_for_node是一个查找子函数。Sub_root:为空或者指向一棵子树。Postcondition:当target不在子树sub_root中存在时,返回NULL,当找到target时返回指向target的指针。,5/27/2023,数据结构与程序设计,9,Implement of Binary Search Trees查找操作 实现,template Error_code Search_tree:tree_search(Record,5/27/2023,数据结构与程序设计,10,Implement of Binary Search Trees查找操作 实现-递归,template Binary_node*Search_tree:search_for_node(Binary_node*sub_root,const Record,5/27/2023,数据结构与程序设计,11,Implement of Binary Search Trees查找操作 实现 非递归,/Nonrecursive version:template Binary_node*Search_tree:search_for_node(Binary_node*sub_root,const Record,5/27/2023,数据结构与程序设计,12,查找操作 实现分析 P449页,需要注意:同样的关键码,可能产生很多不同的查找树结构。图(a)(b)(c)(d)(e)为由七个字母构成的二分查找树的结构。对于查找操作:整棵树越浓密,则查找操作的效率越高。,最好的结构,最常见的结构,5/27/2023,数据结构与程序设计,13,查找操作 实现分析 P449页,最坏的结构,5/27/2023,数据结构与程序设计,14,10.2.3 Insert into a Binary Search Tree 二分查找树的插入操作,向二分查找树中插入节点的过程分析:如果二叉查找树为空,则新结点作为根结点。如果二叉查找树非空,则将新结点的关键码与根结点的关键码比较:若相等表示该结点已在二叉排序树中插入失败;若小于根结点的关键码,则将新结点插入到根结点的左子树中;否则,插入到右子树中。子树中的插入过程和树中的插入过程相同,如此进行下去,直到找到该结点,或者直到左或右子树为空二叉树,新结点插入成为叶子结点为止。,5/27/2023,数据结构与程序设计,15,P451 e,b,d,f,a,g,c逐一插入的过程,5/27/2023,数据结构与程序设计,16,10.2.3 Insert into a Binary Search Tree 插入操作分析,(1)不同的插入序列可能会产生相同的二分查找树的结构。如 e,f,g,b,a,d,c and e,b,d,c,a,f,g(2)如果插入的序列已经有序,那么生成的查找树的结构是最坏的。如a,b,c,d,e,f,g,将生成图10.8(e)的结构,5/27/2023,数据结构与程序设计,17,Implement of Binary Search TreesTree search 插入操作 实现,#include Binary_tree.cpptemplate class Search_tree:public Binary_tree public:Error_code insert(const Record,5/27/2023,数据结构与程序设计,18,Implement of Binary Search Trees插入操作 实现,template Error_code Search_tree:insert(const Record,5/27/2023,数据结构与程序设计,19,Implement of Binary Search Trees插入操作 实现,template Error_code Search_tree:search_and_insert(Binary_node*,5/27/2023,数据结构与程序设计,20,10.2.4 Tree sort,对于一棵二叉查找树,中序遍历的序列即为有序序列。因此,二叉查找树的插入过程也可以看成是排序的过程。即首先,将无序序列逐一插入二叉排序树。然后,对二叉排序树进行中序遍历。完成排序Tree sort比较适合于无序的序列,对于基本有序的序列效率较低,5/27/2023,数据结构与程序设计,21,10.2.5 Removal from a Binary Search Tree 删除操作讨论,(1)删除的节点是叶子结点:replace the link to the removed node by NULL.,5/27/2023,数据结构与程序设计,22,10.2.5 Removal from a Binary Search Tree 删除操作讨论,(2)删除的节点只有一棵非空子树:Adjust the link from the parent of the removed node to point to the root of the nonempty subtree.,5/27/2023,数据结构与程序设计,23,10.2.5 Removal from a Binary Search Tree 删除操作讨论,(3)删除的节点左右子树都非空:找到被删除节点的中序遍历的前驱(左子树中最右边的孩子),用前驱节点代替被删除点.,5/27/2023,数据结构与程序设计,24,Implement of Binary Search TreesTree search 删除操作 实现,#include Binary_tree.cpptemplate class Search_tree:public Binary_tree public:。Error_code remove(const Record,5/27/2023,数据结构与程序设计,25,Implement of Binary Search TreesTree search 删除操作 实现 P456,Error_code remove_root(Binary_node*,5/27/2023,数据结构与程序设计,26,Implement of Binary Search Trees删除操作 实现 P458,template Error_code Search_tree:remove(const Record,5/27/2023,数据结构与程序设计,27,Implement of Binary Search Trees删除操作 实现 P458,template Error_code Search_tree:search_and_destroy(Binary_node*,5/27/2023,数据结构与程序设计,28,删除操作 实现 P457,template Error_code Search_tree:remove_root(Binary_node*,5/27/2023,数据结构与程序设计,29,Implement of Binary Search Trees,void main()Search_tree mytree;mytree.insert(Record(2);mytree.insert(Record(4);mytree.insert(Record(1);mytree.insert(Record(3);,2,1,4,3,5/27/2023,数据结构与程序设计,30,Implement of Binary Search Trees,coutTree size is:mytree.size()endl;coutPreorder:endl;mytree.preorder(print);coutendl;coutinorder:endl;mytree.inorder(print);coutendl;coutPostorder:endl;mytree.postorder(print);coutendl;,Tree size is:4Preorder:2 1 4 3inorder:1 2 3 4Postorder:1 3 4 2,5/27/2023,数据结构与程序设计,31,Implement of Binary Search Trees,mytree.remove(Record(4);coutTree size is:mytree.size()endl;coutPreorder:endl;mytree.preorder(print);coutendl;coutinorder:endl;mytree.inorder(print);coutendl;coutPostorder:endl;mytree.postorder(print);coutendl;cin.get();,2,1,3,Tree size is:3Preorder:2 1 3inorder:1 2 3Postorder:1 3 2,5/27/2023,数据结构与程序设计,32,Implement of Binary Search Trees,目录Search_tree下例程,5/27/2023,数据结构与程序设计,33,HOMEWORK,BOOK P459E1(b)(e)(i)E2(b)(c)E3(c)(e)(f),

    注意事项

    本文(数据结构与程序设计(王丽苹)25二分查找树.ppt)为本站会员(小飞机)主动上传,三一办公仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知三一办公(点击联系客服),我们立即给予删除!

    温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。




    备案号:宁ICP备20000045号-2

    经营许可证:宁B2-20210002

    宁公网安备 64010402000987号

    三一办公
    收起
    展开