华中师范大学计算机科学系：《数据结构》第6章 二叉树和树

章二叉衍和树

第6章 二叉树和树

树型结构是一类重要的非线性结构。树型 结构是结点之间有分支并且具有层次关系 的结构它非常类似于自然界中的树。树结 构在客观世界中是大量存在的。例如家谱、 行政组织机构都可用树形象地表示。 树结构在计算机领域中也有着广泛的应用, 例如在编译程序中,用树结构来表示源程序 的语法结构;在数据库系统中,可用树结构 来组织信息;在分析算法的行为时可用树 结构来描述其执行过程等等

• 树型结构是一类重要的非线性结构。树型 结构是结点之间有分支,并且具有层次关系 的结构,它非常类似于自然界中的树。树结 构在客观世界中是大量存在的。例如家谱、 行政组织机构都可用树形象地表示。 • 树结构在计算机领域中也有着广泛的应用, 例如在编译程序中,用树结构来表示源程序 的语法结构；在数据库系统中,可用树结构 来组织信息；在分析算法的行为时,可用树 结构来描述其执行过程等等

ds. cs. ccnu.edu. cn equ ●●●(buaa ccnu ′whu)●·● ●●●(au ee d

华中师范大学 魏 开 平 王 敬 华 沈 显 君 … 系统 软件 应用 办公室 操作系统 数据库 数据结构 离散数学 … … 外 语 中 文 历 史 计 科 教 务 处 科 研 处 总 务 处 … … 附 … 中 ds.cs.ccnu.edu.cn au ee cn edu ccnu cs ds … buaa whu … … … … …

第六章二又树初树 课前导学 61二又树 62遍历二又树和线索二又树 63树和森林 64树的应用

课前导学 6.1 二叉树 6.2 遍历二叉树和线索二叉树 6.3 树和森林 6.4 树的应用

【学习目铜】 1.领会树和二叉树的类型定义,理解树和二叉树的结构差别。 2.熟记二叉树的主要特性,并掌握它们的证明 3.熟练掌握二叉树的各种遍历算法,并能灵活运用遍历算法实 现二叉树的其它操作。 4.理解二叉树的线索化过程以及在中序线索化树上找给定结点 的前驱和后继的方法。 5.熟练掌握二叉树和树的各种存储结构及其建立的算法。 6.学会编写实现树的各种操作的算法。 7.了解最优剡的特性,掌握建最优剡和赫夫曼编码的方法

【学习目标】 1. 领会树和二叉树的类型定义，理解树和二叉树的结构差别。 2. 熟记二叉树的主要特性，并掌握它们的证明 3. 熟练掌握二叉树的各种遍历算法，并能灵活运用遍历算法实 现二叉树的其它操作。 4. 理解二叉树的线索化过程以及在中序线索化树上找给定结点 的前驱和后继的方法。 5. 熟练掌握二叉树和树的各种存储结构及其建立的算法。 6. 学会编写实现树的各种操作的算法。 7. 了解最优树的特性，掌握建立最优树和赫夫曼编码的方法

【重点和赢】 难重 点点 最作树树线的 树 操编 优的和和索实叉叉叉的 作写叉 树实森森二现树树树类 的实树 和现林林叉的的的型 递现和 赫的的树遍存类定 归二树 夫遍存 历储型义 算叉的 曼历储 以表定 法树遍 编以表 示义 和历 码及示 其它操 及其它操作 树及 的其 各应 种用

【重点和难点 】 重点：二叉树和树的遍历及其应用 难点：编写实现二叉树和树的各种 操作的递归算法 知识点 – 树的类型定义 – 二叉树的类型定义 – 二叉树的存储表示 – 二叉树的遍历以及其它操作 的实现 – 线索二叉树 – 树和森林的存储表示 – 树和森林的遍历以及其它操 作的实现 – 最优树和赫夫曼编码

【学习有 本章是整个课程的第三个学习重点,也是 整个课程中的一大难点。在本章的学习过程中 主要应该学会如何根据二叉树和树的结构及其 操作的递归定义编写递归算法。 本章必须完成的算法设计题为: 6.1,6.3,6.4,6.5,6.6,6.7, 6.8,6.9,6.10,6.11,6.12,6.14 6.16,6.176.18,6.20,6.21,6.24, 6.25,6.26

【学习指南】 本章是整个课程的第三个学习重点，也是 整个课程中的一大难点。在本章的学习过程中 主要应该学会如何根据二叉树和树的结构及其 操作的递归定义编写递归算法。 本章必须完成的算法设计题为: 6.1, 6.3, 6.4, 6.5, 6.6, 6.7, 6.8, 6.9, 6.10, 6.11, 6.12, 6.14, 6.16, 6.17, 6.18, 6.20, 6.21, 6.24, 6.25, 6.26

、S御的定初基事 三、二的 物理构

6.1 二叉树 二、二叉树的基本性质 一、二叉树的定义和基本术语 三、二叉树的存储结构 逻辑结构 物理结构

、御的宮和基事语 1、二叉树的义 、二树的基本术语 3、二又树的应用拳例 4二又树的基事操作

一、二叉树的定义和基本术语 1、二叉树的定义 2、二叉树的基本术语 3、二叉树的应用举例 4、二叉树的基本操作

l、二御定3 二叉树T是n个结点的有限集合,其中n0,当n=0时, 为空树,否则,其中有一个结点为根结点,其余结 点划分为两个互不相交的子集TL、TR,并且TL、 TR分别构成叫作左、右子树的二叉树 A的TL 逼归寞或 B的TLN

1、 二叉树定义 • 二叉树T是n个结点的有限集合，其中n≥0,当n=0时， 为空树，否则，其中有一个结点为根结点，其余结 点划分为两个互不相交的子集TL、TR，并且TL、 TR分别构成叫作左、右子树的二叉树。 A C D E F B G H I K J M L A的TL B的TL 递归定义