欢迎来到人人文库网! | 帮助中心 人人文档renrendoc.com美如初恋!
人人文库网
全部分类
  • 图纸下载>
  • 教育资料>
  • 专业文献>
  • 应用文书>
  • 行业资料>
  • 生活休闲>
  • 办公材料>
  • 毕业设计>
  • ImageVerifierCode 换一换
    首页 人人文库网 > 资源分类 > PPT文档下载  

    数据结构与算法分析lecture6(二叉树).ppt

    • 资源ID:17763106       资源大小:265.50KB        全文页数:34页
    • 资源格式: PPT        下载积分:9.9积分
    扫码快捷下载 游客一键下载
    会员登录下载
    微信登录下载
    三方登录下载: 微信开放平台登录 支付宝登录   QQ登录   微博登录  
    二维码
    微信扫一扫登录

    手机扫码下载

    请使用微信 或支付宝 扫码支付

    • 扫码支付后即可登录下载文档,同时代表您同意《人人文库网用户协议》

    • 扫码过程中请勿刷新、关闭本页面,否则会导致文档资源下载失败

    • 支付成功后,可再次使用当前微信或支付宝扫码免费下载本资源,无需再次付费

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

    数据结构与算法分析lecture6(二叉树).ppt

    Binary Trees (二叉树),Tao Liang College of software SiChuan University,1数据的逻辑结构,2、数据的存储结构,3、数据的运算:检索、排序、插入、删除、修改等。,A线性结构,B非线性结构,A 顺序存储,B 链式存储,线性表,栈,队,树形结构,图形结构,数据结构的三个主要问题,1数据的逻辑结构,2、数据的存储结构,3、数据的运算:检索、排序、插入、删除、修改等。,A线性结构,B非线性结构,A 顺序存储,B 链式存储,线性表,栈,队,树形结构,图形结构,数据结构的三个主要问题,线性结构,A , B , C , ······· ,X ,Y , Z,学 生 成 绩 表,线性表结点间是以线性关系联结,1数据的逻辑结构,2、数据的存储结构,3、数据的运算:检索、排序、插入、删除、修改等。,A线性结构,B非线性结构,A 顺序存储,B 链式存储,线性表,栈,队列,树形结构,图形结构,数据结构的三个主要问题,树形结构,全校学生档案管理的组织方式,树形结构 结点间具有分层次的连接关系,Binary Tree,Definitions and Properties Binary Tree Traversals Binary Tree Node Implementions Binary Search Trees Heaps and Priority Queues Huffman Coding Trees,Definitions and Properties,二叉树的定义:由结点(node)的有限集合组成,这个集合或者为空(empty),或由一个根结点(root)和两棵分别称为根的左子树(left subtree)和右子树(right subtree)的互不相交的二叉数组成。,介绍几个概念: 结点(Node):树中的元素,包含数据项及若干指向其子树的分支。 结点的度(Degree):结点拥有的子树数。 结点的层次:从根结点开始算起,根为第0层。 叶子(Leaf):度为零的结点,也称端结点。 孩子(Child):结点子树的根称为该结点的孩子结点。 兄弟(Sibling):同一双亲的孩子。 双亲(Parent):孩子结点的上层结点,称为这些结点的双亲。 结点的深度(Depth): 从根结点到该结点的路径的长度。 树的高度(Height):等于最深结点的深度加1。,Two different trees,满二叉树(full binary tree ) 的每一个结点或者是一个分支结点,并恰有两个非空子结点;或者是叶结点. 完全二叉树(complete binary tree)有严格的形状要求:从根结点起每一层从左到右填充.一棵高度为d的完全二叉树除了d-1层以外,每一层都是满的.底层叶结点集中在左边的若干位置上.,The Full Binary Tree Theorem (满二叉树定理),Theorem 5.1 Full Binary Tree Theorem:The number of leaves in a non-empty full binary tree is one more than the number of internal nodes. Theorem 5.2 The number of empty subtrees in a non-empty binary tree is one more than of nodes in the tree.,A Binary Tree Node ADT,Clearly there are activities that relate to nodes(e.g.,reach a child or get a value),and activities that relate to trees(e.g.,tree initialization). So nodes and trees should be separate classes in a C+ implementation.,/binary tree node abstract class template class BinNode public : /return the nodes element virtual Elem,/set the nodes left child virtual void setLeft(BinNode*)=0; /return the nodes right child virtual BinNode* right() const =0; /set the nodes right child virtual void setRight(BinNode*)=0; /return true if the node is a leaf virtual bool isleaf() =0; ;,Binary Tree Traversals (二叉树的遍历),查找某个结点,或对二叉树中全部结点进行某种处理,就需要 遍历。 (1)遍历定义 遍历是指按某条搜索路线寻访树中每个结点,且每个结点只被访问一次。 按先左后右的原则,一般使用三种遍历: preorder traversal 前序遍历 inorder traversal 中序遍历 posterorder traversal 后序遍历,前序遍历(D L R): 访问根结点,按前序遍历左子树,按前序遍历右子树。 A B D C E G F H I 中序遍历(L D R): 按中序遍历左子树,访问根结点,按中序遍历右子树。 B D A G E C H F I 后序遍历(L R D): 按后序遍历左子树,按后序遍历右子树,访问根结点。 二叉树为空时,执行空操作,即空二叉树已遍历完。 D B G E H I F C A,(2)遍历算法,先序遍历:D L R 中序遍历:L D R 后序遍历:L R D,A,D,B,C,T1,T2,T3,D L R,以先序遍历D L R为例演示遍历过程,ABDC,BDAC,DBCA,template void PreOder (BinNode* subroot) if(subroot =NULL) return; visit(subroot); PreOrder (subroot-left(); PreOrder (subroot-right(); /*前序遍历*/,返回,返回,返回,返回,A,C,B,D,返回,template void PreOder (BinNode* subroot) if(subroot =NULL) return; visit(subroot); PreOrder (subroot-left(); PreOrder (subroot-right(); /*前序遍历*/,template void PreOder (BinNode* subroot) if(subroot =NULL) return; visit(subroot); PreOrder (subroot-left(); PreOrder (subroot-right(); /*前序遍历*/,?,中序遍历二叉树的递归算法: template void InOder (BinNode* subroot) if(subroot =NULL) return; InOrder (subroot-left(); visit(subroot); InOrder (subroot-right(); /*中序遍历*/,后序遍历二叉树的递归算法: template void PostOder (BinNode* subroot) if(subroot =NULL) return; PostOrder (subroot-left(); PostOrder (subroot-right(); visit(subroot); /*后序遍历*/,Example5.4 A function that counts the number of nodes in a binary tree. template int count(BinNode* subroot) if(subroot = NULL) return 0; return 1+count(subroot-left() +count(subroot-right(); ,Binary Tree Node Implemention (二叉树的实现),A typical pointer-based binary tree implemention, Each node stores two child pointers and a value.,A binary tree node class implemention(二叉树结点类的实现),/ Binary tree node class template class BinNodePtr : public BinNode private: Elem it; / The node's value BinNodePtr* lc; / Pointer to left child BinNodePtr* rc; / Pointer to right child,public: / Two constructors - with and without initial values BinNodePtr() lc = rc = NULL; BinNodePtr(Elem e, BinNodePtr* l =NULL, BinNodePtr* r =NULL) it = e; lc = l; rc = r; BinNodePtr() / Destructor Elem ,inline BinNode* left() const return lc; void setLeft(BinNode* b) lc = (BinNodePtr*)b; inline BinNode* right() const return rc; void setRight(BinNode* b) rc = (BinNodePtr*)b; bool isLeaf() return (lc = NULL) ,-,*,*,+,*,c,a,x,2,x,4,An expression tree for 4x(2x+a)-c Leaves and internal nodes use different definition,How to differentiate leaf from internal nodes,One way to differentiate leaf from internal nodes is to use the C+ union construct,as shown in Figure 5.9(P 152) C+ provides a better approach to differentiating leaf from internal nodes through the use of class inheritance,as shown in Figure 5.10(P 153) Another way to differentiate leaf from internal nodes is to use a virtual base class and separate node classes for the two types,as shown in Figure 5.11(P 155),Comparison of different implementations,P95-99,Space Requirements,Discuss,Array Implementation for Complete Binary Trees,Properties of complete Binary Trees: Complete binary trees have all levels except the bottom filled out completely,and the bottom level has all of its nodes filled in from left to right.,A complete binary tree and its array implementation,The formulae for calculating the array indices of the various relatives of a node are as follows:,n is the total number of nodes in the tree. r is the index of the node in question,which must fall in the range 0 to n-1.,

    注意事项

    本文(数据结构与算法分析lecture6(二叉树).ppt)为本站会员(jun****875)主动上传,人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知人人文库网(点击联系客服),我们立即给予删除!

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




    关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们

    网站客服QQ:2881952447     

    copyright@ 2020-2024  renrendoc.com 人人文库版权所有   联系电话:400-852-1180

    备案号:蜀ICP备2022000484号-2       经营许可证: 川B2-20220663       公网安备川公网安备: 51019002004831号

    本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知人人文库网,我们立即给予删除!