数据结构--从概念到C++实现（算法与程序设计第3版普通高校本科计算机专业特色教材精选）

作者简介

内容简介

第5章树和二叉树本章概述前面讨论的数据结构都属于线性结构，线性结构主要描述具有单一的前驱和后继关系的数据。树结构是一种比线性结构更复杂的数据结构，适合描述具有层次关系的数据，如祖先—后代、上级—下属、整体—部分以及其他类似的关系。树结构在计算机领域有着广泛的应用，例如，在编译程序中用语法树来表示源程序的语法结构，在数据挖掘中用决策树来进行数据分类等。 本章的内容分为树和二叉树两部分。由实际问题引出树结构，介绍树的定义和基本术语，给出树的抽象数据类型定义，讨论树的存储结构；给出二叉树的定义和基本性质，讨论二叉树的存储结构，实现二叉链表存储的二叉树的遍历操作，最后讨论二叉树的经典应用——哈夫曼树。教学重点二叉树的性质；二叉树和树的存储表示；二叉树的遍历及算法实现；树与二叉树的转换关系；哈夫曼树教学难点二叉树的层序遍历算法；二叉树的建立算法；哈夫曼算法教学内容 和 教学目标知识点树的定义和基本术语树和二叉树的抽象数据类型定义树和二叉树的遍历树的存储结构二叉树的定义二叉树的基本性质二叉树的顺序存储结构二叉链表三叉链表二叉树遍历的递归算法二叉树遍历的非递归算法二叉树的层序遍历算法二叉树的建立算法树、森林和二叉树之间的转换哈夫曼树及哈夫曼编码教 学 要 求了解理解掌握熟练掌握√√√√√√√√√√√√√√√数据结构——从概念到C++实现（第3版）第5章树和二叉树5.1引言 树结构比较适合描述具有层次关系的数据，如祖先—后代、上级—下属、整体—部分以及其他类似的关系。很多实际问题抽象的数据模型是树结构，请看下面两个例子。 【例51】文件统计。Windows操作系统的文件目录结构如图51(a)所示，其中，“/”表示文件夹，括号内的数字表示文件的大小，单位是KB。假设文件夹本身的大小是1KB，请统计每个文件和文件夹的大小。 【想法——数据模型】文件目录结构具有层次特点，每个文件夹均可包含多个子文件夹和文件，将每个文件或文件夹抽象为一个结点，文件夹与文件之间的关系抽象为结点之间的边，从而将文件目录结构抽象为一个树结构，如图51(b)所示。可以对树进行某种遍历，即对树中所有结点进行没有重复没有遗漏的访问，在遍历过程中统计每个文件和文件夹的大小。那么，应该如何存储文件目录结构并在遍历过程中统计大小呢？ 【例52】二叉表示树。编译系统在处理算术表达式时，通常将表达式转换为一棵二叉表示树，通过二叉表示树可以判断算术表达式是否存在语法错误。请将给定的算术表达式转换为二叉表示树。 【想法——数据模型】二叉表示树是对应一个算术表达式的二叉树，并具有以下特点： ①叶子结点一定是操作数； ②分支结点一定是运算符。将一个算术表达式转化为二叉表示树基于如下规则： ① 根据运算符的优先顺序，将表达式结合成（左操作数 运算符 右操作数）的形式； ② 由外层括号开始，运算符作为二叉表示树的根结点，左操作数作为根结点的左子树，右操作数作为根结点的右子树； ③ 如果某子树对应的操作数为一个表达式，则重复第②步的转换，直到该子树对应的操作数不能再分解。 例如，将表达式(A+B)(C+DE)结合成((A+B)(C+(DE)))，则二叉表示树的根结点是运算符，左操作数即左子树是(A+B)，右操作数即右子树是(C+(DE))。对于左子树(A+B)，其根结点是运算符+，左子树是A，右子树是B。对于右子树(C+(DE))，其根结点是运算符+，左子树是C，右子树是(DE)。依此类推，构造过程如图52所示。 1. 合理规划教学内容。紧扣《高等学校计算机专业核心课程教学实施方案》和《计算机学科硕士研究生入学考试大纲》，涵盖教学方案及考研大纲要求的全部知识点。 2. 遵循认知规律，理清教学主线。根据学生的认知规律和课程的知识结构，按照从已知到未知的思维进程逐步推进教学内容，梳理和规划了各知识单元及其拓扑结构。 3. 提炼基础知识，适当扩展提高。抓牢核心概念，贯彻数据结构课程的基本教学要求，同时对某些知识点进行了适当的扩充和提高。 4. 兼顾概念层和实现层。将数据结构的实现过程分为抽象层、设计层和实现层，既强调数据结构的基本概念和原理方法，又注重数据结构的程序实现和实际运用。 5. 展现求解过程，培养计算思维。按照“问题？想法？算法？程序”的模式进行问题求解，采用“阐述基本思想→伪代码描述算法→C++语言实现算法”的模式进行算法设计。 6. 明确重点，化解难点。给出每一章的重点难点、各知识点的教学要求，以及有效的处理方法。针对数据结构内容抽象的特点，设计大量图解降低了理解问题的复杂性。