先序遍历算法StatusPreOrderTraverseBiTreeT-丽水学院.ppt

丽水学院工学院
第5章树和二叉树
线性结构——一个对一个,如线性表、栈、队列
树形结构——一个对多个,如树
集合——数据元素间除“同属于一个集合”外,无其它关系
图形结构——多个对多个,如图
逻辑结构
第5章树和二叉树
树和二叉树的定义
案例引入
树和二叉树的抽象数据类型定义
二叉树的性质和存储结构
遍历二叉树和线索二叉树
树和森林
哈夫曼树及其应用
案例分析与实现
1. 掌握二叉树的基本概念、性质和存储结构
2. 熟练掌握二叉树的前、中、后序遍历方法
3. 了解线索化二叉树的思想
4. 熟练掌握:哈夫曼树的实现方法、构造哈夫曼编码的方法
5. 了解:森林与二叉树的转换,树的遍历方法
教学目标
树和二叉树的定义
树(Tree)是n(n≥0)个结点的有限集,它或为空树(n = 0);或为非空树,对于非空树T:
(1)有且仅有一个称之为根的结点;
(2)除根结点以外的其余结点可分为m(m>0)个互不相交的有限集T1, T2, …, Tm, 其中每一个集合本身又是一棵树,并且称为根的子树(SubTree)。
树的定义
树是n个结点的有限集
T1
T2
T3
凹入表示
嵌套集合
广义表
树的其它表示方式
根
叶子
森林
有序树
无序树
——即根结点(没有前驱)
——即终端结点(没有后继)
——指m棵不相交的树的集合(例如删除A后的子树个数)
——结点各子树从左至右有序,不能互换(左为第一)
——结点各子树可互换位置。
基本术语
——即上层的那个结点(直接前驱)
——即下层结点的子树的根(直接后继)
——同一双亲下的同层结点(孩子之间互称兄弟)
——即双亲位于同一层的结点(但并非同一双亲)
——即从根到该结点所经分支的所有结点
——即该结点下层子树中的任一结点
双亲
孩子
兄弟
堂兄弟
祖先
子孙
基本术语
——即树的数据元素
——结点挂接的子树数
结点
结点的度
结点的层次
终端结点
分支结点
树的度
树的深度
(或高度)
——从根到该结点的层数(根结点算第一层)
——即度为0的结点,即叶子
——即度不为0的结点(也称为内部结点)
——所有结点度中的最大值
——指所有结点中最大的层数
层次
1
2
3
4
基本术语