《数据结构》课程PPT教学课件（2012）第6章 树和二叉树 Tree & Binary Tree（1/4）

数据结构课程的内容 线性结构（线性表、栈、队、串、数组） 逻辑结构 树结构 非线性结构 图结构 颜序结构 链式结构 数据结构 物理（存储)结构 索引结构 散列结构 插入运算 删除运算 数据运算 修改运算 查找运算 排序运算 7

1 数据结构课程的内容

目录 第章 绪论 第2章 线性表 第3章 栈和队列 第4章 串 第5章 数组和广义表 第6章 树和二叉树 第7章 图 第9章 查找 第10章排序

2 第 1 章 绪论 第 2 章 线性表 第 3 章 栈和队列 第 4 章 串 第 5 章 数组和广义表 第 6 章 树和二叉树 第 7 章 图 第 9 章 查找 第10 章 排序 目 录

第6章 树和二叉树(Tree&Binary Tree,) 特点：非线性结构，一个直接前驱，但可能有多个 直接后继。（一对多或1n) 二叉树的定义、 6.1 树的基本概念 性质和存储结构 6.2 二叉树 6.3遍历二叉树和线索二叉树 6.4 树和森林 二叉树的运算 6.5 赫夫曼树及其应用 3

3 第6章 树和二叉树（Tree & Binary Tree） 6.1 树的基本概念 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.5 赫夫曼树及其应用 特点：非线性结构，一个直接前驱，但可能有多个 直接后继。（一对多或1:n） 二叉树的定义、 性质和存储结构 二叉树的运算

6. 树的基本概念 6.1.1 树的定义 6.1.2 若干术语 6.1.3 逻辑结构 6.1.4 存储结构 6.1.5 树的运算

4 6.1 树的基本概念 6.1.1 树的定义 6.1.2 若干术语 6.1.3 逻辑结构 6.1.4 存储结构 6.1.5 树的运算

6.1.1 树的定义 由一个或多个(20)结点组成的有限集合T,有目仅有一 个结点称为根(root),当n>1时其余的结点分为m(m20) 个互不相交的有限集合T1,T2,.,Tm。每个集合本身又是 棵树，被称作这个根的子树。 注1：过去许多书籍中都定义树为≥1，曾经有“空树不是 树”的说法，但现在树的定义已修改。 注2：树的定义具有递归性，即“树中还有树” 5

5 6.1.1 树的定义 注1：过去许多书籍中都定义树为n≥1，曾经有“空树不是 树”的说法，但现在树的定义已修改。 注2：树的定义具有递归性，即“树中还有树”。 由一个或多个(n≥0)结点组成的有限集合T，有且仅有一 个结点称为根（root），当n>1时，其余的结点分为m(m≥0) 个互不相交的有限集合T1,T2，.，Tm。每个集合本身又是 棵树，被称作这个根的子树

6.1.2 若开术语 根 即根结点（没有前驱） 即终端结点设有后继) 森林 指m棵不相交的树的集 合（例如删除A后的子树个数） 有序树 结点各子树从左至右有序，不能互换（左为第一） 无序树 结点各子树可互换位置。 双亲 即上层的那个结点（直接前驱 孩子 即下层结点的子树的根直接后继) 兄弟 同一双亲下的同层结点（孩子之间互称兄弟） 堂兄弟 即双亲位于同一层的结点（但并非同一双亲） 祖先 即从根到该结点所经分支的所有结点 子孙 即该结点下层子树中的任一结点 6

6 6.1.2 若干术语 ——即上层的那个结点(直接前驱) ——即下层结点的子树的根(直接后继) ——同一双亲下的同层结点（孩子之间互称兄弟） ——即双亲位于同一层的结点（但并非同一双亲） ——即从根到该结点所经分支的所有结点 ——即该结点下层子树中的任一结点 A B C E G I D F H J K L F 根 叶子 森林 有序树 无序树 ——即根结点(没有前驱) ——即终端结点(没有后继) ——指m棵不相交的树的集 合(例如删除A后的子树个数) 双亲 孩子 兄弟 堂兄弟 祖先 子孙 ——结点各子树从左至右有序，不能互换（左为第一） ——结点各子树可互换位置

结点 即树的数据元素 结点的度 结点挂接的子树数 (有几个直接后继就是几度，亦称次数” 结点的层次一从根到该结点的层数（根结点算第一层） 终端结点 即度为0的结点，即叶子 分支结点 即度不为0的结点（也称为内部结点） 树的度 所有结点度中的最大值(Max{各结点的度}) 树的深度 指所有结点中最大的层数(Max{各结点的层次) 或高度) 问：右上图中的结点数=13树的度=3树的深度=

7 ——即树的数据元素 ——结点挂接的子树数 结点 结点的度 结点的层次 终端结点 分支结点 树的度 树的深度 (或高度) A B C E G I D F H J K L F ——从根到该结点的层数（根结点算第一层） ——即度为0的结点，即叶子 ——即度不为0的结点（也称为内部结点） ——所有结点度中的最大值（Max{各结点的度}） ——指所有结点中最大的层数（Max{各结点的层次}） 问：右上图中的结点数＝13；树的度＝ 3；树的深度＝ 4 （有几个直接后继就是几度，亦称“次数”）

自学：树的抽象数据类型定义 (见教材P118- 119) ADT Treef 数据对象D:D是具有相同特性的数据元素的集合。 数据关系R:若D为空集，则称为空树；/允许=0 若D中仅含一个数据元素，则R为空集； 其他情况下的R存在二元关系： ①root唯一 /关于根的说明 ②D∩Dk=Φ /关于子树不相交的说明 ③ 。 /关于数据元素的说明 基本操作P:/至少有15个，如求树深，求某结点的双亲 ADT Tree

8 自学：树的抽象数据类型定义 （见教材P118- 119） ADT Tree{ 数据对象D: 数据关系R: 基本操作 P： }ADT Tree D是具有相同特性的数据元素的集合。 若D为空集，则称为空树；//允许n=0 若D中仅含一个数据元素，则R为空集； 其他情况下的R存在二元关系： ① root 唯一 //关于根的说明 ② Dj∩Dk= Φ //关于子树不相交的说明 ③ . //关于数据元素的说明 //至少有15个，如求树深，求某结点的双亲

6.1.3 树的逻辑结构 特点： 一对多(1：n),有多个直接后继（如家谱 树、目录树等等)，但只有一个根结点，且 子树之间互不相交。 6.1.4 树的存储结构 讨论1：树是非线性结构，该怎样存储？ 仍然有顺序存储、链式存储等方式。 9

9 6.1.3 树的逻辑结构 一对多（1:n），有多个直接后继（如家谱 树、目录树等等），但只有一个根结点，且 子树之间互不相交。 6.1.4 树的存储结构 讨论1：树是非线性结构，该怎样存储？ 特点： ——仍然有顺序存储、链式存储等方式

讨论2：树的顺序存储方案应该怎样制定？ 可规定为：从上至下、从左至右将树的结点依次存入内存。 重大缺陷：复原困难 不能唯一复原就没有实用价值！ 讨论3：树的链式存储方案应该怎样制定？ 可用多重链表：一个前趋指针，个后继指针。 细节问题：树中结点的结构类型样式该如何设计？ 即应该设计成“等长”还是“不等长”？ 缺点：等长结构太浪费（每个结点的度不一定相同）： 不等长结构太复杂（要定义好多种结构类型）。 解决思路： 先研究最简单、最有规律的树，然 后设法把一般的树转化为简单树。 最简单的树 二叉树 10

10 最简单的树———二叉树 讨论3：树的链式存储方案应该怎样制定？ 复原困难 可用多重链表：一个前趋指针，n个后继指针。 细节问题： 树中结点的结构类型样式该如何设计？ 即应该设计成“等长”还是“不等长”？ 缺点： 等长结构太浪费（每个结点的度不一定相同）； 不等长结构太复杂（要定义好多种结构类型）。 先研究最简单、最有规律的树，然 后设法把一般的树转化为简单树。 可规定为： 从上至下、从左至右将树的结点依次存入内存。 重大缺陷： 解决思路： 不能唯一复原就没有实用价值！ 讨论2：树的顺序存储方案应该怎样制定？