数据结构(c语言版)课件 第五章 树 严蔚敏、吴伟民编 清华大学出版社

数据结构教材出版社：清华大学出版社作者：严蔚敏吴伟民ISBN ：978-7-302-02368-5目录第1章绪论1.1 什么是数据结构1.2 基本概念和术语1.3 抽象数据类型的表现与实现1.4 算法和算法分析第2章线性表2.1 线性表的类型定义2.2 线性表的顺序表示和实现2.3 线性表的链式表示和实现2.4 一元多项式的表示及相加第3章栈和队列3.1 栈3.2 栈的应有和举例3.3 栈与递归的实现3.4 队列3.5 离散事件模拟第4章串4.1 串类型的定义4.2 串的表示和实现4.3 串的模式匹配算法4.4 串操作应用举例第5章数组和广义表5.1 数组的定义5.2 数组的顺序表现和实现5.3 矩阵的压缩存储5.4 广义表的定义5.5 广义表的储存结构5.6 m元多项式的表示5.7 广义表的递归算法第6章树和二叉树6.1 树的定义和基本术语6.2 二叉树6.2.1 二叉树的定义6.2.2 二叉树的性质6.2.3 二叉树的存储结构6.3 遍历二叉树和线索二叉树6.3.1 遍历二叉树6.3.2 线索二叉树6.4 树和森林6.4.1 树的存储结构6.4.2 森林与二叉树的转换6.4.3 树和森林的遍历6.5 树与等价问题6.6 赫夫曼树及其应用6.6.1 最优二叉树（赫夫曼树）6.6.2 赫夫曼编码6.7 回溯法与树的遍历6.8 树的计数第7章图7.1 图的定义和术语7.2 图的存储结构7.2.1 数组表示法7.2.2 邻接表7.2.3 十字链表7.2.4 邻接多重表7.3 图的遍历7.3.1 深度优先搜索7.3.2 广度优先搜索7.4 图的连通性问题7.4.1 无向图的连通分量和生成树7.4.2 有向图的强连通分量7.4.3 最小生成树7.4.4 关节点和重连通分量7.5 有向无环图及其应用7.5.1 拓扑排序7.5.2 关键路径7.6 最短路径7.6.1 从某个源点到其余各顶点的最短路径7.6.2 每一对顶点之间的最短路径第8章动态存储管理8.1 概述8.2 可利用空间表及分配方法8.3 边界标识法8.3.1 可利用空间表的结构8.3.2 分配算法8.3.3 回收算法8.4 伙伴系统8.4.1 可利用空间表的结构8.4.2 分配算法8.4.3 回收算法8.5 无用单元收集8.6 存储紧缩第9章查找9.1 静态查找表9.1.1 顺序表的查找9.1.2 有序表的查找9.1.3 静态树表的查找9.1.4 索引顺序表的查找9.2 动态查找表9.2.1 二叉排序树和平衡二叉树9.2.2 B树和B+树9.2.3 键树9.3 哈希表9.3.1 什么是哈希表9.3.2 哈希函数的构造方法9.3.3 处理冲突的方法9.3.4 哈希表的查找及其分析第10章内部排序10.1 概述10.2 插入排序10.2.1 直接插入排序10.2.2 其他插入排序10.2.3 希尔排序10.3 快速排序10.4 选择排序10.4.1 简单选择排序10.4.2 树形选择排序10.4.3 堆排序10.5 归并排序10.6 基数排序10.6.1 多关键字的排序10.6.2 链式基数排序10.7 各种内部排序方法的比较讨论第11章外部排序11.1 外存信息的存取11.2 外部排序的方法11.3 多路平衡归并的实现11.4 置换一选择排序11.5 最佳归并树第12章文件12.1 有关文件的基本概念12.2 顺序文件12.3 索引文件12.4 ISAM文件和VSAM文件12.4.1 ISAM文件12.4.2 VSAM文件12.5 直接存取文件（散列文件）12.6 多关键字文件12.6.1 多重表文件12.6.2 倒排文件附录A 名词索引附录B 函数索引参考书目。

选择排序的基本思想
在未排序序列中找到最小（或最大）元素，存放到排序 序列的起始位置，然后，再从剩余未排序元素中继续寻 找最小（或最大）元素，然后放到已排序序列的末尾。 以此类推，直到所有元素均排序完毕。
交换排序和归并排序
交换排序的基本思想
通过不断地交换相邻的两个元素（如果它们的顺序错 误）来把最小的元素“浮”到数列的一端。具体实现 时，从第一个元素开始，比较相邻的两个元素，如果 前一个比后一个大，则交换它们的位置；每一对相邻 元素做同样的工作，从开始第一对到结尾的最后一对 ；这步做完后，最后的元素会是最大的数；针对所有 的元素重复以上的步骤，除了最后一个；持续每次对 越来越少的元素重复上面的步骤，直到没有任何一对 数字需要比较。
归并排序的基本思想
将两个或两个以上的有序表合并成一个新的有序表。具 体实现时，把长度为n的输入序列分成两个长度为n/2 的子序列；对这两个子序列分别采用归并排序；将两个 排序好的子序列合并成一个最终的排序序列。
查找的基本概念和方法
查找的定义
根据给定的某个值，在查找表中确定 一个其关键字等于给定值的数据元素 的过程或操作。
数组的定义和基本操作
数组的定义
数组（Array）是由相同类型的元素（ element）的集合所组成的数据结构 ，分配一块连续的内存来存储。利用 元素的索引（index）可以计算出该 元素对应的存储位置。
数组的基本操作
数组的基本操作包括数组的创建、数 组的初始化、数组的访问、数组的遍 历、数组的排序和数组的查找等。
顺序表的基本操作实现
包括插入、删除、查找等操作，时间复杂度为 O(n)。
顺序表的特点
支持随机访问，存储密度高，但插入和删除操作需要移动大量元素。

问题：必须先运行依据算法编制的程序；依赖软硬 件环境，容易掩盖算法本身的优劣；没有实际价值。 事前分析：求出该算法的一个时间界限函数。
与此相关的因素有： 依据算法选用何种策略； 问题的规模； 程序设计的语言； 编译程序所产生的机器代码的质量； 机器执行指令的速度； 撇开软硬件等有关部门因素，可以认为一个特定算
如何用数据形式描述问题?—即由问题抽象出一个 适当的数学模型; 问题所涉及的数据量大小及数据之间的关系; 如何在计算机中存储数据及体现数据之间的关系? 处理问题时需要对数据作何种运算? 所编写的程序的性能是否良好? 上面所列举的问题基本上由数据结构这门课程来回答。
1.1 数据结构及其概念
信息的表示和组织又直接关系到处理信息的程序的 效率。随着应用问题的不断复杂，导致信息量剧增与信 息范围的拓宽，使许多系统程序和应用程序的规模很大， 结构又相当复杂。因此，必须分析待处理问题中的对象 的特征及各对象之间存在的关系，这就是数据结构这门 课所要研究的问题。
计算机求解问题的一般步骤
编写解决实际问题的程序的一般过程：
编写解决实际问题的程序的一般过程如何用数据形式描述问题如何用数据形式描述问题即由问题抽象出一个适当的数学模型即由问题抽象出一个适当的数学模型问题所涉及的数据量大小及数据之间的关系问题所涉及的数据量大小及数据之间的关系如何在计算机中存储数据及体现数据之间的关系如何在计算机中存储数据及体现数据之间的关系处理问题时需要对数据作何种运算处理问题时需要对数据作何种运算所编写的程序的性能是否良好所编写的程序的性能是否良好算法与数据结构是计算机科学中的一门综合性专业基础课
O(㏒n) ：对数时间阶 O(n㏒n) ：线性对数时间阶
O (nk)： k≥2 ，k次方时间阶 例１ 两个n阶方阵的乘法

法“运行工作量”的大小，只依赖于问题的规模（通常 用n表示），或者说，它是问题规模的函数。
算法分析应用举例
算法中基本操作重复执行的次数是问题规模n的某 个函数，其时间量度记作 T(n)=O(f(n))，称作算法的渐 近时间复杂度(Asymptotic Time complexity)，简称时间复杂度。
K={k1, k2, …, k9} R={ <k1, k3>，<k1, k8>，<k2, k3>，<k2, k4>，<k2, k5>，<k3, k9>， <k5, k6>，<k8, k9>，<k9, k7>，<k4, k7>，<k4, k6> } 画出这逻辑结构的图示，并确定那些是起点，那些是终点
数据元素之间的关系可以是元素之间代表某种含义 的自然关系，也可以是为处理问题方便而人为定义的关 系，这种自然或人为定义的 “关系”称为数据元素之 间的逻辑关系，相应的结构称为逻辑结构。
《算法与数据结构》是计算机科学中的一门综合性专 业基础课。是介于数学、计算机硬件、计算机软件三者 之间的一门核心课程，不仅是一般程序设计的基础，而 且是设计和实现编译程序、操作系统、数据库系统及其 他系统程序和大型应用程序的重要基础。
1.1.1 数据结构的例子
例1：电话号码查询系统
设有一个电话号码薄，它记录了N个人的名字和其相 应的电话号码，假定按如下形式安排：(a1, b1)，(a2, b2)，…(an, bn)，其中ai, bi(i=1，2…n) 分别表示某人的名字 和电话号码。 本问题是一种典型的表格问题。如表1-1， 数据与数据成简单的一对一的线性关系。
图状结构

先序(根)遍历二叉树、 中序(根)遍历二叉树、 后序(根)遍历二叉树。
TElemType
data;
struct TriTNode *lchild, *rchild;
// 左右孩子指针
struct TriTNode *parent; //双亲指针
} TriTNode, *TriTree;
TriTree
parent lchild data 结点结构:
A
rchild
B
D
C
G
G
A (a()aB)一一棵棵C二二叉叉∧树树 D E ∧ ∧ ∧ F(b) 改∧造后∧(的b)完改全G造二叉后树的完全二叉树
A
B
C(c) 改∧造后完全D二叉树E顺序存∧储状态∧ ∧
F
∧∧ G
A B C ∧ D E ∧∧∧ F ∧∧G
(c) 改造后完全二叉树顺序存储状态
(c) 改造后完全二叉树顺序存储状态
任何一棵非空树的逻辑结构：
是一个二元组 Tree = （root，F）
其中：root 被称为根结点， F 被称为子树森林
叶子：K，L，F，G，M，I，J
结点A的孩子：B，C，D 结点B的孩子：E，F
结点I的双亲：D 结点L的双亲：E
结点A的度：3 结点B的度：2 结点M的度：0
A
B
C
结点A的层次：1 D 结点M的层次：4
例如，B,C,D为A的子树的根，则B,C,D是A的孩子， 而A则是B,C,D的双亲。
同一个双亲的孩子之间互称兄弟。将这些关系进一步 推广，结点的祖先是从根到该结点所经分支上的所有结点 。反之，以某结点为根的子树中的任一结点都称为该结点 的子孙。如B的子孙为E、F、K和L 。

在计算机科学中，数据的含义极为广泛，包括数值型、非 数值型、多媒体数据等。

数据元素(Data Element): 是数据的基本单位，在计算机程 序中通常作为一个整体进行考虑和处理。Eg. “图”中的圆 圈。 一个数据元素可由若干个数据项(Data Item)组成。数据 项是数据的不可分割的最小单位。 Eg. “书目”中的书名。

数据对象(Data Object) : 是性质相同的数据元素的集合。是 数据的一个子集。 Eg. C={ “ A’’, “ B”, · · · ,“Z”}
7
2019/3/20
1.2 基本概念和术语

数据结构(Data Structure)：是相互之间存在一种或多种特
定关系的数据元素的集合。数据元素相互之间的关系称为 结构。通常分为四类基本结构： 1、集合 数据元素除了同属于一种类型外，别无其它关系。 2、线性结构 数据元素之间存在一对一的关系。 3、树形结构 数据元素之间存在一对多的关系。 4、图状结构 数据元素之间存在多对多的关系。
数据结构
(Data Structure)
柳 青
Email: liuqing@
School of Software , Yunnan University
2019/3/20
1
数据结构教材及参考材料

《数据结构》 （C语言版）

严蔚敏 吴伟民
清华大学出版社

《数据结构题集》

严蔚敏 吴伟民
英文字符类型的数据对象是{A，B，C，D，E，F，…}

数据对象可以是有限的，也可以是无限的。 数据结构不同于数据类型，也不同于数据对象，它不仅要描 述数据类型的数据对象，而且要描述数据对象各元素之间的 相互关系。 2019/3/20

数组的抽象数据类型定义略，参见教材P90
6
5.2 数组的顺序存储表示和实现
问题： 计算机的存储结构是一维的，而数组一般是多维 的，怎样存放？ 解决办法：事先约定按某种次序将数组元素排成一列序列， 然后将这个线性序列存入存储器中。 例如：在二维数组中，我们既可以规定按行存储，也可以 规定按列存储。 注意： • 若规定好了次序，则数组中任意一个元素的存放地址便 有规律可寻，可形成地址计算公式； • 约定的次序不同，则计算元素地址的公式也有所不同； • C和PASCAL中一般采用行优先顺序；FORTRAN采用列优先。
行数 总列数，即 第2维长度 元素个数
ij
补充：计算二维数组元素地址的通式
设一般的二维数组是A[c1..d1, c2..d2]，这里c1,c2不一定是0。
单个元素 长度
二维数组列优先存储的通式为： LOC(aij)=LOC(ac1，c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L
8
二维数组(书上)
答： Volume=m*n*L=6*8*6=48*6=288
例2：已知二维数组Am,m按行存储的元素地址公式是：
Loc(aij)= Loc(a11)+[(i-1)*m+(j-1)]*K , 按列存储的公式是？ Loc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*K （尽管是方阵，但公式仍不同）
a[0][1] a[0][0] a[1][1] a[1][0] a a[2][0] a[2][1] a[n 1][0] a[n 1][1] a[0][m 1] a[1][m 1] a[2][m 1] a[n 1][m 1]

2021/3/12
Page 2
单关键字文件
❖ 文件中的记录只有一个唯一标识记录的主关键字。
多关键字文件
❖ 文件中的记录除了含有一个主关键字外，还含有若干个次关键字。
记录的属性
❖ 记录中所有非关键字的数据项。
记录的逻辑结构
❖ 记录在用户或应用程序员面前呈现的方式，是用户对数据的表示和 存取方式。
文件的检索方式
❖ 顺序存取：存取下一个逻辑记录。 ❖ 直接存取；存取第i个逻辑记录。 ❖ 按关键字存取：
简单查询、区域查询、函数查询、布尔查询
Data Structure
2021/3/12
Page 4
文件的修改
❖ 记录的插入、删除、修改。
文件的物理结构
❖ 文件在外存上的组织方式。 ➢ 顺序组织 ➢ 随机组织 ➢ 链组织
记录的物理结构
❖ 数据在物理存储器上存储的方式，是数据的物理表示和组织。
Data Structure
2021/3/12
Page 3
物理记录
❖ 计算机用一条I/0命令进行读写的基本数据单位（物理块）。 ❖ 物理记录和逻辑记录之间可能存在下列三种关系：
➢ 一个物理记录存放一个逻辑记录； ➢ 一个物理记录包含多个逻辑记录； ➢ 多个物理记录表示一个逻辑记录。
项。索引项指出该记录的物理地址。最后，索引表按关键字排序。 ❖ 只能存储在磁盘存储设备上。
Data Structure
2021/3/12
Page 8
物理记录号 职工号 姓名 职务 其他
101
29 张珊 程序员
103
05 李四 维修员
104
02 王红 程序员
105
38 刘淇 穿孔员

➢ 在非空的线性表，有且仅有一个开始结点a1， 它没有直接前趋，而仅有一个直接后继a2；
➢ 有且仅有一个终端结点an，它没有直接后继， 而仅有一个直接前趋a n-1；
➢ 其余的内部结点ai(2≦i≦n-1)都有且仅有一个 直接前趋a i-1和一个直接后继a i+1。 线性表是一种典型的线性结构。
数据的运算是定义在逻辑结构上的，而运算 的具体实现则是在存储结构上进行的。
总的时间由一个常数（即零次多项式）
来限界。而一个时间为O(n2)的算法则由 一个二次多项式来限界。
以下六种计算算法时间的多项式是最常 用的。其关系为：
O(1)<O(logn)<O(n)<O(nlogn)
<O(n2)<O(n3)
指数时间的关系为：
O(2n)<O(n!)<O(nn)
当n取得很大时，指数时间算法和多项 式时间算法在所需时间上非常悬殊。因
(a1，b1)(a2，b2)…(an，bn) 其中ai，bi(i=1，2…n) 分别表示某人的名字和对应的电
话号码要求设计一个算法，当给定任何一个人的名字 时，该算法能够打印出此人的电话号码，如果该电话 簿中根本就没有这个人，则该算法也能够报告没有这 个人的标志。
算法的设计，依赖于计算机如何存储人的 名字和对应的电话号码，或者说依赖于名字和 其电话号码的结构。
P3
通过以上几例可以直接地认为：数据结构 就是研究数据的逻辑结构和物理结构以及它们 之间相互关系，并对这种结构定义相应的运算， 而且确保经过这些运算后所得到的新结构仍然 是原来的结构类型。
1.2 基本概念和术语
数据(Data):是对信息的一种符号表示。在计 算机科学中是指所有能输入到计算机中并被 计算机程序处理的符号的总称。

哈希查找
哈希查找利用哈希函数将关 键字映射为存储位置进行查 找。
排序算法
排序算法用于对数据进行升序或降序排列。源自冒泡排序、快速排序和堆排序
冒泡排序通过相邻元素交换进行排序，快速排 序使用分治思想，堆排序利用堆的性质进行排 序。
高级数据结构
B-树和B+树
B-树和B+树是一种多路搜索树，用于处理大量数据。
算法性能的重要指标。
稳定排序算法会保持相同元素的相对位
置不变。
3
贪心算法、动态规划算法等
贪心算法和动态规划算法是解决优化问 题的常用方法。
图的遍历算法
图的遍历有广度优先搜索和深度优先搜索两种 常用算法。
图的存储结构
图的存储结构包括邻接矩阵和邻接表等多种方 式。
最短路径算法
最短路径算法用于求解图中两个顶点之间的最 短路径。
查找与排序
查找算法
查找算法用于在数据结构中 查找指定元素的位置。
顺序查找和二分查找
顺序查找是逐个比较查找， 二分查找利用有序性进行折 半查找。
树结构
1
树的定义
树是一种非线性结构，具有层次关系的
二叉树
2
数据结构。
二叉树是一种特殊的树结构，每个节点
最多有两个子节点。
3
遍历算法
二叉树的遍历有前序、中序和后序三种
线索二叉树
4
常用算法。
线索二叉树是一种利用空指针存储前驱 和后继结点的二叉树。
图结构
图的定义
图是由顶点和边组成的非线性结构，用于描述 事物之间的关系。
数据结构的基本概念
数据结构包括元素、关系和操作等基本概念。
线性结构
线性表的定义

谢谢！
《数据结构C语言版》严蔚 敏PPTc文件-精
26、机遇对于有准备的头脑有特别的 亲和力 。 27、自信是人格的核心。
28、目标的坚定是性格中最必要的力 量泉源 之一， 也中 ，徒劳 无功。- -查士 德斐尔 爵士。 29、困难就是机遇。--温斯顿．丘吉 尔。 30、我奋斗，所以我快乐。--格林斯 潘。
61、奢侈是舒适的，否则就不是奢侈 。——CocoCha nel 62、少而好学，如日出之阳；壮而好学 ，如日 中之光 ；志而 好学， 如炳烛 之光。 ——刘 向 63、三军可夺帅也，匹夫不可夺志也。 ——孔 丘 64、人生就是学校。在那里，与其说好 的教师 是幸福 ，不如 说好的 教师是 不幸。 ——海 贝尔 65、接受挑战，就可以享受胜利的喜悦 。——杰纳勒 尔·乔治·S·巴顿

第5章树和二叉树1．选择题（1）把一棵树转换为二叉树后，这棵二叉树的形态是（）。

A．唯一的Ｂ．有多种C．有多种，但根结点都没有左孩子Ｄ．有多种，但根结点都没有右孩子答案：A解释：因为二叉树有左孩子、右孩子之分，故一棵树转换为二叉树后，这棵二叉树的形态是唯一的。

（2）由3个结点可以构造出多少种不同的二叉树？（）A．2 B．3 C．4 D．5答案：D解释：五种情况如下：（3）一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）。

A．250 B． 500 C．254 D．501答案：D解释：设度为0结点（叶子结点）个数为A，度为1的结点个数为B，度为2的结点个数为C，有A=C+1，A+B+C=1001，可得2C+B=1000，由完全二叉树的性质可得B=0或1，又因为C 为整数，所以B=0，C=500，A=501，即有501个叶子结点。

（4）一个具有1025个结点的二叉树的高h为（）。

A．11 B．10 C．11至1025之间 D．10至1024之间答案：C解释：若每层仅有一个结点，则树高h为1025；且其最小树高为⎣log21025⎦ + 1=11，即h 在11至1025之间。

（5）深度为h的满m叉树的第k层有（）个结点。

(1=<k=<h)A．m k-1 B．m k-1 C．m h-1 D．m h-1答案：A解释：深度为h的满m叉树共有m h-1个结点，第k层有m k-1个结点。

（6）利用二叉链表存储树，则根结点的右指针是（）。

A．指向最左孩子 B．指向最右孩子 C．空 D．非空答案：C解释：利用二叉链表存储树时，右指针指向兄弟结点，因为根节点没有兄弟结点，故根节点的右指针指向空。

（7）对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（）遍历实现编号。

A．先序 B. 中序 C. 后序 D. 从根开始按层次遍历答案：C解释：根据题意可知按照先左孩子、再右孩子、最后双亲结点的顺序遍历二叉树，即后序遍历二叉树。