数据结构 C语言版 教学课件 严蔚敏 李冬梅 吴伟民 第5章 树和二叉树.pdfVIP

数据结构 数据结构 李冬梅 李冬梅 北京林业大学信息学院 2015年6月11 日 逻辑结构 集合——数据元素间除“同属于一个集合”外，无其它关系 线性结构——一个对一个，如线性表、栈、队列 树形结构——一个对多个，如树 图形结构——多个对多个，如图 北京林业大学信息学院 2015年6月11 日 第5章　树和二叉树 5.1 树的定义和基本术语 5.2 二叉树 5.3 遍历二叉树与线索二叉树 5.4 树和森林 5.5 霍夫曼树及其应用 北京林业大学信息学院 2015年6月11 日 教学目标 1. 掌握二叉树的基本概念、性质和存储结构 1. 掌握二叉树的基本概念、性质和存储结构 2. 熟练掌握二叉树的前、中、后序遍历方法 2. 熟练掌握二叉树的前、中、后序遍历方法 3. 了解线索化二叉树的思想 3. 了解线索化二叉树的思想 4. 熟练掌握：霍夫曼树的实现方法、构造霍夫曼编 4. 熟练掌握：霍夫曼树的实现方法、构造霍夫曼编 码的方法 码的方法 5. 了解：森林与二叉树的转换，树的遍历方法 5. 了解：森林与二叉树的转换，树的遍历方法 北京林业大学信息学院 2015年6月11 日 5.1 树的定义和基本术语 树是n个结点的有限集 A A B C D E F G H I J K L M T1 T2 T3 北京林业大学信息学院 2015年6月11 日 树的抽象数据类型定义 ADT Tree{ 数据对象D: D是具有相同特性的数据元素的集合。 数据关系R: 若D为空集，则称为空树；//允许n=0 若D 中仅含一个数据元素，则R为空集； 其他情况下的R存在二元关系： ① root 唯一 //关于根的说明 ② D ∩D = Φ //关于子树不相交的说明 j k ③ …… //关于数据元素的说明 基本操作 P ： //至少有15个 }ADT Tree 北京林业大学信息学院 2015年6月11 日 树的其它