数据结构课件VIP专享

第 15 页精品文档---下载后可任意编辑数据结构课件 第 6 章 树和二叉树.ppt 1、树型结构不同与线性表、栈、队列、串和广义表结构，是一类重要的非线性数据结构，其中以树和二叉树最为常用。树形结构反映了元素之间的层次关系和分支关系，它特别类似于自然界中的树。*第 6 章树和二叉树树型结构在现实世界中广泛存在，例如人类社会的族谱和各种社会组织机构都可用树来表示。在计算机领域中，DOS 和 Windows 操作系统中对磁盘文件的管理就采纳树型名目结构；在编译程序中，使用树来表示源程序的语法结构；在数据库系统中，树型结构也是信息的重要组织形式之一。6.1 树 6.2 二叉树 6.3 遍历二叉树 6.4二叉线索树 6.5 树和森林与二叉树 2、的转换 6.6 赫夫曼树及其应用 6.1 树 6.2 二叉树 6.3 遍历二叉树 6.4 二叉线索树 6.5 树和森林与二叉树的转换 6.6 赫夫曼树及其应用树(tree)结构是一种多分支多层次的数据结构，由一组结点组成。由于它呈现与自然界树类似的结构形式，所以称之为树。在很多算法中，常用树型结构描述问题的求解过程或表示求解的对策等。树的规律结构 6.1 树*树的存储结构树是由 n(n≥0)个结点组成的有限集。在任意一棵非空树 T 中：①有且仅有一个特定的称为根(root)结点；②当 n1 时，其余 n-1 个结点分成 m(m0)个互不相交的有限集 T1 3、，T2，…，Tm，其中每一个集合 Ti 本身又都是一棵树，并且称为根的子树。*6.1.1 树的规律结构 1.树的定义 AABCABCABDCEGFHIJK(a)(b)(c)(d)**2.树的基本操作InitTree(tree);操作结果：构造空树Tree。InsertChild(Tree,p,child);初始条件：树 Tree 存在，p 指向 Tree 中某个结点，1≤i≤p 所指结点的度+1，非空树 child 与 Tree 不相交。操作结果：插入 child 为 Tree 中 p 所指结点的子树。树结构中常常会用到一些基本术语。例如：结点结点的度叶结点 4、分支结点树的度双亲及孩子兄弟堂兄弟祖先子孙层次树的深度有序树无序树森林*3.树的基本概念*ABDCEFKLGHIJM 结点：树结点包含一个数据元素及若干指向其子树的分支 A 结点的度：结点所拥有的子树的数目叶子结点：度为 0 的结点，也称终端结点 FKLGIJM 分支结点：度不为 0 的结点，也称非终端结点ABDCEH 树的度：树内各结点的度的最大值双亲及孩子：一个结点的子树的根称为该结点的孩子，该结点称为孩子的双亲 HIJ 结点 D 的孩子 D 结点 H、I、J ...