当前位置：文档之家 › 数据结构第六章

数据结构第六章

  • 格式：docx
  • 大小：38.60 KB
  • 文档页数：18

下载文档原格式

  / 18

合集下载

数据结构课后习题答案及解析第六章

数据结构课后习题答案及解析第六章

第六章树和二叉树（下载后用阅读版式视图或web版式可以看清）习题一、选择题1．有一“遗传”关系：设x是y的父亲，则x可以把它的属性遗传给y。

表示该遗传关系最适合的数据结构为( )。

A.向量B.树 C图 D.二叉树2．树最合适用来表示( )。

A.有序数据元素B元素之间具有分支层次关系的数据C无序数据元素 D.元素之间无联系的数据3．树B的层号表示为la，2b，3d，3e，2c，对应于下面选择的( )。

A. la (2b (3d,3e),2c)B. a(b(D,e),c)C. a(b(d,e),c)D. a(b,d(e),c)4.高度为h的完全二叉树至少有( )个结点，至多有( )个结点。

A. 2h_lB.h C．2h-1 D. 2h5.在一棵完全二叉树中，若编号为f的结点存在右孩子，则右子结点的编号为( )。

A. 2iB. 2i-lC. 2i+lD. 2i+26.一棵二叉树的广义表表示为a(b(c)，d(e(，g(h))，f))，则该二叉树的高度为 ( )。

A.3B.4C.5D.67.深度为5的二叉树至多有( )个结点。

A. 31B. 32C. 16D. 108.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为( )个。

A. 15B. 16C. 17D. 479.题图6-1中，( )是完全二叉树，( )是满二叉树。

..专业知识编辑整理..10.在题图6-2所示的二叉树中：(1)A结点是A.叶结点B根结点但不是分支结点 C根结点也是分支结点 D.分支结点但不是根结点(2)J结点是A.叶结点B．根结点但不是分支结点 C根结点也是分支结点 D.分支结点但不是根结点(3)F结点的兄弟结点是A.EB.D C．空 D.I(4)F结点的双亲结点是A.AB.BC.CD.D(5)树的深度为A.1B.2C.3D.4(6)B结点的深度为A.1B.2C.3D.4(7)A结点所在的层是A.1B.2C.3D.4..专业知识编辑整理..11.在一棵具有35个结点的完全二叉树中，该树的深度为( )。

数据结构(C语言版)严蔚敏第6章 树和二叉树

数据结构(C语言版)严蔚敏第6章 树和二叉树
如图6-1(b)中结点H、I、J、K、L、M、N是叶子 结点，而所有其它结点都是分支结点。
⑷ 孩子结点、双亲结点、兄弟结点
一个结点的子树的根称为该结点的孩子结点(child) 或子结点；相应地，该结点是其孩子结点的双亲结点 (parent)或父结点。
4
如图6-1(b)中结点B 、C、D是结点A的子结点，而结 点A是结点B 、C、D的父结点；类似地结点E 、F是结 点B的子结点，结点B是结点E 、F的父结点。
这是树的递归定义，即用树来定义树，而只有 一个结点的树必定仅由根组成，如图6-1(a)所示。
2
2 树的基本术语
⑴ 结点(node)：一个数据元素及其若干指向其子树的分支。 ⑵ 结点的度(degree) 、树的度：结点所拥有的子树
的棵数称为结点的度。树中结点度的最大值称为树的度。
A
B
C
D
A
E
F G HI J
同一双亲结点的所有子结点互称为兄弟结点。
如图6-1(b)中结点B 、C、D是兄弟结点；结点E 、 F是兄弟结点。
⑸ 层次、堂兄弟结点
规定树中根结点的层次为1，其余结点的层次等于 其双亲结点的层次加1。
若某结点在第l(l≧1)层，则其子结点在第l+1层。
双亲结点在同一层上的所有结点互称为堂兄弟结点。 如图6-1(b)中结点E、F、G、H、I、J。
(a) 只有根结点
K
LM N
图6-1 树的示例形式
(b) 一般的树
3
如图6-1(b)中结点A的度是3 ，结点B的度是2 ，结点 M的度是0，树的度是3 。
⑶ 叶子(left)结点、非叶子结点：树中度为0的
结点称为叶子结点(或终端结点)。相对应地，度不为 0的结点称为非叶子结点(或非终端结点或分支结点)。 除根结点外，分支结点又称为内部结点。

数据结构(CC++语言版)第六章new

数据结构(CC++语言版)第六章new
为简单路径。
回路 若路径上第一个顶点 v1 与最后一个顶点vm 重合, 则称这样的路径
为回路或环。
路径长度
非带权图的路径长度是指此路径上边的条数。 带权图的路径长度是指路径上各边的权之和。
▪图的连通 在无向图G中，若两个顶点vi和vj之间有 路径存在，则称vi 和vj 是连通的。若G中任意两 个顶点都是连通的，则称G为连通图。非连通图的 极大连通子图叫做连通分量。
5 9
1
12
63
8
15
76
6
3
4
16
7
60
A
B 40 80 C
30
75
35
D
E
45
▪子图 设有两个图 G＝(V, E) 和 G‘＝(V’, E‘)。若 V’ V 且 E‘E, 则称 图G’ 是 图G 的子图。
路径 在图 G＝(V, E) 中, 若从顶点 vi 出发, 沿一些边经过一些顶点 vp1,
种带权图叫做网。
▪生成树 一个连通图的生成树是它的极小 连通子图，在n个顶点的情形下，有n-1条 边。生成森林
不予讨论的图 包含顶点到其自身的边； 一条边在图中重复出现
6.2 图的存储结构
一. 图的数组表示法 (邻接矩阵表示法)
基本思想：
✓ 图需要存储的信息：顶点和弧。 ✓ 引入两个数组，一个记录各个顶点信息的顶点表，还
有一个表示各个顶点之间关系的邻接矩阵。
设图 A = (V, E)是一个有 n 个顶点的图，则图的 邻接矩阵是一个二维数组 A.arcs[n][n]，定义：
1 arcs[i][j] = 0
若<vi, vj> 或 (vi, vj) E 反之
2
1

数据结构第六章 哈夫曼树

数据结构第六章 哈夫曼树

6.3哈夫曼树6.3.1基本术语1.路径和路径长度若在一棵中存在着一个结点序列k1 ,k2,…,kj，使得ki是k1+i 的双亲(1ji<≤)，则称此结点序列是从k1～kj的路径，因树中每个结点只有一个双亲结点，所以它也是这两个结点之间k 1～kj所经过的分支数称为这两点之间的路径长度，它等于路径上的结点数减1(实际就是边数)。

如在图5-19(a)所示的二叉树中，从树根结点L到叶子结点P的路径为结点序列L、M、S、P，路径长度为3。

(a) (b)(c) (d)图5-19 二叉排序树的删除2.结点的权和带权路径长度在许多应用中，常常将树中的结点赋上一个有着某种意义的实数，我们称此实数为该结点的权。

结点的带权路径长度规定为从树根结点到该结点之间的路径长度与该结点上权的乘积3.树的带权路径长度树的带权路径长度定义为树中所有叶子结点的带权路径长度这和，通常记为：2 WPL = ∑=n i i i lw 1其中n 表示叶子结点的数目，i w 和i l 分别表示叶子结点i k 的权值和根到i k 之间的路径长度 。

4.哈夫曼树哈夫曼(Huffman)树又称最优二叉树。

它是n 个带权叶子结点构成的所有二叉树中，带权路径长度 WPL 最小的二叉树。

因为构造这种树的算法是最早由哈夫曼于1952年提出的，所以被称之为哈夫曼树。

例如，有四个叶子结点a 、b 、c 、d ，分别带权为9、4、5、2，由它们构成的三棵不同的二叉树（当然还有其它许多种）分别如图5-20(a)到图5-20(c)所示。

b ac a b cd d c a b d(a) (b) (c)图5-20 由四个叶子结点构成的三棵不同的带权二叉树 每一棵二叉树的带权路径长度WPL 分别为：(a) WPL = 9×2 + 4×2 + 5×2 + 2×2 = 40(b) WPL = 4×1 + 2×2 + 5×3 + 9×3 = 50(c) WPL = 9×1 + 5×2 + 4×3 + 2×3 = 37其中图5-20(c)树的WPL 最小，稍后便知，此树就是哈夫曼树。

数据结构-第6章 树和二叉树---4. 树和森林(V1)

数据结构-第6章 树和二叉树---4. 树和森林(V1)
ElemType data ; struct CSnode *firstchild, *nextsibing ; }CSNode;
6.4.1 树的存储结构
R AB C D EG F
R⋀
A
⋀D
⋀B
⋀E ⋀
C⋀
⋀G
⋀F ⋀
6.4.2 树、森林和二叉树的转换
1. 树转换为二叉树 将树转换成二叉树在“孩子兄弟表示法”中已 给出，其详细步骤是： ⑴ 加线。在树的所有相邻兄弟结点之间加一 条连线。 ⑵ 去连线。除最左的第一个子结点外，父结点 与所有其它子结点的连线都去掉。 ⑶ 旋转。将树以根结点为轴心，顺时针旋转 450，使之层次分明。
B C
D
A E
L HK
M
技巧：无左孩子 者即为叶子结点
6.4.3 树和森林的遍历
1. 树的遍历 由树结构的定义可知，树的遍历有二种方法。 ⑴ 先序遍历：先访问根结点，然后依次先序 遍历完每棵子树等。价于对应二叉树的先序遍历
⑵ 后序遍历：先依次后序遍历完每棵子树，然 后访问根结点。等价于对应二叉树的中序遍历
0 R -1 1A 0 2B 0 3C 0
}Ptree ; R
4D 1 5E 1
AB C
6F 3
7G 6
DE
F
8H 6
9I 6
G H I 10~MAX_Size-1 ... ...
6.4.1 树的存储结构
2. 孩子表示法
每个结点的孩子结点构成一个单链表，即有n 个结点就有n个孩子链表；
n个孩子的数据和n个孩子链表的头指针组成一 个顺序表； 结点结构定义： 顺序表定义：
typedef struct PTNode { ElemType data ;

《数据结构(C语言版 第2版)》(严蔚敏 著)第六章练习题答案

《数据结构(C语言版 第2版)》(严蔚敏 著)第六章练习题答案

《数据结构（C语言版第2版）》（严蔚敏著）第六章练习题答案第6章图1．选择题（1）在一个图中，所有顶点的度数之和等于图的边数的（）倍。

A．1/2B．1C．2D．4答案：C（2）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。

A．1/2B．1C．2D．4答案：B解释：有向图所有顶点入度之和等于所有顶点出度之和。

（3）具有n个顶点的有向图最多有（）条边。

A．n B．n(n-1)C．n(n+1)D．n2答案：B解释：有向图的边有方向之分，即为从n个顶点中选取2个顶点有序排列，结果为n(n-1)。

（4）n个顶点的连通图用邻接距阵表示时，该距阵至少有（）个非零元素。

A．n B．2(n-1)C．n/2D．n2答案：B所谓连通图一定是无向图,有向的叫做强连通图连通n个顶点,至少只需要n-1条边就可以了,或者说就是生成树由于无向图的每条边同时关联两个顶点,因此邻接矩阵中每条边被存储了两次（也就是说是对称矩阵）,因此至少有2(n-1)个非零元素（5）G是一个非连通无向图，共有28条边，则该图至少有（）个顶点。

A．7B．8C．9D．10答案：C解释：8个顶点的无向图最多有8*7/2=28条边，再添加一个点即构成非连通无向图，故至少有9个顶点。

（6）若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是（）图。

A．非连通B．连通C．强连通D．有向答案：B解释：即从该无向图任意一个顶点出发有到各个顶点的路径，所以该无向图是连通图。

（7）下面（）算法适合构造一个稠密图G的最小生成树。

A．Prim算法B．Kruskal算法C．Floyd算法D．Dijkstra算法答案：A解释：Prim算法适合构造一个稠密图G的最小生成树，Kruskal算法适合构造一个稀疏图G的最小生成树。

（8）用邻接表表示图进行广度优先遍历时，通常借助（）来实现算法。

A．栈 B.队列 C.树D．图答案：B解释：广度优先遍历通常借助队列来实现算法，深度优先遍历通常借助栈来实现算法。

数据结构第六章

数据结构第六章
i 1 k ( 第 i 层的最大结点数 ) 2 2 1 i 1 i 1 k k
K
L
M
任何一棵非空树是一个二元组 Tree = （root，F） 其中：root 被称为根结点， F 被称为子树森林

6.2 二叉树
定义
定义：二叉树是n(n0)个结点的有限集，它或为空树 (n=0)，或由一个根结点和两棵分别称为左子树和右子树 的互不相交的二叉树构成 二叉树，度为2的树? 特点
树和二叉树
树是一类重要的非线性数据结构，以分支 关系描述数据元素之间的层次结构 6.1 树 定义: 树(tree)是n(n≥0)个结点的有限集。在任意一棵非
空树中：
有且仅有一个特殊的结点，称为树的根结点(root)
当n>1时，除根结点之外的其余结点可分为
m(m>0)个 互不相交的有限集合T1,T2,……Tm，其 中每一个集合本身又是一棵树，称为根的子树 (subtree)
证明：用归纳法证明之 i=1时，只有一个根结点，2i-1 = 20 = 1； 假设对所有j(1j<i)命题成立，即第j层上至多有2j-1 个结 点,那么，第i-1层至多有2i-2个结点 又二叉树每个结点的度至多为2 第i层上最大结点数是第i-1层的2倍，即2i-2 2 = 2i-1 故命题得证 k 性质2：深度为k的二叉树至多有 2 1 个结点(k1) 证明：由性质1，可得深度为k 的二叉树最大结点数是
基本操作 P ：
插入类：
InitTree(&T) // 初始化臵空树 CreateTree(&T, definition) // 按定义构造树 Assign(T, cur_e, value) // 给当前结点赋值 InsertChild(&T, &p, i, c) // 将以c为根的树插入为 结点p的第i棵子树

数据结构——用C语言描述 第六章 树状结构

数据结构——用C语言描述 第六章 树状结构

数据结构——用C语言描述第六章树状结构在计算机科学中，数据结构是组织和存储数据的方式，以便能够高效地访问和操作这些数据。

树状结构是一种重要的数据结构，它在许多算法和应用中都发挥着关键作用。

树状结构就像是一棵倒立的树，有一个根节点，然后从根节点向下延伸出许多分支，每个分支又可以进一步延伸出更多的分支。

这种结构使得数据的组织和管理更加清晰和高效。

在树状结构中，每个节点可以包含数据以及指向其子节点的指针。

节点之间通过这些指针形成层次关系。

树状结构的一个重要特点是，除了根节点外，每个节点都有且仅有一个父节点。

二叉树是树状结构中最常见的一种形式。

二叉树中的每个节点最多有两个子节点，分别称为左子节点和右子节点。

二叉搜索树是一种特殊的二叉树，它具有一定的规则。

对于二叉搜索树中的每个节点，其左子树中的所有节点的值都小于该节点的值，而其右子树中的所有节点的值都大于该节点的值。

这种特性使得在二叉搜索树中进行查找、插入和删除操作的效率很高。

例如，如果要在二叉搜索树中查找一个值，我们可以从根节点开始。

如果要查找的值小于当前节点的值，就向左子树继续查找；如果大于当前节点的值，就向右子树继续查找。

直到找到目标值或者确定该值不存在。

用 C 语言来实现二叉搜索树，首先需要定义一个节点结构体，来存储节点的数据以及左右子节点的指针。

｀｀｀ctypedef struct TreeNode ｛int data;struct TreeNode left;struct TreeNode right;｝ TreeNode;｀｀｀接下来，实现插入节点的函数。

插入节点时，需要按照二叉搜索树的规则，找到合适的位置插入新节点。

｀｀｀cvoid insertNode(TreeNode root, int value) ｛if （root ＝＝ NULL) ｛root ＝（TreeNode ）malloc(sizeof(TreeNode)）；（root)＞data ＝ value;（root)＞left ＝ NULL;（root)＞right ＝ NULL;return;｝if （value ＜（root)＞data) ｛insertNode(＆（（root)＞left)， value)；｝ else if （value ＞（root)＞data) ｛insertNode(＆（（root)＞right)， value)；｝｝｀｀｀查找节点的函数也类似，根据比较值的大小在左右子树中递归查找。

第6章 数据结构-二维数组

第6章 数据结构-二维数组
2
,…β m)
其中每一个数据元素β i是一个行向量
β
i ＝(ai1,
ai2, ai3,… …ain,)
12
二维数组的初步认识
一般地，二维数组的逻辑结构可表示为： Array_2 = (D, R) 其中， D={aij | i=c1, c1+1,…, d1; j= c2, c2+1,…, d2； aij∈Data Object} R={ROW, COL} ROW={< aij,ai,j+1>| c1≤i≤d1 ; c2≤j≤d2-1 ; aij,ai,j+1∈D} COL={< aij,ai+1,j>| c1≤i≤d1-1 ; c2≤j≤d2 ; ai+1,j,aij∈D} 其中：(c1, d1)和(c2,d2)分别为数组下标i, j的一对界偶（即 满足条件c1≤i≤d1，c2≤j≤d2）。 称C1,c2为下界,通常取c1 = c2= 1; 称d1,d2为上界,通常取d1= m，d2= n
将item设计成一维排列是为了使 矩阵中的行数和列数在存储量 容许的情形下可以进行变化；
矩阵类的构造函数
Matrix:: Matrix(float a[], int row, int col) { int j; m=row; n=col; item=new float [m*n]; for (j=0;j<m*n;j++ ) item[j]=a[j]; }; Matrix:: Matrix(Matrix& b) { int j; m=b.m; n=b.n; item=new float [m*n]; for (j=0;j<m*n;j++ ) item[j]=b.item[j]; };

数据结构与算法-第6章

数据结构与算法-第6章

如果 e=(u, v) 是 E(G) 中的一条边，则称 u 与 v
互为邻接点或相邻点;称边e与顶点u,v关联;
如果 a=<u, v> 是 E(G) 中的一条弧，则称u邻接到v
或v邻接于u,也称弧a与顶点u,v关联.
9
6.1 图的基本概念
顶点的度（与树中结点的度不同）: –无向图中，顶点的度是与每个顶点关联的边数, 记作TD(v) –有向图中，顶点的度分成入度与出度 •入度：以该顶点为终头的弧的数目,记为ID(v) •出度：以该顶点为始点的弧的数目,记为OD(v) 一个顶点的度等于该顶点的入度与出度之和,即 TD(v)=OD(v)+ID(v)
20
带权图的邻接矩阵
wij 若(vi，vj)∈E或<vi，vj>∈E
A[i][j]= ∞ 其它 0 i=j
21
用邻接矩阵表示的图的类的定义
class AdjMatrix { int n； int matrix[MaxSize][ MaxSize]； public: AdjMatrix(int m) { n=m； } }; // AdjMatrix class AdjMatrix { const int INFINITE=∞； int n； float matrix[MaxSize][MaxSize]； public: AdjMatrix(int m) { n=m；} }; // AdjMatrix // 非带权图 // 顶点的个数 // 邻接矩阵
回路——第一个顶点和最后一个顶点相同的路径。
简单回路——除了第一个顶点和最后一个顶点外，其
余顶点不重复出现的回路。
11
6.1 图的基本概念
V0V1V3V2
V0V1V3V0V1V2

数据结构_第六章_图_练习题与答案详细解析(精华版)

数据结构_第六章_图_练习题与答案详细解析(精华版)

图1. 填空题⑴ 设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。

【解答】0，n(n-1)/2，0，n(n-1)【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。

⑵ 任何连通图的连通分量只有一个，即是（）。

【解答】其自身⑶ 图的存储结构主要有两种，分别是（）和（）。

【解答】邻接矩阵，邻接表【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。

⑷ 已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。

【解答】Ｏ(n+e)【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。

⑸ 已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。

【解答】求第j列的所有元素之和⑹ 有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。

【解答】出度⑺ 图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。

【解答】前序，栈，层序，队列⑻ 对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal 算法求最小生成树的时间复杂度为（）。

【解答】Ｏ(n2)，Ｏ(elog2e)【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。

⑼ 如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。

【解答】回路⑽ 在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi, vj, vk的相对次序为（）。

【解答】vi, vj, vk【分析】对由顶点vi, vj, vk组成的图进行拓扑排序。

数据结构 第六章 树和二叉树

数据结构 第六章 树和二叉树

F
G
H
M
I
J
结点F，G为堂兄弟 结点A是结点F，G的祖先
5
树的基本操作
树的应用很广，应用不同基本操作也不同。下面列举了树的一些基本操作： 1）InitTree(&T); 2）DestroyTree(&T); 3）CreateTree(&T, definition); 4）ClearTree(&T); 5）TreeEmpty(T); 6）TreeDepth(T); 7） Root(T); 8） Value(T, &cur_e); 9） Assign(T, cur_e, value); 10）Paret(T, cur_e); 11）LeftChild(T, cur_e); 12）RightSibling(T, cur_e); 13）InsertChild(&T, &p, i, c); 14）DeleteChild(&T,&p, i); 15）TraverseTree(T, Visit( ));
1
2 4 8 9 10 5 11 12 6 13 14 3 7 15 4 6 2
1
3
5 7
证明：设二叉树中度为1的结点个数为n1 根据二叉树的定义可知，该二叉树的结点数n=n0+n1+n2
又因为在二叉树中，度为0的结点没有孩子，度为1的结点有1 个孩子，度为2的结点有2个结孩子，故该二叉树的孩子结点 数为 n0*0+n1*1+n2*2(分支数） 而一棵二叉树中，除根结点外所有都为孩子结点，故该二叉 树的结点数应为孩子结点数加1即：n=n0*0+n1*1+n2*2+1
文件夹1
文件夹n

数据结构课后习题及解析第六章

数据结构课后习题及解析第六章

第六章习题1．试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。

2．对题1所得各种形态的二叉树，分别写出前序、中序和后序遍历的序列。

3．已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，……，n k个度为k的结点，则该树中有多少个叶子结点并证明之。

4.假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请画出该二叉树。

5．已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个6．给出满足下列条件的所有二叉树：①前序和后序相同②中序和后序相同③前序和后序相同$7．n个结点的K叉树，若用具有k个child域的等长链结点存储树的一个结点，则空的Child域有多少个8．画出与下列已知序列对应的树Ｔ：树的先根次序访问序列为GFKDAIEBCHJ；树的后根次序访问序列为DIAEKFCJHBG。

9．假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为：，，，，，，，请为这8个字母设计哈夫曼编码。

10．已知二叉树采用二叉链表存放,要求返回二叉树T的后序序列中的第一个结点指针,是否可不用递归且不用栈来完成请简述原因.11. 画出和下列树对应的二叉树：!12．已知二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目。

13．编写递归算法：对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。

14．分别写函数完成：在先序线索二叉树T中，查找给定结点*p在先序序列中的后继。

在后序线索二叉树T中，查找给定结点*p在后序序列中的前驱。

15．分别写出算法，实现在中序线索二叉树中查找给定结点*p在中序序列中的前驱与后继。

16．编写算法，对一棵以孩子-兄弟链表表示的树统计其叶子的个数。

17．对以孩子-兄弟链表表示的树编写计算树的深度的算法。

18．已知二叉树按照二叉链表方式存储，利用栈的基本操作写出后序遍历非递归的算法。

19．设二叉树按二叉链表存放，写算法判别一棵二叉树是否是一棵正则二叉树。

数据结构 第6章 排序

数据结构 第6章 排序

判断某序列是否符合堆定义
只要将序列依次排成一棵完全二叉树，所有结点的 值都不大于（或不小于）其左右子树结点的值，那么该 序列就符合堆的定义。 例：序列：102、87、100、79、82、62、84
10 2 87 10 0 82
故： 此序列符 合堆定义。
84
79
62
若n个元素的排序码k1，k2，k3，…，kn满足堆，且让结点 按1、2、3、…、n顺序编号，根据完全二叉树的性质（若i为 根结点，则左孩子为2i，右孩子为2i+1）可知，堆排序实际与 一棵完全二叉树有关。若将排序码初始序列组成一棵完全二 叉树，则堆排序可以包含建立初始堆（使排序码变成能符合 堆的定义的完全二叉树）和利用堆进行排序两个阶段。
14
17
25 )
20
9
(3
14
17
20
25 )
9
第五次插入
(3
9
14
17
20
25)
图 9-1 直接插入排序示例
注意:
排正序时，要插入的元素先和有序表中最后 一个元素进行比较，即从后往前；排逆序时， 则刚相反，得从前往后进行比较。 当n很小时，直接插入排序的效率较高，时间 复杂度为o(n^2)。 正序时比较次数最少为n-1； 逆序时最大为(n+2)*(n-1)/2； 两者的平均值约为(n^2)/4。
例如，n=6，数组R的六个排序码分别为：17，3，25，14，20， 9。下面用图9-3给出冒泡排序算法的执行过程。
0 1 2 3 4 5
初始状态
（17
3
25
14
20
9)
第一趟排序
3
(17
9
25

数据结构第6章树和二叉树

数据结构第6章树和二叉树

数据结构第6章树和⼆叉树第六章树和⼆叉树⼀、选择题1．已知⼀算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为( )A．-A+B*C/DE B. -A+B*CD/E C．-+*ABC/DE D. -+A*BC/DE2.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶⼦数为（）A．5 B．6 C．7 D．83.在下述结论中，正确的是（）①只有⼀个结点的⼆叉树的度为0; ②⼆叉树的度为2；③⼆叉树的左右⼦树可任意交换;④深度为K的完全⼆叉树的结点个数⼩于或等于深度相同的满⼆叉树。

A．①②③ B．②③④ C．②④ D．①④4.设森林F对应的⼆叉树为B，它有m个结点，B的根为p,p的右⼦树结点个数为n,森林F中第⼀棵树的结点个数是（）A．m-n B．m-n-1 C．n+1 D．条件不⾜，⽆法确定5．⼀棵完全⼆叉树上有1001个结点，其中叶⼦结点的个数是（）A．250 B． 254 C．500 D．5016.设给定权值总数有n 个，其哈夫曼树的结点总数为( )A．不确定 B．2n C．2n+1 D．2n-17.有关⼆叉树下列说法正确的是（）A．⼆叉树的度为2 B．⼀棵⼆叉树的度可以⼩于2 C．⼆叉树中⾄少有⼀个结点的度为2 D．⼆叉树中任何⼀个结点的度都为2 8．⼆叉树的第I层上最多含有结点数为（）A．2I B． 2I-1-1 C． 2I-1 D．2I -19.⼀个具有1025个结点的⼆叉树的⾼h为（）A．11 B．10 C．11⾄1025之间 D．10⾄1024之间10．⼀棵⼆叉树⾼度为h,所有结点的度或为0，或为2，则这棵⼆叉树最少有( )结点A．2h B．2h-1 C．2h+1 D．h+111.⼀棵具有 n个结点的完全⼆叉树的树⾼度（深度）是（）A．?log2n?+1 B．log2n+1 C．?log2n? D．log2n-112．深度为h的满m叉树的第k层有（）个结点。

数据结构 第六章-树

数据结构 第六章-树

20
A B C D
E
F
G H
I J
A
E F H
G
B C
D A
I J
A
B C F
E H
G
B C D F
E G H I J
21
I
D
J
5. 二叉树转换成树和森林
二叉树转换成树 1. 加线：若p结点是双亲结点的左孩子，则将p的右孩 子，右孩子的右孩子，……沿分支找到的所有右孩 子，都与p的双亲用线连起来 2. 抹线：抹掉原二叉树中双亲与右孩子之间的连线 3. 调整：将结点按层次排列，形成树结构7Fra bibliotek6.3.2
树和森林的存储结构
树的存储结构有很多，既可以采用顺序存储结构， 也可以采用链式存储结构。但无论采用哪种存储方式， 都要求存储结构不仅能存储各结点本身的数据信息，还 要能惟一地反映树中各结点之间的逻辑关系。 双亲表示法 孩子链表表示法 孩子兄弟表示法
8
1.双亲表示法 除根外，树中的每个结点都有惟一的一个双亲结点，所以可以用一 组连续的存储空间存储树中的各结点。一个元素表示树中一个结点， 包含树结点本身的信息及结点的双亲结点的位臵。 A B E F C G H D I
}CTBox;
//树结构 typedef struct {CTBox nodes[MAX_TREE_SIZE]; int n, r; }Ctree
12
3. 孩子-兄弟表示法（树的二叉链表）
孩子兄弟表示法用二叉链表作为树的存储结构。将树中的多支关系用 二叉链表的双支关系体现。 ※ 结点的左指针指向它的第一个孩子结点
//孩子结点结构 typedef struct CTNode
1 2 3 4 5 6
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

第6章树和二叉树6.1 树6.2 二叉树6.3 以结点类为基础的二叉树设计6.4 二叉树类6.5 线索二叉树6.6 哈夫曼树6.7 树与二叉树的转换6.8 树的遍历6.1 树6.1.1 树的定义树是由n(n≥0)个结点组成的有限集合T。

n=0的树称为空树；对n>0的树，有:(1)仅有一个特殊的结点称为根结点，根结点没有前驱结点；(2)当n>1时，除根结点外其余的结点分为m(m>0)个互不相交的有限集合T1,T2，…，Tm，其中每个集合T i本身又是一棵结构和树类似的子树。

注意：树的定义具有递归性，即“树中还有树”。

树的示例：只有根结点的树一般的树若干术语根——即根结点(没有前驱)叶子结点——即终端结点(没有后继)森林——指m棵不相交的树的集合(例如删除A后的子树个数)有序树——结点各子树从左至右有序，不能互换（左为第一）无序树——结点各子树可互换位置。

双亲结点——即上层的那个结点(直接前驱)孩子结点——即下层结点的子树的根(直接后继)兄弟结点——同一双亲下的同层结点（孩子之间互称兄弟）祖先结点——即从根到该结点所经分支的所有结点子孙结点——即以该结点为根的子树中的所有结点结点——即树的数据元素结点的度——结点挂接的子树数（有几个直接后继就是几度，亦称“次数”）结点的层次——从根到该结点的层数（根结点算第0层）终端结点——即度为0的结点，即叶子分支结点——即度不为0的结点（也称为内部结点）树的度——所有结点度中的最大值（Max{各结点的度}）树的深度——指所有结点中最大的层数（Max{各结点的层次}）(或高度)问：右上图中的结点数＝13 ；树的度＝3 ；树的深度＝36.1.2 树的抽象数据类型数据集合：树的结点集合，每个结点由数据元素和构造数据元素之间关系的指针组成。

操作集合：（1）双亲结点parent() ：把当前结点的双亲结点置为当前结点。

（2）左孩子结点leftChild()：把当前结点的左孩子结点置为当前结点。

（3）右兄弟结点rightSibling() ：把当前结点的右兄弟结点置为当前结点。

（4）遍历树traverse(vs) ：按某种遍历方法访问树的每个结点，且每个结点只访问一次。

6.1.3 树的存储结构1.双亲表示法2.孩子表示法3.双亲孩子表示法4.孩子兄弟表示法1 双亲表示法双亲表示法就是用指针表示出每个结点的双亲结点。

对于使用仿真指针的双亲表示法来说，每个结点应有两个域，一个是数据元素域，另一个是指示其双亲结点在数组中下标序号的仿真指针域。

树及其使用仿真指针的双亲表示法2 孩子表示法孩子表示法就是用指针表示出每个结点的孩子结点。

常规指针的孩子表示法3 双亲孩子表示法双亲孩子表示法就是用指针既表示出每个结点的双亲结点，也表示出每个结点的孩子结点。

4 孩子兄弟表示法孩子兄弟表示法就是用指针既表示出每个结点的孩子结点，也表示出每个结点的兄弟结点。

6.2 二叉树6.2.1 二叉树的定义6.2.2 二叉树抽象数据类型6.2.2 二叉树的性质6.2.3 二叉树的存储结构6.2.1二叉树的定义二叉树：是n（n≥0）个结点的有限集合。

n=0的树称为空二叉树；n>0的二叉树由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。

逻辑结构：一对二（1:2）基本特征:①每个结点最多只有两棵子树（不存在度大于2的结点）；②左子树和右子树次序不能颠倒。

基本形态：问：具有3个结点的二叉树可能有几种不同形态？注意：二叉树与树和有序树的区别二叉树与度数不超过2的树不同，与度数不超过2的有序树也不同。

在有序树中，虽然一个结点的儿子之间是有左右次序的，但若该结点只有一个儿子时，就无须区分其左右次序。

而在二叉树中，即使是一个儿子也有左右之分。

例如图中(a)和(b)是两棵不同的二叉树。

虽然它们与图c中的普通树(作为无序树或有序树)很相似，但它们却不能等同于这棵普通的树。

若将这3棵树均看作是有序树，则它们就是相同的了。

尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形。

满二叉树在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的二叉树称为满二叉树。

完全二叉树如果一棵深度为k，有n个结点的二叉树中各结点能够与深度为k的顺序编号的满二叉树从1到n标号的结点相对应的二叉树称为完全二叉树。

特点:(1)所有的叶结点都出现在第k层或k－1层。

(2)若任一结点，如果其右子树的最大层次为i，则其左子树的最大层次为i或i＋1。

满二叉树与完全二叉树的区别满二叉树是叶子一个也不少的树，而完全二叉树虽然前k-1层是满的，但最底层却允许在右边缺少连续若干个结点。

满二叉树是完全二叉树的一个特例。

为何要研究这两种特殊形式？因为它们在顺序存储方式下可以复原。

6.2.2 二叉树抽象数据类型数据集合：二叉树的结点集合，每个结点由数据元素和构造数据元素之间关系的指针组成。

操作集合：（1）双亲结点parent()：（2）左孩子结点leftChild()（3）右孩子结点rightChild()（4）左插入结点insertLeftNode(x)（5）右插入结点insertRightNode(x)（6）删除左子树deleteLeftTree()（7）删除右子树deleteRightTree()（8）遍历二叉树traverse(vs)6.2.3二叉树的性质讨论1：第i层的结点数最多是多少？(i≥0) 2i个性质1:在一棵非空二叉树的第i层上至多有2i个结点（i≥0）。

讨论2：深度为k(k≥-1)的二叉树，最多有多少个结点？2k+1-1个性质2:深度为k的二叉树至多有2k+1-1个结点(k≥-1)。

1+2+22+23+24+ (2)讨论3：二叉树的叶子数和度为2的结点数之间有关系吗？性质3: 对于任何一棵非空的二叉树，若度为2的结点数有n2个，则叶子数（n0）必定为n2＋1 （即n0=n2+1）叶子数＝2度结点数＋1对于两种特殊形式的二叉树（满二叉树和完全二叉树），还特别具备以下2个性质：性质4: 具有n个结点的完全二叉树的深度k必为⎡log2(n+1)⎤-1(假定k为0时表示此二叉树仅有根结点）证明：根据性质2，深度为k的二叉树最多只有2k+1-1个结点，且完全二叉树的定义是与同深度的满二叉树前面编号相同，即它的总结点数n位于k层和k-1层满二叉树容量之间，即2(k-1)+1-1<n≤2k+1-1，移项，有2k<n+1≤2k+1对不等式求对数，有k<log2(n+1)≤k+1 即k-1<log2(n+1)-1≤k 因为k是整数，所以k=⎡log2(n+1)⎤-1性质5:对于一棵有n个结点的完全二叉树的结点按照从上至下和从左至右的顺序对所有结点从0开始顺序编号,则对于序号为i的结点,有：(1)如果i=0，则结点i无双亲，是二叉树的根；如果i>0，则其双亲是结点(i-1)/2(“/”表示整除）。

(2)如果2i+1≥n，则结点i为叶子结点，无左孩子；否则，其左孩子是结点2i+1。

(3)如果2i＋2≥n，则结点i无右孩子；否则，其右孩子是结点2i＋2。

6.2.4 二叉树的存储结构二叉树的存储结构主要有三种：顺序存储结构、链式存储结构和仿真指针存储结构。

1. 二叉树的顺序存储结构完全二叉树的结点可按从上至下和从左至右的次序存储在一维数组中，其结点之间的关系可由公式计算得到，这就是二叉树的顺序存储结构。

下图在数组中的存储结构为：问题：对于一般的二叉树如何存储呢？显然不能直接使用二叉树的顺序存储结构。

我们可以采取下面这种办法：首先在非完全二叉树中增添一些并不存在的空结点使之变成完全二叉树的形态，然后再用顺序存储结构存储。

(a)一般二叉树(b)完全二叉树（c)在数组中的存储形式一般二叉树的顺序存储结构2. 二叉树的链式存储结构二叉树的链式存储结构是用指针建立二叉树中结点之间的关系。

二叉树最常用的的链式存储结构是二叉链。

二叉链存储结构的每个结点包含三个域，分别是数据域data、左孩子指针域leftChild和右孩子指针域rightChild。

二叉链存储结构中每个结点的图示结构为：二叉链存储结构的二叉树也有不带头结点和带头结点两种。

带头结点的二叉链存储结构的二叉树见图7.7(b)，不带头结点的二叉链存储结构的二叉树如图7.7（a）所示。

（a）不带头结点的二叉树（b）带头结点的二叉树3. 二叉树的仿真指针存储结构二叉树的仿真指针存储结构是用数组存储二叉树中的结点，数组中每个结点除数据元素域外，再增加仿真指针域用于仿真常规指针建立二叉树中结点之间的关系。

1.根据右图的树回答问题：（1）这棵树的根结点是什么？（2）这棵树的叶子结点是什么？（3）结点C的度是多少？（4）这棵树的度是多少？（5）这棵树的深度是多少？（6）结点C的孩子结点是哪些？（7）结点C的双亲结点是谁？2.若一棵度为4的树中度为1、2、3、4的结点个数分别为4、3、2、2，则该树叶子结点的个数是多少？总结点个数是多少？分析：结点总数n=n0+n1+n2+n3+n4，除了根结点外，每个结点都对应一个分支，所以总分支数为n-1，而度为i的结点的分支数为i，所以有n-1=1×n1+2×n2+3×n3+4×n4。

综合两式得：n0+n1+n2+n3+n4-1= 1×n1+2×n2+3×n3+4×n4n0= n2+ 2n3+ 3n4+1=3+4+6+1=14总结点个数为14+4+3+2+2=253.一棵高度为h的完全二叉树至少有2h 结点。

4.一棵高度为h的完全二叉树至多有2h+1-1结点。

5.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为2h+1 。

6.具有n个结点的二叉树采用二叉链存储结构，共有n+1 个空指针域。

分析：对于二叉链存储结构，n个结点的二叉树有2n个指针域，除根结点外，每个结点都由一个指针所指向，则共有n-1个非空指针域，空指针域个数=2n-(n-1)=n+1。

7.n个结点的二叉树中如果有m个叶子，则一定有n-2m+1 个度为1的结点，m-1 个度为2的结点。

分析：由二叉树性质知度为2的结点个数为叶子结点数-1，则有m-1个度为2的结点。

又因为总结点数为n，则度为1的结点数为n-(m-1)-m=n-2m+1。

6.3 以结点类为基础的二叉树设计6.3.1 二叉树结点类class BiTreeNode{private BiTreeNode leftChild;private BiTreeNode rightChild;private Object data;public BiTreeNode(){leftChild = null;rightChild = null;}public BiTreeNode(Object item, BiTreeNode left, BiTreeNode right) {data = item;leftChild = left;rightChild = right;}public BiTreeNode getLeft(){return leftChild;}public BiTreeNode getRight(){return rightChild;}public Object getData(){return data;}}6.3.2 二叉树的遍历1、遍历定义——指按照某种顺序访问二叉树中的每个结点，使每个结点被访问一次且仅被访问一次。