数据结构与算法分析lecture6(二叉树).ppt_第1页
数据结构与算法分析lecture6(二叉树).ppt_第2页
数据结构与算法分析lecture6(二叉树).ppt_第3页
数据结构与算法分析lecture6(二叉树).ppt_第4页
数据结构与算法分析lecture6(二叉树).ppt_第5页
已阅读5页,还剩29页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

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 nodes 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.,

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论