数据结构课件(第6章)树和二叉树

《数据结构课件(第6章)树和二叉树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章树和二叉树信阳师范学院计算机与信息技术学院主要内容6.1树的基本概念6.2二叉树6.3遍历二叉树和线索二叉树6.4树和森林6.5赫夫曼树及其应用2021/6/182信阳师范学院计算机与信息技术学院掌握二叉树的结构特性;熟悉二叉树的各种存储结构的特点及适用范围；掌握各种遍历策略的递归算法，能灵活运用遍历算法实现二叉树的其他操作；理解二叉树线索化的实质,掌握二叉树的线索化过程。熟悉树的各种存储结构及其特点，掌握树和与二叉树的转换方法，掌握树的遍历方法；解哈夫曼树的特性，掌握构造哈夫曼树和哈夫曼编码的方法；学习要点2021/6/183信阳师范学院计算机与信

2、息技术学院6.1.1树的定义注1：过去许多书籍中都定义树为n≥1，曾经有“空树不是树”的说法，但现在树的定义已修改。注2：树的定义具有递归性，即“树中还有树”。由一个或多个(n≥0)结点组成的有限集合T，有且仅有一个结点称为根（root），当n>1时，其余的结点分为m(m≥0)个互不相交的有限集合T1,T2，…，Tm。每个集合本身又是棵树，被称作这个根的子树。6.1树的有关概念2021/6/184信阳师范学院计算机与信息技术学院6.1.2若干术语ABCGEIDHFJMLK根叶子森林有序树无序树——即根结点(没有前驱)——即终端结点(没有后继)——指m棵不相

3、交的树的集合(例如删除A后的子树个数)——结点各子树从左至右有序，不能互换（左为第一）——结点各子树可互换位置。2021/6/185信阳师范学院计算机与信息技术学院——即上层的那个结点(直接前驱)——即下层结点的子树的根(直接后继)——同一双亲下的同层结点（孩子之间互称兄弟）——即双亲位于同一层的结点（但并非同一双亲）ABCGEIDHFJMLK双亲孩子兄弟堂兄弟6.1.2若干术语2021/6/186信阳师范学院计算机与信息技术学院——即从根到该结点所经分支的所有结点——即该结点下层子树中的任一结点ABCGEIDHFJMLK祖先子孙结点结点的度——即树的数据

4、元素——结点挂接的子树数6.1.2若干术语2021/6/187信阳师范学院计算机与信息技术学院结点的层次终端结点分支结点树的度树的深度(或高度)ABCGEIDHFJFLK——从根到该结点的层数（根结点算第一层）——即度为0的结点，即叶子——即度不为0的结点（也称为内部结点）——所有结点度中的最大值（Max{各结点的度}）——指所有结点中最大的层数（Max{各结点的层次}）问：右上图中的结点数＝；树的度＝；树的深度＝13346.1.2若干术语2021/6/188信阳师范学院计算机与信息技术学院树的抽象数据类型定义（见教材P118-119）ADTTree{数据

5、对象D:数据关系R:基本操作P：}ADTTreeD是具有相同特性的数据元素的集合。若D为空集，则称为空树；//允许n=0若D中仅含一个数据元素，则R为空集；其他情况下的R存在二元关系：①root唯一//关于根的说明②Dj∩Dk=Φ//关于子树不相交的说明③……//关于数据元素的说明//15个，如求树深，求某结点的双亲2021/6/189信阳师范学院计算机与信息技术学院从逻辑结构看：1）树中只有根结点没有前驱；2）除根外，其余结点都有且仅一个前驱；3）一对多（1:n），树的结点可以有零个或多个后继；4）除根外的其他结点，都存在唯一条从根到该结点的路径；

6、5）树是一种分枝结构ABCGEIDHFJFLK6.1.3　树的逻辑结构2021/6/1810信阳师范学院计算机与信息技术学院教师学生其他人员2006级2007级2008级2009级……信阳师范学院数学学院计算机学院文学院……叶子根子树图形表示法2021/6/1811信阳师范学院计算机与信息技术学院嵌套集合表示法2021/6/1812信阳师范学院计算机与信息技术学院(A(B(E(K,L),F),C(G),D(H(M),I,J))约定：根作为由子树森林组成的表的名字写在表的左边广义表表示法2021/6/1813信阳师范学院计算机与信息技术学院凹入表示法又称目录

7、表示法2021/6/1814信阳师范学院计算机与信息技术学院ABCDEFGHIJKLMdata左孩子右兄弟左孩子－右兄弟表示法多叉树转为了二叉树2021/6/1815信阳师范学院计算机与信息技术学院6.1.5　树的运算要明确：1.普通树（即多叉树）若不转化为二叉树，则运算很难实现。2.二叉树的运算仍然是插入、删除、修改、查找、排序等，但这些操作必须建立在对树结点能够“遍历”的基础上！本章重点：二叉树的表示和实现遍历——指每个结点都被访问且仅访问一次，不遗漏不重复2021/6/1816信阳师范学院计算机与信息技术学院为何要重点研究每结点最多只有两个“叉”的树

8、？二叉树的结构最简单，规律性最强；可以证明，所有树都能转为唯一对应