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

数据结构第6章2

  • 格式：ppt
  • 大小：454.50 KB
  • 文档页数：78

下载文档原格式

  / 78

合集下载

数据结构-6 树和二叉树

数据结构-6 树和二叉树

第六章树和二叉树一．选择题1. 以下说法错误的是。

A.树形结构的特点是一个结点可以有多个直接前趋B.线性结构中的一个结点至多只有一个直接后继C.树形结构可以表达(组织)更复杂的数据D.树(及一切树形结构)是一种"分支层次"结构2. 如图6-2所示的4 棵二叉树中，不是完全二叉树。

图6-2 4 棵二叉树3. 在线索化二叉树中，t 所指结点没有左子树的充要条件是。

A. t->left == NULLB. t->ltag==1C. t->ltag==1 且t->left==NULL D .以上都不对4. 以下说法错误的是。

A.二叉树可以是空集B.二叉树的任一结点最多有两棵子树C.二叉树不是一种树D.二叉树中任一结点的两棵子树有次序之分5. 以下说法错误的是。

A.完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达B.在三叉链表上，二叉树的求双亲运算很容易实现C.在二叉链表上，求根，求左、右孩子等很容易实现D.在二叉链表上，求双亲运算的时间性能很好6. 如图6-3所示的4 棵二叉树，是平衡二叉树。

图6-3 4 棵二叉树7. 如图6-4所示二叉树的中序遍历序列是。

A. abcdgefB. dfebagcC. dbaefcgD. defbagc图6-4 1 棵二叉树8. 已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是。

A. acbedB. decabC. deabcD. cedba9. 如果T2 是由有序树T 转换而来的二叉树，那么T 中结点的前序就是T2 中结点的。

A. 前序B.中序C. 后序D. 层次序10. 某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是。

A. bdgcefhaB. gdbecfhaC. bdgaechfD. gdbehfca11. 将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的双亲结点编号为。

数据结构(c语言)第6章二叉树课练答案(含完整实验程序刘玉保留

数据结构(c语言)第6章二叉树课练答案(含完整实验程序刘玉保留

第6章树和二叉树自测卷解答姓名班级一、下面是有关二叉树的叙述，请判断正误（每小题1分，共10分）（√）1. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。

（×）2.二叉树中每个结点的两棵子树的高度差等于1。

（√）3.二叉树中每个结点的两棵子树是有序的。

（×）4.二叉树中每个结点有两棵非空子树或有两棵空子树。

（×）5.二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。

（应当是二叉排序树的特点）（×）6.二叉树中所有结点个数是2k-1-1，其中k是树的深度。

（应2i-1）（×）7.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。

（×）8.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。

（应2i-1）（√）9.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。

（正确。

用二叉链表存储包含n个结点的二叉树，结点共有2n个链域。

由于二叉树中，除根结点外，每一个结点有且仅有一个双亲，所以只有n-1个结点的链域存放指向非空子女结点的指针，还有n+1个空指针。

）即有后继链接的指针仅n-1个。

（√）10. 〖01年计算机系研题〗具有12个结点的完全二叉树有5个度为2的结点。

最快方法：用叶子数＝[n/2]＝6，再求n2=n0-1=5二、填空（每空1分，共15分）1．由３个结点所构成的二叉树有5种形态。

2. 【计算机研2000】一棵深度为6的满二叉树有n1+n2=0+ n2= n0-1=31 个分支结点和26-1 =32个叶子。

注：满二叉树没有度为1的结点，所以分支结点数就是二度结点数。

3．一棵具有２５７个结点的完全二叉树，它的深度为9。

（注：用⎣ log2(n) ⎦+1= ⎣ 8.xx ⎦+1=94.【全国专升本统考题】设一棵完全二叉树有700个结点，则共有350个叶子结点。

数据结构(朱战立)章 (6)

数据结构(朱战立)章 (6)
30
Move Disk 2 from Peg A to Peg C Move Disk 1 from Peg B to Peg C Move Disk 3 from Peg A to Peg B Move Disk 1 from Peg C to Peg A Move Disk 2 from Peg C to Peg B Move Disk 1 from Peg A to Peg B Move Disk 4 from Peg A to Peg C Move Disk 1 from Peg B to Peg C Move Disk 2 from Peg B to Peg A Move Disk 1 from Peg C to Peg A
" from peg "， fromPeg， " to peg
/*把n-1个圆盘从auxPeg借助fromPeg移至
29
towers(n-1，auxPeg，toPeg，fromPeg); }设计一个测试主函数如下： ＃include <stdio.h> void main(void) {
Towers(4， 'A'， 'C'， 'B'); }程序运to Peg B
26
Move Disk i from Peg X to Peg Y 这样， 汉
诺塔问题的递归算法可设计如下： void towers(int n，
char fromPeg， char toPeg， char auxPeg)
{
if(n＝＝1)
/*递归出口*/
{
printf("%s%c%s%c＼n"， "move disk
并不是每个问题都适宜于用递归算法求解。 适宜于用递归 算法求解的问题的充分必要条件是：

《数据结构(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解释：广度优先遍历通常借助队列来实现算法，深度优先遍历通常借助栈来实现算法。

数据结构-C语言描述(第三版)(陈慧南)章 (6)

数据结构-C语言描述(第三版)(陈慧南)章 (6)

第6章 树 例如，设有序表为(21, 25, 28, 33, 36, 43)，若要在表中 查找元素36，通常的做法是从表中第一个元素开始，将待查元素 与表中元素逐一比较进行查找，直到找到36为止。粗略地说，如 果表中每个元素的查找概率是相等的，则平均起来，成功查找一 个元素需要将该元素与表中一半元素作比较。如果将表中元素组 成图6－3所示的树形结构，情况就大为改观。我们可以从根结点 起，将各结点与待查元素比较，在查找成功的情况下，所需的最 多的比较次数是从根到待查元素的路径上遇到的结点数目。当表 的长度n很大时，使用图6－3所示的树形结构组织表中数据，可 以很大程度地减少查找所需的时间。为了查找36，我们可以让36 与根结点元素28比较，36比28大，接着查右子树，查找成功。显 然，采用树形结构能节省查找时间。
第6章 树
E
E
A
F
B
G
CD
LJ
M
N
T1
X
YZ
U T2
B
F
A
DC
G
JL
T3 N
M
(a)
(b)
图6－2 树的例子
(a) 树T1和T2组成森林；(b) 树T3
第6章 树
6.2 二 叉 树
二叉树是非常重要的树形数据结构。很多从实际问题中抽 象出来的数据都是二叉树形的，而且许多算法如果采用二叉树 形式解决则非常方便和高效。此外，以后我们将看到一般的树 或森林都可通过一个简单的转换得到与之相应的二叉树，从而 为树和森林的存储及运算的实现提供了有效方法。
第6章 树
图6－1描述了欧洲部分语言的谱系关系，它是一个后裔图， 图中使用的描述树形结构数据的形式为倒置的树形表示法。在 前几章中，我们学习了多种线性数据结构，但是一般来讲，这 些数据结构不适合表示如图6－1所示的层次结构的数据。为了 表示这类层次结构的数据，我们采用树形数据结构。在本章中 我们将学习多种不同特性的树形数据结构，如一般树、二叉树、 穿线二叉树、堆和哈夫曼树等。

数据结构第六章题目讲解

数据结构第六章题目讲解

数据结构第六章题⽬讲解02⼀选择题：1、以下说法错误的是①树形结构的特点是⼀个结点可以有多个直接前趋②线性结构中的⼀个结点⾄多只有⼀个直接后继③树形结构可以表达(组织)更复杂的数据④树(及⼀切树形结构)是⼀种"分⽀层次"结构⑤任何只含⼀个结点的集合是⼀棵树2．深度为6的⼆叉树最多有( )个结点①64 ②63 ③32 ④313 下列说法中正确的是①任何⼀棵⼆叉树中⾄少有⼀个结点的度为2②任何⼀棵⼆叉树中每个结点的度都为2 ⼆叉树可空③任何⼀棵⼆叉树中的度肯定等于2 ④任何⼀棵⼆叉树中的度可以⼩于24 设森林T中有4棵树，第⼀、⼆、三、四棵树的结点个数分别是n1,n2,n3,n4,那么当把森林T转换成⼀棵⼆叉树后，且根结点的右⼦树上有（）个结点。

①n1-1 ②n1③n1+n2+n3④n2+n3+n4⼆．名词解释：1 结点的度 3。

叶⼦ 4。

分⽀点 5。

树的度三填空题⼆叉树第i(i>=1)层上⾄多有_____个结点。

1、深度为k(k>=1)的⼆叉树⾄多有_____个结点。

2、如果将⼀棵有n个结点的完全⼆叉树按层编号，则对任⼀编号为i(1<=i<=n)的结点X有：若i=1,则结点X是_ ____；若i〉1,则X的双亲PARENT(X)的编号为__ ____。

若2i>n，则结点X⽆_ _____且⽆_ _____；否则，X的左孩⼦LCHILD(X)的编号为____。

若2i+1>n，则结点X⽆__ ____；否则，X的右孩⼦RCHILD(X)的编号为_____。

4．以下程序段采⽤先根遍历⽅法求⼆叉树的叶⼦数，请在横线处填充适当的语句。

Void countleaf(bitreptr t,int *count)/*根指针为t，假定叶⼦数count的初值为0*/ {if(t!=NULL){if((t->lchild==NULL)&&(t->rchild==NULL))__ __;countleaf(t->lchild,&count);countleaf(t->rchild,&count);}}5 先根遍历树和先根遍历与该树对应的⼆叉树，其结果_____。

数据结构第六章二叉树的应用教案

数据结构第六章二叉树的应用教案

6.3 哈夫曼树
• • 最优树的定义 如何构造最优树
6.3.1 基本术语
路径和路径长度
若在一棵树中存在着一个结点序列 k1,k2,…,kj，使得ki是ki+1的 双亲(1≤i<j)，则称此结点序列是 从k1到kj的路径从k1到kj所经过的 分支数称为这两点之间的路径长度
结点的权和带权路径长度
权 给结点赋上一个有某种意义 的实数，我们称为权。 带权路径长度 从根结点到该结点之间路径 长度与该结点上权的乘积。
23 设 key = 48
T
20 10 T 23 T 25
T T
30
T
40 35 T
bool Find(BTreeNode* T, ElemType& item) if(T==NULL) return false; //查找失败 else { if(item==T->data) { item=T->data; return true; } else if(item<T->data) //向左子树继续查找 return Find(T->left, item); else return Find(T->right, item); } //向右子树继续查找
ri r2i ri r2i 1
(小顶堆)
或
ri r2i ri r2i 1
(大顶堆)
12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49
是小顶堆
12, 36, 27, 65, 40, 14, 98, 81, 73, 55, 49
不是堆
子树上查找；
3）大于根结点的关键字，则继续在右
子树上查找。

云大《数据结构》课程教学课件-第6章 树和二叉树(147P)_OK

云大《数据结构》课程教学课件-第6章 树和二叉树(147P)_OK

^d ^ ^ e ^ 三叉链表
3）二叉链表是二叉树最常用的存储结构。还有其它链接方 法，采用何种方法，主要取决于所要实施的各种运算频度。
例:若经常要在二叉树中寻找某结点的双亲时，可在每个结 点上再加一个指向其双亲的指针域parent，称为三叉链表。
lchild data parent rchild
2021/8/16
2021/8/16
9
6.2 二 叉 树
6.2.1 二叉树的概念
一、二叉树的定义： 二叉树(Binary Tree)是n(n>=0)个结点的有限集，它或者是 空集(n=0)或者由一个根结点和两棵互不相交的，分别称 为根的左子树和右子树的二叉树组成。 可以看出，二叉树的定义和树的定义一样，均为递归定 义。
A
集合3
集合1
BCD
EF
G
集合2
2021/8/16
3
2、树的表示方法 1）树形图法
A
BCD
EF
G
2）嵌套集合法
3）广义表形式 ( A(B, C(E,F), D(G) )
4）凹入表示法
2021/8/16
A B
D
CG
EF
A B C E DF G
4
3、 树结构的基本术语
1）结点的度(Degree)：为该结点的子树的个数。 2）树的度：为该树中结点的最大度数。
7）路径(Path)：若树中存在一个结点序列k1,k2,…,kj,使得ki是 ki+1的双亲(1<=i<j)，则称该结点序列是从ki到kj一条路径 (Path)
路径长度：路径的长度为j-1,其为该路径所经过的边的数 目。
A
BCD
EF
G

数据结构第06章广义表

数据结构第06章广义表

第6章广义表z6.1 广义表的基本概念z6.2 广义表的存储结构z6.3 广义表的操作算法16.1 广义表的基本概念广义表（列表）的概念-n( ≥0 )个表元素组成的有限序列，记作LS= ( a1, a1, a2, …, a n)LS是表名，a i是表元素，它可以是单个元素(称为原子) ，可以是表(称为子表) 。

n为表的长度。

n= 0 的广义表为空表。

n> 0时，表的第一个表元素称为广义表的表头(head)，除此之外，其它表元素组成的表称为广义表的表尾(tail)。

2广义表举例：（1）A=（）（2）B=（e）（3）C=（a, (b, c, d) )（4）D=（A，B，C）（5）E= (a , E）9任意一个非空广义表，均可分解为表头和表尾。

9对于一个非空广义表，其表头可能是原子，也可能是子表；而表尾一定是子表。

3广义表的基本操作：•结构的创建和销毁InitGList(&L); DestroyGList(&L); CreateGList(&L, S); CopyGList(&T, L);•状态函数GListLength(L); GListDepth(L);GListEmpty(L); GetHead(L); GetTail(L);•插入和删除操作InsertFirst_GL(&L, e);DeleteFirst_GL(&L, &e);•遍历Traverse_GL(L, Visit());66. 2 广义表的存储结构z由于广义表中的元素不是同一类型，因此难以用顺序结构表示，通常采用链接存储方法存储广义表，并称之为广义链表。

z由于广义表中有两种数据元素，原子或子表，因此，需要两种结构的结点：一种是表结点，一种是原子结点。

z下面介绍一种广义表的链式存储结构。

78扩展的线性链表表示法：-子表结点由三个域组成：标志域、表头指针域和指向下一个元素的指针域；-原子结点的三个域为：标志域、值域和指向下一个元素的指针域。

《数据结构——C语言描述》第6章：树

《数据结构——C语言描述》第6章：树
Void paintleaf (Btree root) { if (root!=NULL) { if (root ->Lchild==NULL && root ->Rchild==NULL) printf (root ->data); paintleaf (root ->Lchild); paintleaf (root -遍历左子树； （2）访问根结点； （3）中根遍历右子树。 后根遍历二叉树 （1）后根遍历左子树； （2）后根遍历右子树； （3）访问根结点。
先根遍历: -+a*b–cd/ef 中根遍历: a+b*c–d–e/f 后根遍历: abcd-*+ef/-
typedef struct Node { datatype data; struct Node *Lchild; struct Node *Rchild; } BTnode,*Btree;
满二叉树：一棵深度为k且有2k-1个结 点的二叉树称为满二叉树。 完全二叉树：深度为k，有n个结点的 二叉树当且仅当其每一个结点都与深度 为k的满二叉树中编号从1至n的结点一一 对应时，称为完全二叉树。
1 2 4 8 9 10 5 11 12 6 13 14 3 7 15 4 6 2
1 3 5 7
树的度：树中最大的结点的度数即为 树的度。图6.1中的树的度为3。 结点的层次(level)：从根结点算起， 根为第一层，它的孩子为第二层……。 若某结点在第l层，则其孩子结点就在 第l+1层。图6.1中，结点A的层次为1， 结点M的层次为4。 树的高度(depth)：树中结点的最大层 次数。图6.1中的树的高度为4。 森林(forest)：m(m≥0)棵互不相交的 树的集合。

第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]; };

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

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

所以
n=n1+2×n2+…+m×nm+1 由（1）（2）可知 n0= n2+2×n3+3×n4+…+(m-1) ×nm+1
（2）
八、证明：一棵满 K 叉树上的叶子结点数 n0 和非叶子结点数 n1 之间满足以下关 系:n0=(k-1)n1+1。 证明：n=n0+n1
n=n1k+1 由上述式子可以推出 n0=(k-1)n1+1 十五、请对右图所示的二叉树进行后序线索化，为每个空指针建立相应的前驱或 后继线索。
四十三、编写一递归算法，将二叉树中的所有结点的左、右子树相互交换。 【分析】 依题意，设 t 为一棵用二叉链表存储的二叉树，则交换各结点的左右子树的
运算基于后序遍历实现：交换左子树上各结点的左右子树；交换右子树上各结点 的左右子树；再交换根结点的左右子树。
【算法】 void Exchg(BiTree *t){ BinNode *p; if (t){ Exchg(&((*t)->lchild)); Exchg(&((*t)->rchild)); P=(*t)->lchild; (*t)->lchild=(*t)->rchild; (*t)->rchild=p; } }
(4)编号为 i 的结点的有右兄弟的条件是什么? 其右兄弟的编号是多少? 解：
(1) 层号为 h 的结点数目为 kh-1 (2) 编号为 i 的结点的双亲结点的编号是：|_ (i-2)/k _|+1(不大于(i-2)/k 的最大整数。也就是(i-2)与 k 整除的结果.以下/表示整除。 (3) 编号为 i 的结点的第 j 个孩子结点编号是：k*(i-1)+1+j; (4) 编号为 i 的结点有右兄弟的条件是(i-1)能被 k 整除

数据结构——用C语言描述(第3版)教学课件第6章 树与二叉树

数据结构——用C语言描述(第3版)教学课件第6章 树与二叉树

6.2 二叉树 6.2.1 二叉树的定义与基本操作 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构
6.2.1 二叉树的定义与基本操作 定义：我们把满足以下两个条件的树型结构叫做二 叉树（Binary Tree）： （1）每个结点的度都不大于2； （2）每个结点的孩子结点次序不能任意颠倒。
有序树：在树T中，如果各子树Ti之间是有先后次序的，则称为有序树。 森林：m（m≥0）棵互不相交的树的集合。将一棵非空树的根结点删去，树就变成一 个森林；反之，给森林增加一个统一的根结点，森林就变成一棵树。
同构：对两棵树，通过对结点适当地重命名，就可以使两棵树完全相等（结点对应相 等，对应结点的相关关系也像等），则称这两棵树同构。
二叉树的基本结构由根结点、左子树和右子树组成
如图示
LChild Data RChild
Data
LChild RChild
用L、D、R分别表示遍历左子树、访问根结点、遍 历右子树，那么对二叉树的遍历顺序就可以有：
(1) 访问根，遍历左子树，遍历右子树(记做DLR)。 (2) 访问根，遍历右子树，遍历左子树(记做DRL)。 (3) 遍历左子树，访问根，遍历右子树(记做LDR)。 (4) 遍历左子树，遍历右子树，访问根 (记做LRD)。 (5) 遍历右子树，访问根，遍历左子树 (记做RDL)。 (6) 遍历右子树，遍历左子树，访问根 (记做RLD)。
(8) NextSibling（Tree，x）： 树Tree存在，x是Tree中的某个结点。若x不 是其双亲的最后一个孩子结点，则返回x后面的下一个兄弟结点，否则 返回“空”。
基本操作:
(9) InsertChild（Tree，p，Child）： 树Tree存在，p指向Tree 中某个结点，非空树Child与Tree不相交。将Child插入Tree中， 做p所指向结点的子树。

数据结构与算法-第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

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

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

性质2：深度为 的二叉树至多有 个结点(k≥ 性质 ：深度为k的二叉树至多有2 k 1 个结点 ≥1)
证明：由性质 ，可得深度为k 证明：由性质1，可得深度为 的二叉树最大结点数是
(第i层的最大结点数 ) = ∑ 2 i 1 = 2 k 1 ∑
i =1 i =1
k
k
10
性质3：对任何一棵二叉树 ，如果其终端结点数(即 性质 ：对任何一棵二叉树T，如果其终端结点数 即 叶节点)为 度为2的结点数为 的结点数为n 叶节点 为n0，度为 的结点数为 2，则n0=n2+1 证明： 为二叉树 中度为1的结点数 为二叉树T中度为 证明：n1为二叉树 中度为 的结点数 因为：二叉树中所有结点的度均小于或等于2 因为：二叉树中所有结点的度均小于或等于 所以：其结点总数n=n0+n1+n2 所以：其结点总数 又二叉树中，除根结点外， 又二叉树中，除根结点外，其余结点都只有一个 分支进入； 分支进入； 为分支总数， 设B为分支总数，则n=B+1 为分支总数 又：分支由度为1和度为 的结点射出，∴B=n1+2n2 分支由度为 和度为2的结点射出， 和度为 的结点射出 于是， 于是，n=B+1=n1+2n2+1=n0+n1+n2 ∴n0=n2+1
7
结点A的度：3 结点 的度： 的度 结点B的度：2 结点 的度： 的度 结点M的度：0 结点 的度： 的度 结点A的孩子： ， ， 结点 的孩子：B，C，D 的孩子 结点B的孩子 的孩子： ， 结点 的孩子：E，F 树的度： 树的度：3 E K 结点A的层次： 结点 的层次：1 的层次 结点M的层次 的层次： 结点 的层次：4 L B F A C G H M

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

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

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

《数据结构与算法项目化教程》课件第6章

《数据结构与算法项目化教程》课件第6章

为G=(V, E)，V是顶点A的有限集合，E是边的有限集合，即
V={A|A∈某个数据集合}， E={(A, B)|A, B∈V}
或
E={<A, B> |A, B∈V 且 path(A, B)}
其中，path(A, B)表示从顶点A到B的一条通路。
学习情境６ 图
2．图的类型 (1) 无向图。 无向图(undirected graph)中的边没有方向，每条边用两个 顶点的无序对表示，如(A, B)表示连接顶点A和B之间的一条 边，(A, B)和(B, A)表示同一条边。图6-1是一个无向图，用G 表示无向图，其顶点集合V为
V(G)={A,B,C,D,E} E(G)={<A,B>,<A,D>,<A,E>,<B,C>,<C,B>,<C,D>,<D,B> ,<D,E>,<E,A>}
学习情境６ 图
图6-2 有向图
学习情境６ 图
(3) 自身环的图和多重图。 如图6-3所示，顶点C有一个路径指向自身，这种图称为 带自身环的图；顶点B有两条路径到顶点A，这种图属于多重 图。这些一般不属于数据结构讨论的范畴，本学习情境只讨 论无向图和有向图。 (4) 完全图。 完全图(complete graph)的任一顶点均有路径到其他顶点。 完全图的边数是最大的。无向完全图的边数有n × (n-1)/2，有 向完全图的边数为n × (n-1)。
学习情境６ 图
图6-13 邻接表元素
学习情境６ 图
图6-14 带权无向图的邻接表表示
学习情境６ 图
3．有向图的邻接表表示 以邻接表表示有向图，需要根据边的方向而得到边表， 边表有两种：出边表和入边表。 出边表：第i行单链表存储以顶点vi为起点的所有边<vi, vj>，dest域是该条边的终点vj在顶点表中的下标。 入边表：第i行单链表存储以顶点vi为终点的所有边<vj, vi>，dest域是该条边的起点vj在顶点表中的下标。 有向图的邻接表表示有两种，分别是由出边表构成的邻 接表和由入边表构成的逆邻接表。带权有向图邻接表的出边 表表示如图6-15所示。在有向图的邻接表或逆邻接表中，每 条边只存储一次。

严蔚敏《数据结构》教学笔记第六章 树和二叉树

严蔚敏《数据结构》教学笔记第六章 树和二叉树

来自
转载请注明
严蔚敏数据结构教学笔记
CountLeaf( T->rchild, count); // 统计右子树中叶子结点个数 } }
2、求二叉树的深度(后序遍历) int Depth (BiTree T ) { if ( !T ) depthval = 0; else { depthLeft = Depth( T->lchild ); depthRight= Depth( T->rchild ); depthval = 1 + (depthLeft> depthRight?depthLeft:depthRight); } return depthval; }
五、遍历算法的应用举例: 1、统计二叉树中叶子结点的个数(先序遍历) void CountLeaf (BiTree T, int& count) { if ( T ) { if ((!T->lchild)&& (!T->rchild)) count++; CountLeaf( T->lchild, count); // 统计左子树中叶子结点个数 9
LeftChild(T, cur_e); RightSibling(T, cur_e);
TreeEmpty(T); TreeDepth(T);
TraverseTree(T, Visit()); 插入： InitTree(&T); CreateTree(&T, definition);
Assign(T, cur_e, value); InsertChild(&T, &p, i, c); 1
3、复制二叉树(后序遍历) // 生成一个二叉树的结点 BiTNode *GetTreeNode(TElemType item, BiTNode *lptr , BiTNode *rptr ){ if (!(T = (BiTNode*)malloc(sizeof(BiTNode)))) 10

数据结构第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层有（）个结点。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

• 兄弟(sibling)结点 具有同一双亲的所有结点 • 祖先(ancestor)结点 从根到该结点所经分支上的 所有结点。 • 子孙(descendant)结点 以某一结点 为根的子树中的 任一结点。 • 结点所处层次(level) 根结点的层数为1，其余结点 的层数为双亲结点的层数加1 • 树的深度(depth) 树中结点的最大层数
2013-6-27 8
二叉树 (Binary Tree)
二叉树的定义
一棵二叉树是结点的一个有限集合，该集合 或者为空，或者是由一个根结点加上两棵分别称 为左子树和右子树的、互不相交的二叉树组成。
2013-6-27
二叉树的五种不同形态
9
二叉树的性质
性质1 若二叉树的层次从1开始, 则在二叉树的 第 i 层最多有 2i-1 个结点。(i 0) 证明：i = 1 时，有2i-1 = 20 =1，成立
33
• 2、求二叉树的深度(后序遍历) • int Depth (BiTree T ) • • • • • • • • • { if ( !T ) depthval = 0; else { depthLeft = Depth( T->lchild ); depthRight= Depth( T->rchild ); depthval = 1 + (depthLeft>depthRight?depthLeft:depthRight);
6.5 线索二叉树 • 何谓线索二叉树？ • 遍历二叉树的结果是，求得结点的一个线性 序列。 • 指向该线性序列中的“前驱”和“后继”的 指针，称作“线索” • 包含“线索”的存储结构，称作“线索链 表”； • 与其相应的二叉树，称作“线索二叉树”
有序树 无序树 森林

2013-6-27
子树的次序不能互换 子树的次序可以互换 互不相交的树的集合
7
树的基本操作
1、初始化 2、求指定结点所在树的根结点 3、求指定结点的双亲结点 4、求指定结点的某一孩子结点 5、求指定结点的最右边兄弟结点 6、将一棵树插入到另一树的指定结点下作为它 的子树 7、删除指定结点的某一子树 8、树的遍历
至多为：
20 + 21 + 22 + 23 + … + 2k-1 = 2k － 1
2013-6-27 11
性质3 对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2, 则有 n0＝n2＋1
证明： 1、结点总数为度为0的结点加上度为1的结点再加上度 为2的结点： n = n0 + n1 + n2 2、另一方面，二叉树中一度结点有一个孩子，二 度结 点有二个孩子，根结点不是任何结点的孩子，因此， 结点总数为： n = n1 + 2n2 + 1 3、两式相减，得到：
2013-6-27
28
中序遍历
中序遍历二叉树算法的框架是： • 若二叉树为空，则空操作； • 否则 – 中序遍历左子树 (L)； – 访问根结点 (V)； – 中序遍历右子树 (R)。 遍历结果 a+b*c-d-e/f
2013-6-27
表达式语法树29
中序遍历算法
INORDER(bitree *cnt) { if (cnt) { INORDER(t->lch); printf(“\t%c\n”,t->data);
• • • • • • • • •
2013-6-27
遍历算法的应用举例: 1、统计二叉树中叶子结点的个数(先序遍历) void CountLeaf (BiTree T, int& count) { if ( T ) { if ((!T->lchild)&& (!T->rchild)) count++; CountLeaf( T->lchild, count); // 统计左子树中 叶子结点个数 • CountLeaf( T->rchild, count); // 统计右子树中 叶子结点个数 • } • }
lchild
data
rchild
parent
其中，data、lchild以及rchild三个域的意义同二叉 链表结构；parent域为指向该结点双亲结点的指针。 既便于查找孩子结点，又便于查找双亲结点； 相对于二叉链表存储结构而言，它增加了空间开销。
2013-6-27
24
链表表示
2013-6-27
单支树
21
• •
2．链式存储结构 用链表来表示一棵二叉树，即用链来指示着元素的 逻辑关系。通常有两种形式。 • （1）二叉链表存储 • 链表中每个结点由三个域组成，除了数据域外，还有 两个指针域，分别用来给出该结点左孩子和右孩子所 在的链结点的存储地址。当左孩子或右孩子不存在时， 相应指针域值为空（用符号∧或NULL表示）。 •
Ø Ø F G
A B
2013-6-27
C
D E
Ø Ø Ø Ø F
G
20
由于一般二叉树必须仿照完全二叉树那样存 储，可能会浪费很多存储空间，单支树就是 一个极端情况。
•
A B C D
A
B C
D
A ∧B ∧∧∧C ∧∧∧∧∧∧∧D
• (a) 一棵右单支二叉树 (b) 改造后的右单支树对应的完全二叉树
2013-6-27
3
凹入表表示
a
b d e
i j f c g h
2013-6-27 4
嵌套集合表示
a
b
d i
e
j f g
c
h
广义表表示
(a ( b ( d, e ( i, j ),f), c ( g, h ) ) )
2013-6-27 5
1 2
4
3
4
• 结点(node)： • 结点的度(degree)： • 树的度(degree)： • 分支(branch)结点： • 叶(leaf)结点： • 孩子(child)结点： 2013-6-27 • 双亲(parent)结点： 数据元素 + 若干指向子树的分支 结点的子树个数 树中所有结点的度的最大值 度不为0的结点 度为0的结点 某结点子树的根结点 6 某个结点是其子树之根的双亲
2013-6-27 27
•
D 1 L 2 R 3
• 若以D、L、R分别表示访问根结点、遍历根结点的左子 树、遍历根结点的右子树，则二叉树的遍历方式有六 种：DLR、LDR、LRD、DRL、RDL和RLD。 • 限定先左后右，则有三种方式，即DLR（称为先序遍 历）、LDR（称为中序遍历）和LRD（称为后序遍历）。
• } • return depthval;
• }
2013-6-27 34
• 3、建立二叉树的存储结构
• 按给定的先序序列建立二叉链表 • Status CreateBiTree(BiTree &T) { • // 按先序次序输入二叉树中结点的值（一个字符）， 空格字符 表示空树，构造二叉链表表示的二叉树T。 • scanf(&ch); • if (ch==' ') T = NULL; • else { • if (!(T = (BiTNode*)malloc(sizeof(BiTNode)))) • exit(OVERFLOW); • T->data = ch; // 生成根结点 • CreateBiTree(T->lchild); // 构造左子树 • CreateBiTree(T->rchild); // 构造右子树 • } 2013-6-27 return OK; } // CreateBiTree 35 •
2013-6-27
22
• 二叉树的链式存储表示
• • • •
typedef struct BiTNode { TElemType data; struct BiTNode *lchild, *rchild; // 左右孩子指针 • } BiTNode, *BiTree;
2013-6-27
23
• （2）三叉链表存储 • 每个结点由四个域组成，具体结构为： •
2013-6-27
n0 = n2 + 1
12
定义1 满二叉树(Full Binary Tree) 一棵深度为k 且有2k-1个结点的二叉树。 定义2 完全二叉树(Complete Binary Tree) 若设二叉树的高度为h，则共有h层。除 第h层外，其它各层(1h-1)的结点数都达到 最大个数，第h层从右向左连续缺若干结点， 这就是完全二叉树。
2013-6-27 13
1 2 4 5 3 6 7
满二叉树
1
2 3 2
1
3 2
1
3 6 7
4
5
6
4
5
7
(a)完全二叉树
2013-6-27
(b)非完全二叉树
( c)非完全二叉树
14
性质4 具有n个结点的完全二叉树的高度
为 log2n +1
证明：设完全二叉树的高度为h，则有
2h-1 - 1 < n 2h - 1 2h-1 <= n < 2h

若i == 1, 则 i 无双亲 若i > 1, 则 i 的双亲为i /2

若2*i <= n, 则 i 的左子女为2*i；否则，i无左子女，必 若2*i+1 <= n, 则 i 的右子女为2*i+1，否则，i无右子
定是页结点，二叉树中i> n/2 的结点必定是页结点 女

2013-6-27 16
25
二叉树链表表示的示例
2013-6-27 26

6.3 遍历二叉树和线索二叉树