第7章-树和二叉树第1讲-树的概念
- 格式：pdf
- 大小：4.40 MB
- 文档页数：53
下载文档原格式
合集下载
第7章-树和二叉树第2讲-二叉树的概念
（root），其余结点可分为m （m≥0）个互不相交的有限子集 T1、T2、…、Tm，而每个子集本身又是一棵树，称为根结点 root的子树。 树中所有结点构成一种层次关系！
第一层
树的特 点？
第二层 第三层 第四层
复习：二、树的基本术语
1.结点A、D的度？树的度？ 2;3;3; 2.根结点？分支结点？叶子结点？ A;BCDE;GHIJF;
在二叉链中，空指针的个数？
b A
B∧
C
∧D
∧E∧
∧F∧
∧G∧
n个结点 2n个指针域 分支数为n-1 非空指针域有n-1个 空指针域个数 = 2n-(n-1) = n+1
n=7 空指针域个数=8
39/10
40/10
二叉树
当n=3，结果为ห้องสมุดไป่ตู้。
第n个Catalan数
41/23
有n个结点并且高度为n的不同形态的二叉树个数是多少？ 该二叉树：有n层，每层一个结点，该结点可以
43/23
结点个数为n，树形可以唯一确定 叶子结点个数为n0，树形不能唯一确定 n为奇数时，n1=0； n为偶数时，n1=1。 n0=n2+1 高度h= log2(n+1)，是n个结点高度最小的二叉树
44/23
含有60个叶子结点的二叉树的最小高度是多少？
在该二叉树中，n0=60，n2=n0-1=59，n=n0+n1+n2=119+n1。 当n1=0且为完全二叉树时高度最小。 此时高度h=log2(n+1)= log2120=7。
作为双亲结点的左孩子，也可以作为右孩子 这样的二叉树的个数=1×2×…×2=2n-1。
例如，当n=3时有22=4个这样的二叉树。
第一层
树的特 点？
第二层 第三层 第四层
复习：二、树的基本术语
1.结点A、D的度？树的度？ 2;3;3; 2.根结点？分支结点？叶子结点？ A;BCDE;GHIJF;
在二叉链中，空指针的个数？
b A
B∧
C
∧D
∧E∧
∧F∧
∧G∧
n个结点 2n个指针域 分支数为n-1 非空指针域有n-1个 空指针域个数 = 2n-(n-1) = n+1
n=7 空指针域个数=8
39/10
40/10
二叉树
当n=3，结果为ห้องสมุดไป่ตู้。
第n个Catalan数
41/23
有n个结点并且高度为n的不同形态的二叉树个数是多少？ 该二叉树：有n层，每层一个结点，该结点可以
43/23
结点个数为n，树形可以唯一确定 叶子结点个数为n0，树形不能唯一确定 n为奇数时，n1=0； n为偶数时，n1=1。 n0=n2+1 高度h= log2(n+1)，是n个结点高度最小的二叉树
44/23
含有60个叶子结点的二叉树的最小高度是多少？
在该二叉树中，n0=60，n2=n0-1=59，n=n0+n1+n2=119+n1。 当n1=0且为完全二叉树时高度最小。 此时高度h=log2(n+1)= log2120=7。
作为双亲结点的左孩子，也可以作为右孩子 这样的二叉树的个数=1×2×…×2=2n-1。
例如，当n=3时有22=4个这样的二叉树。
数据结构-教学大纲
《数据结构》教学大纲一、基本信息二、教学目标及任务本课程作为计算机专业重要的主干课程，它要求学生学会分析和研究需解决的问题中的数据的特性，为其选择合适的数据结构来描述，在此数据结构的基础上写出相应的算法，并初步掌握算法的时间复杂度和空间复杂度的分析技术。
三、学时分配教学课时分配四、教学内容及教学要求第一章数据结构绪论(共4学时)基本内容：1)数据结构的概念2)数据的逻辑结构和存储结构3)算法教学要求：熟悉数据结构中各名词、术语的含义，掌握其基本概念；理解数据类型和抽象数据类型的含义；理解算法五个要素的确切含义，注意算法与程序的区别；掌握计算语句频度和估算算法时间复杂度的方法。
第二章线性表(共6学时)基本内容：1)线性表的概念及运算2)线性表的顺序存储结构—顺序表3)线性表的链式存储结构—链表教学要求：了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构；熟练掌握这两类存储结构的描述方法，以及线性表的各种基本操作的实现；能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合；掌握用线性表来表示一元多项式的方法及相应操作的实现。
第三章栈和队列(共4学时)基本内容：1)栈2)队列教学要求：掌握栈和队列类型的特点，并能在相应的应用问题中正确选用它们；熟练掌握栈类型的两种实现方法，特别应注意栈满和栈空的条件以及它们的描述方法；熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的描述方法；理解递归算法执行过程中栈的状态变化过程。
第四章数组和矩阵(共4学时)基本内容：1)数组2)特殊矩阵教学要求：了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法；掌握对特殊矩阵进行压缩存储时的下标变换公式；了解稀疏矩阵的三类压缩存储方法的特点和适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法；了解广义表的结构特点及其存储表示方法。
5(选讲)树和二叉树解析
树。所以树的定义是递归的 。
2018/10/13 8
2．树的基本术语
树的结点包含一个数据元素及若干指向其子树的分支。
1. 树的结点:包含一个DE和指向其子树的所有分支; 2. 结点的度:一个结点拥有的子树个数,度为零的结点称为叶结点; 3. 树的度:树中所有结点的度的最大值 Max(D(I)) 含义:树中最大分支数为树的度; 4. 结点的层次及树的深度:根为第一层,根的孩子为第二层,若某结 点为第k层,则其孩子为k+1层. 树中结点的最大层次称为树的深度或高度 5.森林:是m(m>=0)棵互不相的树的集合 森林与树概念相近,相互很容易转换. 6 .有序树、无序树 如果树中每棵子树从左向右的排列拥有一定的 顺序，不得互换，则称为有序树，否则称为无序树。
广度优先（按层次）遍历定义为：先访问第一层结点（即树根结点）， 再从左至右访问第二层结点，依次按层访问 ……，直到树中结点全部被 访问为止。对图6-6 (a)中的树进行按层次遍历得到树的广度优先遍历序 列为：ABCDEFG。 说明： ① 前序遍历一棵树恰好等价于前序遍历该树所对应的二叉树。（6.2 节将介绍二叉树） ② 后序遍历树恰好等价于中序遍历该树所对应的二叉树。
2018/10/13 13
树的先序遍历算法描述如下： void Preorder(Btree *root) { if (root!=NULL) {printf(“%c\n”,root->data); //访问根结点 //先根遍历k叉树
for(i=0;i<k;i++)
preorder(root->t[i]); //递归前序遍历每一个子结点 }
祖父 家族关系表示： R={<祖父，伯父>,<祖父，父亲>，<祖父，叔父>， <伯父，堂兄>,<伯父，堂姐>，<父亲，本人>， <叔父，堂弟>,<堂兄，侄儿>}
《数据结构》第二版严蔚敏课后习题作业参考答案(1-7章)
《数据结构》第二版严蔚敏课后习题作业参考答案(1-7章)【第一章绪论】1. 数据结构是计算机科学中的重要基础知识，它研究的是如何组织和存储数据，以及如何通过高效的算法进行数据的操作和处理。
本章主要介绍了数据结构的基本概念和发展历程。
【第二章线性表】1. 线性表是由一组数据元素组成的数据结构，它的特点是元素之间存在着一对一的线性关系。
本章主要介绍了线性表的顺序存储结构和链式存储结构，以及它们的操作和应用。
【第三章栈与队列】1. 栈是一种特殊的线性表，它的特点是只能在表的一端进行插入和删除操作。
本章主要介绍了栈的顺序存储结构和链式存储结构，以及栈的应用场景。
2. 队列也是一种特殊的线性表，它的特点是只能在表的一端进行插入操作，而在另一端进行删除操作。
本章主要介绍了队列的顺序存储结构和链式存储结构，以及队列的应用场景。
【第四章串】1. 串是由零个或多个字符组成的有限序列，它是一种线性表的特例。
本章主要介绍了串的存储结构和基本操作，以及串的模式匹配算法。
【第五章数组与广义表】1. 数组是一种线性表的顺序存储结构，它的特点是所有元素都具有相同数据类型。
本章主要介绍了一维数组和多维数组的存储结构和基本操作，以及广义表的概念和表示方法。
【第六章树与二叉树】1. 树是一种非线性的数据结构，它的特点是一个节点可以有多个子节点。
本章主要介绍了树的基本概念和属性，以及树的存储结构和遍历算法。
2. 二叉树是一种特殊的树，它的每个节点最多只有两个子节点。
本章主要介绍了二叉树的存储结构和遍历算法，以及一些特殊的二叉树。
【第七章图】1. 图是一种非线性的数据结构，它由顶点集合和边集合组成。
本章主要介绍了图的基本概念和属性，以及图的存储结构和遍历算法。
【总结】1. 数据结构是计算机科学中非常重要的一门基础课程，它关注的是如何高效地组织和存储数据，以及如何通过算法进行数据的操作和处理。
本文对《数据结构》第二版严蔚敏的课后习题作业提供了参考答案，涵盖了第1-7章的内容。
离散数学7-树
(b)
(a)
V5
2
1
V7
8
9
V2
V4
2
3
V8
5
V1
V1
V4
V5
1
3
V7
V6
8
V4
2
V8
5
6
V1
1
V5
6
V7
V6
8
3
V8
5
6
V7
9
V3
(e)
V3
(f)
(g)
22
V2
V3
(h)
五.应用举例——求最小生成树
例3 用管梅谷算法求下图的最小生成树。
23
五.应用举例——求最小生成树
例3 用管梅谷算法求下图的最小生成树。
成圈。
首先证明T无简单回路。对n作归纳证明。
(i) n=1时,m=n-1=0,显然无简单回路；
(ii)假设顶点数为n-1时无简单回路，现考察顶点数是n的情况：此时至少有一
个顶点v其次数d(v)=1。因为若n个顶点的次数都大于等于2，则不少于n条边，但这与
m=n-1矛盾。
删去v及其关联边得到新图T’，根据归纳假设T’无简单回路，再加回v及其关联
边又得到图T，则T也无简单回路。
再由图的连通性可知，加入任何一边后就会形成圈，且只有一个圈，否则原图
中会含圈。
9
二. 基本定理——证明
证明(4):(3)(4)，即证一个无圈图若加入任一边就形成圈，
则该图连通，且其任何一边都是桥。
若图不连通,则存在两个顶点vi和vj，在vi和vj之间没有路，若
加边(vi,vj)不会产生简单回路，但这与假设矛盾。由于T无简单回
树的定义和基本概念
25
6.2 二叉树
满二叉树的特点： (1)每一层结点数都达到最大值。即对给 定深度，它是具有最多结点数的二叉树 (2)满二叉树中不存在度数为1的结点,且树 叶都在最下一层上
【例】一个深度为3的满二叉树。
26
6.2 二叉树
完全二叉树特点： （1） 满二叉树是完全二叉树，完全二叉树不一 定是满二叉树。 （2） 叶子结点只可能在层次最大的两层上出现； （3） 对任一结点，若其右分支下的子孙的最大 层次为l，则其左分支下的子孙的最大层次 为必 l 或 l＋1。
6.1 树的定义和基本术语
从逻辑结构看：
1）树中只有根结点没有前趋； 2）除根外，其余结点都有且仅一个前趋； 3）树的结点，可以有零个或多个后继； 4）除根外的其他结点，都存在唯一条从根 到该结点的路径； 5）树是一种分枝结构（除了一个称为根的 结点外）每个元素都有且仅有一个直接 前趋，有且仅有零个或多个直接后继。
6
6.1 树的定义和基本术语
A B E K L F , E, F, G, H, I, J，K，L，M} A是根，其余结点可以 划分为3个互不相交 的集合：T1, T2, T3
T1={B, E, F，K，L} , T2={C, G} , T3={D, H, I, J ，M}; 它们是A的子树。 对于 T1，B是根，其余结点可以划分为2个互不相 交的集合：T11={E，K，L}，T12={F}，T11,T12 7 是B 的子树。
3
第六章
树和二叉树
难点： • 二叉树的遍历及其有关应用
4
第六章
树和二叉树
• 树形结构是一类非常重要的非线性数据结构， 它是以分支关系定义的层次结构。它在现实世 界中广泛存在，在计算机领域中也有广泛应用 • 本章重点讨论二叉树的存储结构及其各种操作， 并研究树和森林与二叉树之间的转换关系。最 后给出一些应用实例
第7章树和二叉树(2)-数据结构教程(Java语言描述)-李春葆-清华大学出版社
1. 二叉树的定义
二叉树也称为二分树，它是有限的结点集合，这个集合或者是空，或者由 一个根结点和两棵互不相交的称为左子树和右子树的二叉树组成。 二叉树中许多概念与树中的概念相同。 在含n个结点的二叉树中，所有结点的度小于等于2，通常用n0表示叶子结 点个数，n1表示单分支结点个数，n2表示双分支结与度为2的树是不同的。
度为2的树至少有3个结点，而二叉树的结点数可以为0。 度为2的树不区分子树的次序，而二叉树中的每个结点最多有 两个孩子结点，且必须要区分左右子树，即使在结点只有一棵 子树的情况下也要明确指出该子树是左子树还是右子树。
2/35
归纳起来，二叉树的5种形态：
Ø
4/35
3. 满二叉树和完全二叉树
在一棵二叉树中，如果所有分支结点都有左孩子结点和右孩子结点，并且 叶子结点都集中在二叉树的最下一层，这样的二叉树称为满二叉树。
可以对满二叉树的结点进行层序编号，约定编号从树根为1开始，按照层 数从小到大、同一层从左到右的次序进行。
满二叉树也可以从结点个数和树高度之间的关系来定义，即一棵高度为h 且有2h-1个结点的二叉树称为满二叉树。
R={r} r={<ai，aj> | ai，aj∈D， 1≤i，j≤n，当n=0时，称为空二叉树；否则其中
有一个根结点，其他结点构成根结点的互不相交的左、右子树，该 左、右两棵子树也是二叉树 } 基本运算： void CreateBTree(string str)：根据二叉树的括号表示串建立其存储结构。 String toString()：返回由二叉树树转换的括号表示串。 BTNode FindNode(x)：在二叉树中查找值为x的结点。 int Height()：求二叉树的高度。 … }
5
E
二叉树也称为二分树，它是有限的结点集合，这个集合或者是空，或者由 一个根结点和两棵互不相交的称为左子树和右子树的二叉树组成。 二叉树中许多概念与树中的概念相同。 在含n个结点的二叉树中，所有结点的度小于等于2，通常用n0表示叶子结 点个数，n1表示单分支结点个数，n2表示双分支结与度为2的树是不同的。
度为2的树至少有3个结点，而二叉树的结点数可以为0。 度为2的树不区分子树的次序，而二叉树中的每个结点最多有 两个孩子结点，且必须要区分左右子树，即使在结点只有一棵 子树的情况下也要明确指出该子树是左子树还是右子树。
2/35
归纳起来，二叉树的5种形态：
Ø
4/35
3. 满二叉树和完全二叉树
在一棵二叉树中，如果所有分支结点都有左孩子结点和右孩子结点，并且 叶子结点都集中在二叉树的最下一层，这样的二叉树称为满二叉树。
可以对满二叉树的结点进行层序编号，约定编号从树根为1开始，按照层 数从小到大、同一层从左到右的次序进行。
满二叉树也可以从结点个数和树高度之间的关系来定义，即一棵高度为h 且有2h-1个结点的二叉树称为满二叉树。
R={r} r={<ai，aj> | ai，aj∈D， 1≤i，j≤n，当n=0时，称为空二叉树；否则其中
有一个根结点，其他结点构成根结点的互不相交的左、右子树，该 左、右两棵子树也是二叉树 } 基本运算： void CreateBTree(string str)：根据二叉树的括号表示串建立其存储结构。 String toString()：返回由二叉树树转换的括号表示串。 BTNode FindNode(x)：在二叉树中查找值为x的结点。 int Height()：求二叉树的高度。 … }
5
E
数据结构习题及答案与实验指导(树和森林)7
第7章树和森林树形结构是一类重要的非线性结构。
树形结构的特点是结点之间具有层次关系。
本章介绍树的定义、存储结构、树的遍历方法、树和森林与二叉树之间的转换以及树的应用等内容。
重点提示：●树的存储结构●树的遍历●树和森林与二叉树之间的转换7-1 重点难点指导7-1-1 相关术语1．树的定义：树是n（n>=0）个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：①有且仅有一个特定的称为根的结点；②其余的结点可分为m（m>=0）个互不相交的子集T1，T2，…，T m，其中每个子集本身又是一棵树，并称为根的子树。
要点：树是一种递归的数据结构。
2．结点的度：一个结点拥有的子树数称为该结点的度。
3．树的度：一棵树的度指该树中结点的最大度数。
如图7-1所示的树为3度树。
4．分支结点：度大于0的结点为分支结点或非终端结点。
如结点a、b、c、d。
5．叶子结点：度为0的结点为叶子结点或终端结点。
如e、f、g、h、i。
6．结点的层数：树是一种层次结构，根结点为第一层，根结点的孩子结点为第二层，…依次类推，可得到每一结点的层次。
7．兄弟结点：具有同一父亲的结点为兄弟结点。
如b、c、d；e、f；h、i。
8．树的深度：树中结点的最大层数称为树的深度或高度。
9．有序树：若将树中每个结点的子树看成从左到右有次序的（即不能互换），则称该树为有序树，否则称为无序树。
10．森林：是m棵互不相交的树的集合。
7-1-2 树的存储结构1．双亲链表表示法以图7-1所示的树为例。
（1）存储思想:因为树中每个元素的双亲是惟一的，因此对每个元素，将其值和一个指向双亲的指针parent构成一个元素的结点，再将这些结点存储在向量中。
（2）存储示意图:-1 data:parent:（3）注意: Parrent域存储其双亲结点的存储下标，而不是存放结点值。
下面的存储是不正确的：-1 data:parent:2．孩子链表表示法（1）存储思想：将每个数据元素的孩子拉成一个链表，链表的头指针与该元素的值存储为一个结点，树中各结点顺序存储起来，一般根结点的存储号为0。
树的逻辑结构
树的逻辑结构树是一种非常重要的数据结构，可以应用于许多领域，如计算机科学、算法、图形学、生物学等等。
其逻辑结构也是非常有特点的，本篇文章将围绕“树的逻辑结构”进行阐述。
一、树的定义树是一种非线性数据结构，由节点和边组成。
每个节点有零个或多个子节点，但只有一个父节点。
称节点没有子节点的节点为叶节点。
称两个节点之间存在一条边，这两个节点就形成了一个父子关系。
二、树的特点1.每个节点都有唯一的一个父节点，除了顶端的根节点；2.节点之间不存在环；3.节点之间有固定的层级关系，根节点在第一层；4.所有节点都能够通过根节点进行访问；5.树中的节点个数可以是有限的或者无限的。
三、树的基本术语1.根节点：具有所有子节点的最高节点；2.子节点：由父节点生成的节点；3.父节点：具有一个或多个子节点的节点；4.叶节点：没有子节点的节点；5.兄弟节点：同一父节点下的节点；6.子树：由一个节点和其所有子孙节点组成的子树；7.层数：根节点的层数为1，其它节点的层数为其父节点层数加1；8.深度：根节点的深度为0，其它节点的深度为其父节点的深度加1；9.路径：从一节点到其它节点所经过的所有边和节点组成的序列；10.森林：由多棵没有相交边的树组成。
四、常用的树的类型1.二叉树：每个节点最多只有两个子节点的树；2.满二叉树：一棵深度为k的树，若所有节点恰好有2^k-1个，则为满二叉树；3.完全二叉树：一棵深度为k的树，除了k层节点外，其它层的节点数都达到了最大值，且第k层所有的节点都集中在最左边的若干位置上；4.二叉查找树：左子树上所有结点的值均小于或等于它的根节点的值，右子树上所有结点的值均大于或等于它的根节点的值；5.平衡二叉树：左右子树的深度相差不超过1的二叉树；6.线索二叉树：将二叉树中所有的空指针用指向该节点中序遍历的前驱和后继的线索来表示的二叉树。
总之，树的逻辑结构是非常有特点的，可以应用于很多领域，并且存在着不同类型的树，因此我们需要根据实际情况选择合适的树去解决问题。
数据结构教程李春葆课后答案第7章树和二叉树
第 7 章 树和二叉树
教材中练习题及参考答案
1. 有一棵树的括号表示为 A(B，C(E，F(G))，D)，回答下面的问题： （1）指出树的根结点。 （2）指出棵树的所有叶子结点。 （3）结点 C 的度是多少？ （4）这棵树的度为多少？ （5）这棵树的高度是多少？ （6）结点 C 的孩子结点是哪些？ （7）结点 C 的双亲结点是谁？ 答：该树对应的树形表示如图 7.2 所示。 （1）这棵树的根结点是 A。 （2）这棵树的叶子结点是 B、E、G、D。 （3）结点 C 的度是 2。 （4）这棵树的度为 3。 （5）这棵树的高度是 4。 （6）结点 C 的孩子结点是 E、F。 （7）结点 C 的双亲结点是 A。
12. 假设二叉树中每个结点值为单个字符，采用二叉链存储结构存储。设计一个算法 计算一棵给定二叉树 b 中的所有单分支结点个数。 解：计算一棵二叉树的所有单分支结点个数的递归模型 f(b)如下：
f(b)=0 若 b=NULL
6 f(b)=f(b->lchild)+f(b->rchild)+1 f(b)=f(b->lchild)+f(b->rchild)
表7.1 二叉树bt的一种存储结构 1 lchild data rchild 0 j 0 2 0 h 0 3 2 f 0 4 3 d 9 5 7 b 4 6 5 a 0 7 8 c 0 8 0 e 0 9 10 g 0 10 1 i 0
答：（1）二叉树bt的树形表示如图7.3所示。
a b c e h j f i d g e h j c f i b d g a
对应的算法如下：
void FindMinNode(BTNode *b,char &min) { if (b->data<min) min=b->data; FindMinNode(b->lchild,min); //在左子树中找最小结点值 FindMinNode(b->rchild,min); //在右子树中找最小结点值 } void MinNode(BTNode *b) //输出最小结点值 { if (b!=NULL) { char min=b->data; FindMinNode(b,min); printf("Min=%c\n",min); } }
教材中练习题及参考答案
1. 有一棵树的括号表示为 A(B，C(E，F(G))，D)，回答下面的问题： （1）指出树的根结点。 （2）指出棵树的所有叶子结点。 （3）结点 C 的度是多少？ （4）这棵树的度为多少？ （5）这棵树的高度是多少？ （6）结点 C 的孩子结点是哪些？ （7）结点 C 的双亲结点是谁？ 答：该树对应的树形表示如图 7.2 所示。 （1）这棵树的根结点是 A。 （2）这棵树的叶子结点是 B、E、G、D。 （3）结点 C 的度是 2。 （4）这棵树的度为 3。 （5）这棵树的高度是 4。 （6）结点 C 的孩子结点是 E、F。 （7）结点 C 的双亲结点是 A。
12. 假设二叉树中每个结点值为单个字符，采用二叉链存储结构存储。设计一个算法 计算一棵给定二叉树 b 中的所有单分支结点个数。 解：计算一棵二叉树的所有单分支结点个数的递归模型 f(b)如下：
f(b)=0 若 b=NULL
6 f(b)=f(b->lchild)+f(b->rchild)+1 f(b)=f(b->lchild)+f(b->rchild)
表7.1 二叉树bt的一种存储结构 1 lchild data rchild 0 j 0 2 0 h 0 3 2 f 0 4 3 d 9 5 7 b 4 6 5 a 0 7 8 c 0 8 0 e 0 9 10 g 0 10 1 i 0
答：（1）二叉树bt的树形表示如图7.3所示。
a b c e h j f i d g e h j c f i b d g a
对应的算法如下：
void FindMinNode(BTNode *b,char &min) { if (b->data<min) min=b->data; FindMinNode(b->lchild,min); //在左子树中找最小结点值 FindMinNode(b->rchild,min); //在右子树中找最小结点值 } void MinNode(BTNode *b) //输出最小结点值 { if (b!=NULL) { char min=b->data; FindMinNode(b,min); printf("Min=%c\n",min); } }
树的存储结构、遍历;二叉树的定义、性质、存储结构、遍历以及树、森林、二叉树的转换
树和二叉树树与二叉树是本书的重点内容之一，知识点多且比较零碎。
其中二叉树又是本章的重点。
在本章中我们要了解树的定义、熟悉树的存储结构、遍历；二叉树的定义、性质、存储结构、遍历以及树、森林、二叉树的转换。
哈夫曼树及哈夫曼编码等内容。
算法的重点是二叉树的遍历及其应用。
6.1 树的定义一、树的定义树：树是n(n>0)个结点的有限集合T。
一棵树满足下列条件：（1）有且仅有一个称为根的结点；（2）其余结点可分为m(m>=0)棵互不相交的有限集合T1,T2,T3,…Tm，其中每个集合又是一棵树，并称之为根的子树。
有关树的一些基本概念：1）结点的度：树中每个结点具有的子树数目或后继结点数。
如图中结点A的度为2，B的度为32) 树的度：所有结点的度的最大值为树的度。
（图中树的度为3）3) 分支结点：即：树中所有度大于0的结点。
4) 叶子结点：即：树中度为零的结点，也称为终端结点。
5) 孩子结点：一个结点的后续结点称为该结点的孩子结点。
6) 双亲结点：一个结点为其后继结点的双亲结点。
7) 子孙结点：一个结点的所有子树中的结点为该结点的子孙结点。
8) 祖先结点：从根结点到一个结点的路径上所有结点（除自己外）称为该结点的祖先结点。
（如Ａ和Ｂ为Ｄ结点的祖先结点）9) 兄弟结点：具有同一父亲的结点互相为兄弟结点。
（如Ｂ和Ｃ为兄弟结点）10) 结点的层数：从根结点到该结点的路径上的结点总数称为该结点的层数（包括该结点）。
11) 树的深度（高度）：树中结点的最大层数为树的深度。
（图中树的深度为4）12) 森林：0个或多个互不相交的树的集合。
上图中：树的度为3，树的深度为4。
结点A，B，C，D，E，F，G，H，I，J的度分别为：2, 3, 2, 0 ,2 , 0, 0, 0, 0, 0叶结点有：D, F, G, H, I, JB,C为兄弟，D, E, F为兄弟，F, G为兄弟。
I，J为兄弟。
二、树的表示1. 树的逻辑结构描述Tree=（D，R）其中：D为具有相同性质的数据元素的集合。
数据结构(朱战立)章 (7)
2
7.1 树
7.1.1 树的定义 树是由n(n≥0)个结点构成的集合。 n＝0的树称为空树；
对n>0的树T有： (1) 有一个特殊的结点称为根结点， 根结点没有前驱结点；
3
(2) 当n>1时， 除根结点外其他结点被分成m(m>0)个互不相 交的集合T1， T2，…， Tm， 其中每一个集合Ti(1≤i≤m)本身又 是一棵结构和树类同的子树。
10
7.1.2 树的表示方法 树的表示方法主要有三种， 分别用于不同的用途。 1. 直观表示法 图7 - 1就是一棵以直观表示法表示的树。 树的直观表示法
主要用于直观描述树的逻辑结构。 2. 形式化表示法 树的形式化表示法主要用于树的理论描述。 树的形式化表
示法定义树T为T＝(D，R)，其中D为树T中结点的集合， R为树T 中结点之间关系的集合。 当树T为空树时D＝∅； 当树T不为空树 时有
5ቤተ መጻሕፍቲ ባይዱ
下面介绍树的其他一些常用术语。 结点： 由数据元素和构造数据元素之间关系的指针组成。 例如， 在图7 - 1(a)中有1个结点， 图7 - 1(b)中有12个结点。 结点的度： 结点所拥有的子树的个数称为该结点的度。 例 如， 在图7 - 1(b)中结点A的度为3， 结点B的度为2， 结点J的 度为0。 叶结点： 度为0的结点称为叶结点， 叶结点也称作终端结 点。 例如， 在图7 - 1(b)中结点J，F，K，L，H，I均为叶结点。
6
分支结点： 度不为0的结点称为分支结点， 分支结点也称 作非终端结点。 显然， 一棵树中除叶结点外的所有结点都是分 支结点。
孩子结点： 树中一个结点的子树的根结点称作这个结点的 孩子结点。 例如， 在图7 - 1(b) 中结点B，C，D是结点A的孩 子结点。 孩子结点也称作后继结点。
7.1 树
7.1.1 树的定义 树是由n(n≥0)个结点构成的集合。 n＝0的树称为空树；
对n>0的树T有： (1) 有一个特殊的结点称为根结点， 根结点没有前驱结点；
3
(2) 当n>1时， 除根结点外其他结点被分成m(m>0)个互不相 交的集合T1， T2，…， Tm， 其中每一个集合Ti(1≤i≤m)本身又 是一棵结构和树类同的子树。
10
7.1.2 树的表示方法 树的表示方法主要有三种， 分别用于不同的用途。 1. 直观表示法 图7 - 1就是一棵以直观表示法表示的树。 树的直观表示法
主要用于直观描述树的逻辑结构。 2. 形式化表示法 树的形式化表示法主要用于树的理论描述。 树的形式化表
示法定义树T为T＝(D，R)，其中D为树T中结点的集合， R为树T 中结点之间关系的集合。 当树T为空树时D＝∅； 当树T不为空树 时有
5ቤተ መጻሕፍቲ ባይዱ
下面介绍树的其他一些常用术语。 结点： 由数据元素和构造数据元素之间关系的指针组成。 例如， 在图7 - 1(a)中有1个结点， 图7 - 1(b)中有12个结点。 结点的度： 结点所拥有的子树的个数称为该结点的度。 例 如， 在图7 - 1(b)中结点A的度为3， 结点B的度为2， 结点J的 度为0。 叶结点： 度为0的结点称为叶结点， 叶结点也称作终端结 点。 例如， 在图7 - 1(b)中结点J，F，K，L，H，I均为叶结点。
6
分支结点： 度不为0的结点称为分支结点， 分支结点也称 作非终端结点。 显然， 一棵树中除叶结点外的所有结点都是分 支结点。
孩子结点： 树中一个结点的子树的根结点称作这个结点的 孩子结点。 例如， 在图7 - 1(b) 中结点B，C，D是结点A的孩 子结点。 孩子结点也称作后继结点。
自考软件基础(数据结构--树与二叉树)
A
B
C
D
E
F
G
H
I
J
第 5 /209页
第二节 二叉树
一、定义
南昌大学
二叉树是一种重要的树形结构，它的特点是：二叉树可以为空（节点个
数为0），任何一个节点的度都小于或等于2，并且，子树有左、右之分，
其次序不能任意颠倒。 二叉树有5种基本形态，如图10-2所示。
第 6 /209页
第二节 二叉树
南昌大学
struct node
{ datatype data； struct node *Lchild,*rchild：
}；
第 15 /209页
第二节 二叉树
南昌大学
例10-5 写出图10-8a所示二叉树的链式存储结构。其链式结构如图10-8b 所示。可以看出：具有n个节点的二叉树链式存储共有2n个链，其中只 有n-1个用来存放该节点的左、右孩子，其余的n +1个指针域为空。
解：第一步：由后序遍历结果确定整个二叉树根为A，由中序结果确定
A的左、右子树。 后序遍历结果： 中序遍历结果：
第 24 /209页
第三节 二叉树的遍历
第二步：确定A的左子树。 1)后序遍历结果：
南昌大学
中序遍历结果：
2）确定B的右子树： ①后序遍历结果：
第 25 /209页
第三节 二叉树的遍历
②中序遍历结果：
南昌大学
第 9 /209页
第二节 二叉树
下面介绍两种特殊的二叉树。
南昌大学
(1) 满二叉树指深度为k，且有2k-1个节点的二叉树。或者说除叶子节点外，
其它节点的度都为2的二叉树。
(2) 完全二叉树一个满二叉树的最下层从右向左连续缺少n (n>=0)个节点 的二叉树。 图10-3为满二叉树和完全二叉树示例。
B
C
D
E
F
G
H
I
J
第 5 /209页
第二节 二叉树
一、定义
南昌大学
二叉树是一种重要的树形结构，它的特点是：二叉树可以为空（节点个
数为0），任何一个节点的度都小于或等于2，并且，子树有左、右之分，
其次序不能任意颠倒。 二叉树有5种基本形态，如图10-2所示。
第 6 /209页
第二节 二叉树
南昌大学
struct node
{ datatype data； struct node *Lchild,*rchild：
}；
第 15 /209页
第二节 二叉树
南昌大学
例10-5 写出图10-8a所示二叉树的链式存储结构。其链式结构如图10-8b 所示。可以看出：具有n个节点的二叉树链式存储共有2n个链，其中只 有n-1个用来存放该节点的左、右孩子，其余的n +1个指针域为空。
解：第一步：由后序遍历结果确定整个二叉树根为A，由中序结果确定
A的左、右子树。 后序遍历结果： 中序遍历结果：
第 24 /209页
第三节 二叉树的遍历
第二步：确定A的左子树。 1)后序遍历结果：
南昌大学
中序遍历结果：
2）确定B的右子树： ①后序遍历结果：
第 25 /209页
第三节 二叉树的遍历
②中序遍历结果：
南昌大学
第 9 /209页
第二节 二叉树
下面介绍两种特殊的二叉树。
南昌大学
(1) 满二叉树指深度为k，且有2k-1个节点的二叉树。或者说除叶子节点外，
其它节点的度都为2的二叉树。
(2) 完全二叉树一个满二叉树的最下层从右向左连续缺少n (n>=0)个节点 的二叉树。 图10-3为满二叉树和完全二叉树示例。
二叉树
7.1.2
二叉树的五种基本形态
Ф
左子树
(a) (b) (c)
右子树
(d)
左子树
(e)
右子树
7.1.3
两种特殊形态的二叉树
结点拥有的子树数称为该结点的度(degree)。度为零的结点称 为叶子(leaf)，其余结点称为分支结点(branch)。树中结点的最大的 度称为树的度。显然，二叉树结点的度可能为0、1或2。 根结点的层次(level)为1，其余结点的层次等于该结点的双亲结 点的层次加1。树中结点的最大层次称为该树的高度或深度。 1．满二叉树 2．完全二叉树
7.6
本章小结
本章讨论了二叉树数据类型的定义以及实现方法。二叉树是 以两个分支关系定义的层次结构，结构中的数据元素之间存在着一 对多的关系，因此它为计算机应用中出现的具有层次关系或分支关 系的数据，提供了一种自然的表示方法。 二叉树是有明确的左子树和右子树的树形结构，因此当用二 叉树来描述层次关系时，其左孩子表示下属关系，而右孩子表示的 是同一层次的关系。 二叉树的遍历算法是实现各种操作的基础。遍历的实质是按 某种规则将二叉树中的数据元素排列成一个线性序列，二叉树的线 索链表便可看成是二叉树的一种线性存储结构，在线索链表上可对 二叉树进行线性化的遍历，即不需要递归，而是从第一个元素起， 逐个访问后继元素直至后继为空止。因此，线索链表是通过遍历生 成的，即在遍历过程中保存结点之间的前驱和后继的关系。
7.1.4
二叉树的几个特性
由二叉树的定义、形态，我们很容易的得出下面二叉树的 一些特性。 性质1 在二叉树的第i 层上至多有 2i-1 个结点(i≥1)。 性质2 深度为k的二叉树中至多含有2k-1 个结点(k≥1)。 性质3 对任何一棵二叉树 T，如果其终端结点数为，度为 2的结点数为，则。 性质4 具有n个结点的完全二叉树的深度为 log2n+1。 性质5 如果对一棵有 n 个结点的完全二叉树（其深度为 log2n+1）的结点按层序（从第1层到第 log2n+1 层，每层从左到 右）从1起开始编号。
树1
有何特征？
2.二叉树
2）从一棵二叉树到树的转换规则是： (1)若结点X是双亲Y的左孩子，则把X的右孩子，右孩子的右孩 子…都与Y用连线相连； (2)去掉原有的双亲到右孩子的连线。
2.二叉树
3) 树和二叉树间的转换实例
2.二叉树
2.6 二叉树的性质
性质1：在二叉树的第i层上至多有2i-1个结点(i≥1)。 证明：可用数学归纳法予以证明。 当i=1时有2i-1=20=1，同时第一层上只有一个根结点，故命题成立。 设当i=k时成立，即第k层上至多有2k-1个结点。 当i=k+1时，由于二叉树的每个结点至多有两个孩子，所以第k+1层 上至多有22k-1=2k个结点，故命题成立。
1.树的基本概念
结点的层次：从根结点开始，根结点为第一 层，根的孩子为第二层，根的孩子的孩子为 第三层，依次类推。 如：结点M的层次为4。 树的深度：树中结点的最大层次数。 如：该树的深度为4。 堂兄弟：双亲在同一层上的结点互称为堂兄 弟。 例如结点E，G，H互为堂兄弟。 路径：若存在一个结点序列k1,k2,…,kj, 可 使k1到达kj, 则称这个结序序列是k1到达kj 的一条路径。
树的引入
树的引入
树与线性表的逻辑特征比较
线性表是一种线性结构
线性结构的逻辑特征是：有且仅有一个开始结点和一个 终端结点，且所有结点都最多只有一个直接前趋和一个 直接后继。
树是一种非线性结构
非线性结构的逻辑特征是一个结点可能有多个直接前趋 和直接后继。
结构特征
线性表 树 线性结构 非线性结构
直接前趋个数
1.树的基本概念
1.2树的直观表示形式
(1)直观表示法
使用圆圈表示结点，连线表示结点间的关系，结点的名字可写在圆 圈内或圆圈旁
软件技术--树与二叉树
（2）若*p结点只有左子树PL或者只有右子树PR， 此时只要令PL或PR直接成为其双亲结点*f的左子 树即可。显然，作此修改也不会破坏二叉排序树 的特性。
（3 ） 若*p结点的左子树和右子树均不为空。
五、哈夫曼树的应用
1、什么是哈夫曼树
假设有n个权值{w1，w2，…，wn}，试构造一棵有n 个叶子结点的二叉树，每个叶子结点带权wi，则其中带 权路径长度WPL最小的二叉树称作最优二叉树或哈夫 曼树。
2、 树的基本术语
结点的度：一个结点拥有的子树数称为该结点的度。 叶子结点：度为0的结点称为叶子（Leaf）或终端结点。 非终端结点：度不为0的结点称为非终端结点或分支结点。除根结 点之外，分支结点也称为内部结点。
树的度：树内各结点的度的最大值称为树的度。 树中结点之间的关系：在描述结点之间的关系时，通常用家族关 系来形象的称呼结点之间的联系。结点的子树的根称为该结点的孩 子（Child），相应的，该结点称为孩子的双亲（Parents）或父结点。 同一个双亲的孩子之间称为兄弟（Sibling）。 结点的层次（Level）：一棵树从根开始定义起，根为第一层，根的 孩子为第二层，…，依此类推。若某结点在第i层，则其子树的根就 在第i＋1层。其双亲在同一层的结点互为堂兄弟。
(4) 性质4: 具有n个结点的完全二叉树的深度为log2n＋1。
3、几种特殊的二叉树
• 满二叉树：深度为K，且存在2K-1个结点的二叉树。 • 完全二叉树：至多只有最下面两层上的结点度数可以小于
2，并且最下层结点都集中在该层最左边的位置。 • 平衡二叉树：或是一棵空树，或是具有下列性质的二叉树：
每次插入一个结点的递归算法
struct node {anytype data; struct node *lchild; struct node *rchild; } *root; void insnode(t,d) struct node *t; anytype d;
（3 ） 若*p结点的左子树和右子树均不为空。
五、哈夫曼树的应用
1、什么是哈夫曼树
假设有n个权值{w1，w2，…，wn}，试构造一棵有n 个叶子结点的二叉树，每个叶子结点带权wi，则其中带 权路径长度WPL最小的二叉树称作最优二叉树或哈夫 曼树。
2、 树的基本术语
结点的度：一个结点拥有的子树数称为该结点的度。 叶子结点：度为0的结点称为叶子（Leaf）或终端结点。 非终端结点：度不为0的结点称为非终端结点或分支结点。除根结 点之外，分支结点也称为内部结点。
树的度：树内各结点的度的最大值称为树的度。 树中结点之间的关系：在描述结点之间的关系时，通常用家族关 系来形象的称呼结点之间的联系。结点的子树的根称为该结点的孩 子（Child），相应的，该结点称为孩子的双亲（Parents）或父结点。 同一个双亲的孩子之间称为兄弟（Sibling）。 结点的层次（Level）：一棵树从根开始定义起，根为第一层，根的 孩子为第二层，…，依此类推。若某结点在第i层，则其子树的根就 在第i＋1层。其双亲在同一层的结点互为堂兄弟。
(4) 性质4: 具有n个结点的完全二叉树的深度为log2n＋1。
3、几种特殊的二叉树
• 满二叉树：深度为K，且存在2K-1个结点的二叉树。 • 完全二叉树：至多只有最下面两层上的结点度数可以小于
2，并且最下层结点都集中在该层最左边的位置。 • 平衡二叉树：或是一棵空树，或是具有下列性质的二叉树：
每次插入一个结点的递归算法
struct node {anytype data; struct node *lchild; struct node *rchild; } *root; void insnode(t,d) struct node *t; anytype d;
树
已知连通图G ，求其生成树步骤。
生成树的性质
设 G V , E 为连通图， V n， E m， (1) G至少有一棵生成树， (2) m n 1， (3) 设 T 是 G 的生成树， T ' 是 T 的余树，
则 T '中有 m n 1条边。 (4) 设 T 是 G 的生成树， T ' 是 T 的余树，
又由(1) m n 1 ，代入上式，解得 k 2 ，
即 T 至少2片叶。
例题
画出所有的6个顶点的非同构的树。 解：所要画的树有6个顶点，则边数为5，因此 6个顶点的度数之和为10，可以产生以下五 种 度数序列：
(1) 1 1 1 1 1 5
T1
(2) 1 1 1 1 2 4
(3) 1 1 1 1 3 3
注意： (1) 生成树不唯一，
(2) 余树不一定是树。
(3)
(3)是(2)的余树。
生成树存在条件
定理：无向图G具有生成树当且仅当G是连通图 证明:
必要性 显然 充分性，如果G无回路,则G本身就是它的生成树,如G 有回路,则在回路上任取一条边并去掉后仍是连通的, 如G仍有回路,则继续在该回路上去掉一条边,直到图 中无回路为止,此时该图就是G的一棵生成树
树的性质
(1) 树中顶点数与边数的关系： n m 1 。
(2) 非平凡树至少2片树叶。
证明： 设 T V , E 为 n 阶非平凡树，
设 T 有 k 片树叶，则有 (n k) 个顶点度数大于等
n
于2， 由握手定理， 2m d (vi ) k 2(n k ) i 1
T2
(4) 1 1 1 2 2 3
T3
(5)1 1 2 2 2 2
生成树的性质
设 G V , E 为连通图， V n， E m， (1) G至少有一棵生成树， (2) m n 1， (3) 设 T 是 G 的生成树， T ' 是 T 的余树，
则 T '中有 m n 1条边。 (4) 设 T 是 G 的生成树， T ' 是 T 的余树，
又由(1) m n 1 ，代入上式，解得 k 2 ，
即 T 至少2片叶。
例题
画出所有的6个顶点的非同构的树。 解：所要画的树有6个顶点，则边数为5，因此 6个顶点的度数之和为10，可以产生以下五 种 度数序列：
(1) 1 1 1 1 1 5
T1
(2) 1 1 1 1 2 4
(3) 1 1 1 1 3 3
注意： (1) 生成树不唯一，
(2) 余树不一定是树。
(3)
(3)是(2)的余树。
生成树存在条件
定理：无向图G具有生成树当且仅当G是连通图 证明:
必要性 显然 充分性，如果G无回路,则G本身就是它的生成树,如G 有回路,则在回路上任取一条边并去掉后仍是连通的, 如G仍有回路,则继续在该回路上去掉一条边,直到图 中无回路为止,此时该图就是G的一棵生成树
树的性质
(1) 树中顶点数与边数的关系： n m 1 。
(2) 非平凡树至少2片树叶。
证明： 设 T V , E 为 n 阶非平凡树，
设 T 有 k 片树叶，则有 (n k) 个顶点度数大于等
n
于2， 由握手定理， 2m d (vi ) k 2(n k ) i 1
T2
(4) 1 1 1 2 2 3
T3
(5)1 1 2 2 2 2
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
出队操作： front=(front+1)%MaxSize; 取出front处元素e; (e=q->data[q->front])
b
c
3
2 1
a
40dຫໍສະໝຸດ rearfront rear
复习：
2.循环队列代码复习
入队：
1.队满不能入队； 2.队尾指针+1 3.将插入的元素e放入队尾处 4.入队成功！
出队：
q->front=q->rear=p; else { q->rear->next=p; //将*p结点链到队尾，并将rear指向它
q->rear=p; } }
q
a1
a2
…
an ∧
p
e
出队deQueue(q，e)
考虑情况：
原队列为空 原队列只有一个结点 其他情况(多个结点)
q a1
q
q
a1 ∧
a2
…
{ if (q->front==q->rear)
q->rear=(q->rear+1)%MaxSize;
return false;
q->data[q->rear]=e;
q->front=(q->front+1)%MaxSize;
return true;
e=q->data[q->front];
}
return true;
树的实例
«UNIX文件系统结构
bin
math ds sw
/ (root)
人类的族谱
lib
各种社us会er关系
etc
各类分类编码
编译程序的语法树 yIinnternteato中的xDieNS（域名系统）
Queue.cpp Stack.cpp Tree.cpp
形式化定义
树：T={D，R}。D是包含n个结点的有限集合（n≥0）。当n=0 时为空树，否则关系R满足以下条件:
q->front=q->rear=NULL;
else
//队列中有多个结点时
q->front=q->front->next;
e=t->data;
free(t);
return true;
}
t 删除
q
a1
a2
…
an ∧
8/19
9/26
树的实例
«五子棋游戏
……..
……..
…... …... …... …...
复习回顾：
一、队的基本概念（定义，操作受限） 二、顺序结构（1.顺序队、2.循环队列）
顺序队结构体类型：
typedef struct { ElemType data[MaxSize]；
int front,rear； } SqQueue;
队空条件：front = rear 队满条件：rear = MaxSize－1 元素e进队：rear++; data[rear]=e; 元素e出队：front++; e=data[front];
{ if (q->rear==MaxSize-1)
&e)
return false;
{ if (q->front==q->rear)
q->rear++;
return false;
q->data[q->rear]=e;
q->front++;
return true;
e=q->data[q->front];
}
return true;
}
复习：循环队列
rear c 4
b3
a2
front
1
0
a b 3 21
40
c
Q->rear
Q->front
队空条件： front = rear 队满条件： (rear+1)%MaxSize = front
进队e操作：rear=(rear+1)%MaxSize; 将e放在rear处( q->data[q->rear]=e)
-1 0 1 2 3 4 a b c d e -011 -012341
元元元元素素素素bacebad出进入入进队队队队::::
qqq-q>--->>f>rrrroeeeanaartrr++++++++;;;;
rf
r f r f r r r front rear eqqq=---q>>>-ddd>aaadtttaaaat[[[aqqq[---q>>>-rrr>eeefaaarrror]]]n===t‘‘‘]cebad;’’’
多个叶子结点 (无后继)
其它数据元素 (一个前驱、
多个后继)
只有根结点的树
A
子树
有子树的树
A
根
B
C
D
E
F GH I J
K
L
M
15/26
（1）树形表示法。使用一棵倒置的树表示树结构，非常直观和 形象。
有且仅有一个结点d0∈D，它对于关系R来说没有前驱结点，结 点d0称作树的根结点。
除根结点外，每个结点有且仅有一个前驱结点。 D中每个结点可以有零个或多个后继结点。
12/26
线性结构 第一个数据元素
(无前驱)
最后一个数据元素 (无后继)
其它数据元素 (一个前驱、
一个后继)
树型结构 根结点
(无前驱)
}
复习：链队代码复习
进队enQueue(q，e)
考虑情况：
原队列为空 原队列非空
q-
p q
e
q
a1
a2
…
an ∧
p
e
void enQueue(LinkQuNode *&q，ElemType e) { DataNode *p;
p=(DataNode *)malloc(sizeof(DataNode)); p->data=e; p->next=NULL; if (q->rear==NULL) //若链队为空，新结点是队首结点又是队尾结点
复习：顺序队代码复习
入队：
1.队满不能入队； 2.队尾指针+1 3.将插入的元素e放入队尾处 4.入队成功！
出队：
1.队空不能出队； 2.队头指针+1； 3.取队头元素值并赋给变量e; 4.出队成功！
bool enQueue(SqQueue *&q,ElemType e) bool deQueue(SqQueue *&q,ElemType
an ∧
7/19
bool deQueue(LinkQuNode *&q，ElemType &e)
{ DataNode *t;
if (q->rear==NULL) return false; //队列为空
t=q->front;
//t指向第一个数据结点
if (q->front==q->rear)
//队列中只有一个结点时
1.队空不能出队； 2.队头指针+1； 3.取队头元素值并赋给变量e; 4.出队成功！
bool enQueue(SqQueue *&q,ElemType e) bool deQueue(SqQueue *&q,ElemType
{ if ((rear+1)%MaxSize = front)
&e)
return false;
b
c
3
2 1
a
40dຫໍສະໝຸດ rearfront rear
复习：
2.循环队列代码复习
入队：
1.队满不能入队； 2.队尾指针+1 3.将插入的元素e放入队尾处 4.入队成功！
出队：
q->front=q->rear=p; else { q->rear->next=p; //将*p结点链到队尾，并将rear指向它
q->rear=p; } }
q
a1
a2
…
an ∧
p
e
出队deQueue(q，e)
考虑情况：
原队列为空 原队列只有一个结点 其他情况(多个结点)
q a1
q
q
a1 ∧
a2
…
{ if (q->front==q->rear)
q->rear=(q->rear+1)%MaxSize;
return false;
q->data[q->rear]=e;
q->front=(q->front+1)%MaxSize;
return true;
e=q->data[q->front];
}
return true;
树的实例
«UNIX文件系统结构
bin
math ds sw
/ (root)
人类的族谱
lib
各种社us会er关系
etc
各类分类编码
编译程序的语法树 yIinnternteato中的xDieNS（域名系统）
Queue.cpp Stack.cpp Tree.cpp
形式化定义
树：T={D，R}。D是包含n个结点的有限集合（n≥0）。当n=0 时为空树，否则关系R满足以下条件:
q->front=q->rear=NULL;
else
//队列中有多个结点时
q->front=q->front->next;
e=t->data;
free(t);
return true;
}
t 删除
q
a1
a2
…
an ∧
8/19
9/26
树的实例
«五子棋游戏
……..
……..
…... …... …... …...
复习回顾：
一、队的基本概念（定义，操作受限） 二、顺序结构（1.顺序队、2.循环队列）
顺序队结构体类型：
typedef struct { ElemType data[MaxSize]；
int front,rear； } SqQueue;
队空条件：front = rear 队满条件：rear = MaxSize－1 元素e进队：rear++; data[rear]=e; 元素e出队：front++; e=data[front];
{ if (q->rear==MaxSize-1)
&e)
return false;
{ if (q->front==q->rear)
q->rear++;
return false;
q->data[q->rear]=e;
q->front++;
return true;
e=q->data[q->front];
}
return true;
}
复习：循环队列
rear c 4
b3
a2
front
1
0
a b 3 21
40
c
Q->rear
Q->front
队空条件： front = rear 队满条件： (rear+1)%MaxSize = front
进队e操作：rear=(rear+1)%MaxSize; 将e放在rear处( q->data[q->rear]=e)
-1 0 1 2 3 4 a b c d e -011 -012341
元元元元素素素素bacebad出进入入进队队队队::::
qqq-q>--->>f>rrrroeeeanaartrr++++++++;;;;
rf
r f r f r r r front rear eqqq=---q>>>-ddd>aaadtttaaaat[[[aqqq[---q>>>-rrr>eeefaaarrror]]]n===t‘‘‘]cebad;’’’
多个叶子结点 (无后继)
其它数据元素 (一个前驱、
多个后继)
只有根结点的树
A
子树
有子树的树
A
根
B
C
D
E
F GH I J
K
L
M
15/26
（1）树形表示法。使用一棵倒置的树表示树结构，非常直观和 形象。
有且仅有一个结点d0∈D，它对于关系R来说没有前驱结点，结 点d0称作树的根结点。
除根结点外，每个结点有且仅有一个前驱结点。 D中每个结点可以有零个或多个后继结点。
12/26
线性结构 第一个数据元素
(无前驱)
最后一个数据元素 (无后继)
其它数据元素 (一个前驱、
一个后继)
树型结构 根结点
(无前驱)
}
复习：链队代码复习
进队enQueue(q，e)
考虑情况：
原队列为空 原队列非空
q-
p q
e
q
a1
a2
…
an ∧
p
e
void enQueue(LinkQuNode *&q，ElemType e) { DataNode *p;
p=(DataNode *)malloc(sizeof(DataNode)); p->data=e; p->next=NULL; if (q->rear==NULL) //若链队为空，新结点是队首结点又是队尾结点
复习：顺序队代码复习
入队：
1.队满不能入队； 2.队尾指针+1 3.将插入的元素e放入队尾处 4.入队成功！
出队：
1.队空不能出队； 2.队头指针+1； 3.取队头元素值并赋给变量e; 4.出队成功！
bool enQueue(SqQueue *&q,ElemType e) bool deQueue(SqQueue *&q,ElemType
an ∧
7/19
bool deQueue(LinkQuNode *&q，ElemType &e)
{ DataNode *t;
if (q->rear==NULL) return false; //队列为空
t=q->front;
//t指向第一个数据结点
if (q->front==q->rear)
//队列中只有一个结点时
1.队空不能出队； 2.队头指针+1； 3.取队头元素值并赋给变量e; 4.出队成功！
bool enQueue(SqQueue *&q,ElemType e) bool deQueue(SqQueue *&q,ElemType
{ if ((rear+1)%MaxSize = front)
&e)
return false;