树和二叉树课件.ppt

《树和二叉树课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2021年8月3日东华理工大学信工学院主讲：王强数据结构2021年8月3日东华理工大学信工学院线性结构——一个对一个，如线性表、栈、队列树形结构——一个对多个，如树集合——数据元素间除“同属于一个集合”外，无其它关系图形结构——多个对多个，如图逻辑结构2021年8月3日东华理工大学信工学院第5章　树和二叉树5.1树的定义和基本术语5.2二叉树5.3遍历二叉树与线索二叉树5.4树和森林5.5霍夫曼树及其应用2021年8月3日东华理工大学信工学院1.掌握二叉树的基本概念、性质和存储结构2.熟练掌握二叉树的前、中、后序

2、遍历方法3.了解线索化二叉树的思想4.熟练掌握：霍夫曼树的实现方法、构造霍夫曼编码的方法5.了解：森林与二叉树的转换，树的遍历方法教学目标2021年8月3日东华理工大学信工学院5.1树的定义和基本术语树是n个结点的有限集T1T2T32021年8月3日东华理工大学信工学院ADTTree{数据对象D:数据关系R:基本操作P：}ADTTree若D为空集，则称为空树；//允许n=0若D中仅含一个数据元素，则R为空集；其他情况下的R存在二元关系：①root唯一//关于根的说明②Dj∩Dk=Φ//关于子树不相交的说明③……/

3、/关于数据元素的说明D是具有相同特性的数据元素的集合。//至少有15个树的抽象数据类型定义2021年8月3日东华理工大学信工学院凹入表示嵌套集合广义表树的其它表示方式2021年8月3日东华理工大学信工学院根叶子森林有序树无序树——即根结点(没有前驱)——即终端结点(没有后继)——指m棵不相交的树的集合(例如删除A后的子树个数)——结点各子树从左至右有序，不能互换（左为第一）——结点各子树可互换位置。基本术语2021年8月3日东华理工大学信工学院——即上层的那个结点(直接前驱)——即下层结点的子树的根(直接后继)—

4、—同一双亲下的同层结点（孩子之间互称兄弟）——即双亲位于同一层的结点（但并非同一双亲）——即从根到该结点所经分支的所有结点——即该结点下层子树中的任一结点双亲孩子兄弟堂兄弟祖先子孙基本术语2021年8月3日东华理工大学信工学院——即树的数据元素——结点挂接的子树数结点结点的度结点的层次终端结点分支结点树的度树的深度(或高度)——从根到该结点的层数（根结点算第一层）——即度为0的结点，即叶子——即度不为0的结点（也称为内部结点）——所有结点度中的最大值——指所有结点中最大的层数层次1234基本术语2021年8月3日

5、东华理工大学信工学院5.2二叉树普通树（多叉树）若不转化为二叉树，则运算很难实现为何要重点研究每结点最多只有两个“叉”的树？二叉树的结构最简单，规律性最强；可以证明，所有树都能转为唯一对应的二叉树，不失一般性。2021年8月3日东华理工大学信工学院二叉树基本特点：结点的度小于等于2有序树（子树有序，不能颠倒）二叉树的五种不同形态2021年8月3日东华理工大学信工学院具有3个结点的二叉树可能有几种不同形态？普通树呢？练习5种/2种2021年8月3日东华理工大学信工学院ADTBinaryTree{数据对象D:数据关系

6、R:基本操作P：}ADTBinaryTree若D=Φ，则R=Φ；若D≠Φ，则R={H}；存在二元关系：①root唯一//关于根的说明②Dj∩Dk=Φ//关于子树不相交的说明③……//关于数据元素的说明④……//关于左子树和右子树的说明D是具有相同特性的数据元素的集合。//至少有20个二叉树的抽象数据类型定义2021年8月3日东华理工大学信工学院性质1:在二叉树的第i层上至多有2i-1个结点二叉树的性质提问：第i层上至少有个结点？性质2:深度为k的二叉树至多有2k-1个结点提问：深度为k时至少有个结点？1k2021

7、年8月3日东华理工大学信工学院性质3:对于任何一棵二叉树，若2度的结点数有n2个，则叶子数n0必定为n2＋1（即n0=n2+1）2021年8月3日东华理工大学信工学院满二叉树：一棵深度为k且有2k-1个结点的二叉树。（特点：每层都“充满”了结点）特殊形态的二叉树完全二叉树：深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应只有最后一层叶子不满，且全部集中在左边2021年8月3日东华理工大学信工学院满二叉树是叶子一个也不少的树，而完全二叉树虽然前n-1层是满的，但

8、最底层却允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例。满二叉树和完全二叉树的区别2021年8月3日东华理工大学信工学院一棵完全二叉树有5000个结点，可以计算出其叶结点的个数是（）。练习25002021年8月3日东华理工大学信工学院性质4:具有n个结点的完全二叉树的深度必为[log2n]＋1k层nk-1层2021年8月3日东华理工大学信工学院性质5:对完全