【数据结构】——树和二叉树的相关习题

这篇具有很好参考价值的文章主要介绍了【数据结构】——树和二叉树的相关习题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、选择填空判断题

题1

1、设高度为h的二叉树上只有度为0和度为2的结点,则该二叉树中所包含的结点数至少为(),最多为()。
A、h ;2h-1
B、2h-1 ; 2h-1
C、2h+1; 2h-1-1
D、h+1;2h-1

解析:(B)
最少的情况下,除了根结点该层为1个结点以外,其余h-1层都有2个结点,得2(h-1),即2(h-1)+1=2h-1。
最多的情况下,除了最后一层度为0,其余结点都是度为2的结点,即 2h-1个。

题2

2、一棵有124个叶结点的完全二叉树,最多有( )个结点。
A、247
B、248
C、249
D、250

解析:(B)
由于n0=n2+1,且N=n0+n1+n2,度为0和度为1的结点相差为1,所以完全二叉树中度为1的结点n1只可能是0或1,即当总结点数为偶数时n1=1,为奇数时n0=0。
本题中,n0=124,可得n2=123,由于是考虑最多结点数,即n1=1,所以N=124+123+1=248。

题3

3、若一棵二叉树有126个结点,在第7层(根结点在第1层)至多有()个结点。
A、32
B、64
C、63
D、不存在第7层

解析:(C)
考虑第1层到第6层结点都是满的情况,即第1层到第6层结点的结点数量为1+2+4+8+16+32=63个。第7层最多可有64个结点,由于二叉树有126个结点,即第7层还有126-63=63个结点。

题4

4 、一棵有n个结点的二叉树采用二次链表存储结点,其中非空指针数为(),而空指针数为()。
A、n+1;n-1
B、n;n-1
C、n-1;n+1
D、2n;2n-1

解析:(C)
n个结点的数有n-1条分支,每个分支对应一个指针,所以非空指针数为n-1;另外,由于每个结点中包含2个指针域(左指针域lchild、右指针域rchild),总指针域数量减去非空指针数即为空指针数,2n-(n-1)=n+1。

题5

5、在二叉树的前序序列、中序序列和后序序列中,所有叶子结点的先后顺序是()。
A、都不相同
B、完全相同
C、前序序列和中序序列相同,与后序序列不同
D、中序序列和后序序列相同,与前序序列不同

解析:(B)
三种遍历方式中,访问左右子树的顺序是相同的,只是访问根结点的先后顺序不同,故所有叶子结点的先后顺序是相同的。

题6

6、线索二叉树是一种()结构。
A、逻辑
B、逻辑和存储
C、物理
D、线性

解析:(C)
二叉树是一种逻辑结构,而线索二叉树是加上线索的链表结构,是一种物理结构。

题7

7、在有n个叶子结点的哈夫曼树中,非叶子结点的总数是();若该哈夫曼树有215个结点,对其进行哈夫曼编码,可以得到()个不同的码字。
A、n-1;108
B、n;107
C、2n-1;214
D、2n;215

解析:(A)
哈夫曼树中只有度为0和2的结点,由n0=n2+1,可得:非叶子结点的总数为n-1。
结点总数N=n0+n2,且n0=n2+1,N=215代入可得,n0=108。

题8

8、找出下列条件的二叉树:
A、先序遍历序列与后序遍历序列相同,为()
B、中序遍历序列与后序遍历序列相同,为()
C、先序遍历序列与中序遍历序列相同,为()
D、中序遍历序列与层次遍历序列相同,为()

解析:
A、空树或只有根结点的二叉树;
B、空树或任一结点至多只有左子树;
C、空树或任一结点至多只有右子树;
D、空树或任一结点至多只有右子树。

题9

9、(判断)哈夫曼编码树中,两个频率相同的字符具有相同的哈夫曼编码。

解析:(×)
不会有相同的哈夫曼编码,除非它们的字符相同,从而得到的哈夫曼编码也相同。

二、应用题

题10 二叉树的遍历序列

题型通过已知树的遍历序列,求其他遍历序列

10、某二叉树的中序遍历序列为ABCDEFG,后序遍历序列为BDCAFGE,求其先序遍历序列。

解:可知,二叉树的先、中、后序遍历序列以及层次遍历序列的遍历顺序如下:

遍历名称 遍历规则
先序遍历序列 根 > 左 > 右
中序遍历序列 左 > 根 > 右
后序遍历序列 左 > 右 > 根
层次遍历序列 左 > 右

首先,通过所给的两个序列恢复二叉树,后序遍历序列为BDCAFGE,所以该序列的最后一个元素“E”为二叉树的根结点,从而可得到:
设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码
继续对左子树和右子树的中序遍历和后序遍历进行拆分,先看E的左子树,由后序序列可知左子树中A为根结点,且由后序序列可知A无左子树,右子树为BCD;同理,E的右子树中,右子树中G为根结点,但是无法判断F为其左子树还是右子树,所以看中序遍历序列中,G的左边是F,由中序遍历规则,所以F为G的左子树,同时G无右子树,如下:
设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码
同上,可得C为根结点A的右子树,C的左子树为B,右子树为D,如下既是一棵完整的二叉树:
设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码
故可得其先序遍历序列:EACBDGF。

题11 12 二叉树的存储结构

题型根据树的存储结构,画出二叉树

11、下图是一个二叉树的顺序存储结构,其中空白表示该结点不存在,画出该二叉树,并求出该二叉树的中序序列和后序序列。

设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码
解:按完全二叉树存储,其中空白的为空,如下:
设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码
注:其中黑色标注只是为了更清楚展示该二叉树,二叉树只留蓝色部分即可。
中序序列:BADCFE;后序序列:BDFECA。

12、已知二叉树的静态二叉链表存储结构的定义以及二叉树T的静态二叉链表存储结构图如下,求
(1)二叉树T的树形结构图;
(2)二叉树T的前序、中序和后序遍历序列。

#define Maxsize 20	
typedef struct{
	char data;
	int lchild,rchild;
}node;
typedef struct{
	node tree[Maxsize];
	int root,nodenum;
}Sblinklist;
tree[ ] 1 2 3 4 5 6 7 8 9 10
lchild 0 0 1 3 0 5 0 6 0 9
data D G B A H E I C J F
rchild 2 0 0 8 0 7 0 10 0 0
T.root T.nodenum
4 10

解:(1)首先由第二个表可知,T.root 为4,T.nodenum 为10,分别对应该二叉树的根结点为tree[4]的结点和二叉树一共有10个结点,即根结点为tree[4]=A。
然后,通过第一个表可查到结点A的左孩子lchild和右孩子rchild为3和8:

tree[ ] 1 2 3 4 5 6 7 8 9 10
lchild 0 0 1 3 0 5 0 6 0 9
data D G B A H E I C J F
rchild 2 0 0 8 0 7 0 10 0 0

即结点B和结点C。
设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码
以结点B继续查下去,可查到结点B的左孩子lchild和右孩子rchild为1和0(0即为空):

tree[ ] 1 2 3 4 5 6 7 8 9 10
lchild 0 0 1 3 0 5 0 6 0 9
data D G B A H E I C J F
rchild 2 0 0 8 0 7 0 10 0 0

即结点B的左孩子为D,右孩子为空。
设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码
同样,查到结点C的左孩子为E,右孩子为F:

tree[ ] 1 2 3 4 5 6 7 8 9 10
lchild 0 0 1 3 0 5 0 6 0 9
data D G B A H E I C J F
rchild 2 0 0 8 0 7 0 10 0 0

设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码
……,按照上面的方法依次查下去,可得以下二叉树:
设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码
(2)二叉树T的前序、中序和后序遍历序列分别为:
ABDGCEHIFJ、DGBAHEICJF、GDBHIEJFCA。

题13 14 二叉树/树、森林之间的转换

题型一根据所给二叉树,将其转换为树

13、将以下这棵二叉树转换为树。

设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码
解:第一步,旋转。将该二叉树中除了根结点左右子树的所有结点向右旋转45°,如下:
设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码
第二步,连线。若某结点的左孩子有右子树,则右子树与该结点相连,A结点的左孩子B有右子树D,所以将A与D相连;C结点的左孩子E有右子树H,所以将C与H相连,如下:
设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码
第三步,断线。删除除根结点外各结点右子树的右分支与其父结点连线,如下:
设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码
即可得到二叉树转换而来的树:
设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码
题型二根据所给森林,将其转换为二叉树

14、已知下面由三棵树组成的森林,将其转换为二叉树。

设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码
解:第一步,连线。首先将所有结点的兄弟结点相连,另外各树的根结点也相连,如下:
设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码
第二步,断线。只保留所有结点的最左边子女,而其他结点断开,如下:
设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码
断开后:
设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码
第三步,旋转。以第一棵树的根结点为轴心,顺时针旋转45°,如下:
设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码

题15 线索二叉树

题型根据所给二叉树,画出该二叉树的线索二叉树

15、设一棵二叉树的先序、中序遍历序列分别为ABDFCEGH和BFDAGEHC,求这棵二叉树的后序线索树。

解:首先,求出该二叉树,可以得到:
设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码
第一步,求出要画的相应线索二叉树的先/中后序遍历序列。可得到其后序遍历序列是FDBGHECA。
第二步,画线索(针对二叉树中缺少左、右孩子的结点)。若该结点无左孩子,则线索指向相应线索二叉树的先/中/后序遍历序列的前驱,若无前驱则指向NULL;若该结点无右孩子,则线索指向相应线索二叉树的先/中/后序遍历序列的后继,若无后继则指向NULL。
例如,结点D无右孩子,在后序遍历序列中结点D的后继是B,所以指向B;结点F无左孩子,在后序遍历序列中结点F无前驱结点,所以指向NULL;结点H无左孩子和右孩子,在后序遍历序列中结点H的前驱是G,后驱是E,所以分别指向G和E,如下:
设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码

题16 17 哈夫曼编码和哈夫曼树

题型一求哈夫曼树的带权路径长度

16、已知4个字符A、B、C、D的哈夫曼编码分别是1、01、000、001,下列串是由字符组成的一段文本的哈夫曼编码:1001000011011010011010011,将该串还原成编码前的文本,以字符在文本中出现的次数为权值,求出这棵树的带权路径长度。

解:由哈夫曼编码可得到如下:
设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码

1 001 000 01 1 01 1 01 001 1 01 001 1
A D C B A B A B D A B D A

所以还原成编码前的文本为ADCBABABDABDA,
可得到:字符A出现5次,B出现4次,C出现1次,D出现3次,
WPL=1×5+2×4+3×(1+3)=25。
题型二已知字符的概率,设计哈夫曼编码,并画出相应的哈夫曼树

16、若通信系统中只可能出现5种字符A、B、C、D和E,其概率分别是0.12、0.15、0.19、0.21和0.33。
(1)画出哈夫曼树;
(2)设计哈夫曼编码。

解:(1)将频率扩大100倍,分别对应12、15、19、21、33,
首先选取两棵根结点权值最小的树作为左、右子树,新的二叉树的根结点权值为其权值之和,新的结点添加进去。
12+15=27,将27添加,如下图:
设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码
继续并入:
设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码
27和33并入,27+33=60:
设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码
40+60=100,100并入:
设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码
(2)进行哈夫曼编码,从根结点到叶子结点,左分支为0,右分支为1,如下:
设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码
可得到:

A B C D E
100 101 00 01 11

题18 19 20树型查找——二叉排序树(二叉查找树)

题型一根据所给序列,构造二叉排序树

18、输入一个正整数序列(53,17,12,66,58,70,87,25,56,60),求:
(1)按次序构造一棵二叉排序树;
(2)按照二叉排序树,怎么得到一个从小到大的有序序列?
(3)画出二叉排序树中删除“66”后的树结构。

解:(1)二叉排序树的定义中,左子树、右子树和根结点的规定如下:
左子树<根结点<右子树。
首先,按照次序开始构造,17<53,根据定义17应该放在53的左子树,如下:
设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码
因为12<17,所以12放在17的左子树,如下:
设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码
接下来的66,由于66>53,所以应该放在53的右子树;又因为58<66,所以58放在66的左子树,如下:
设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码
70>66,所以应该放在66的右子树;87>70,所以应该放在70的右子树,如下:
设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码
由于25>17,所以应该放在17的右子树,如下:
设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码
56<58,放在58的左子树;60>58,放在58的右子树,如下:
设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码
(2)由于中序遍历一棵二叉树时可以得到一个结点值递增的有序序列,所以有两种方法可以实现得到一个从小到大的有序序列:
①可以将二叉排序树的中序遍历序列依次压入一个栈中,然后再依次出栈;
②定义一个一维数组,从后往前依次放入中序遍历序列,然后再输出数组中的元素。
(3)在二叉排序树中,当删除某个结点元素时,应该用该树的中序遍历序列中该结点的前驱/后继结点来替代,从而才能保证经过调整的树仍然保持二叉排序树的性质。
中序遍历序列为:12,17,25,53,56,58,60,66,70,87。
替代前后的树结构如下:
设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码
题型二根据二叉排序树,求查找成功和查找不成功的平均查找长度

19、如图所示,求出该二叉排序树查找成功和查找不成功的平均查找长(只将与关键字的比较次数计算在内)。

设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码
解:查找成功时,平均查找长度=(1+2+3+4)/6=15/6;
查找失败时,如下,方框中的
设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码
平均查找长度=(2×2+3×3+4×2)/7=21/7。

20、假定对有序表:{13,17,21,28,34,36,42,49,53,62,77,85}进行二分查找,求:
(1)画出二分查找树;
(2)若查找元素81,需要依次与哪些元素进行比较?
(3)假定每个元素的查找概率相等,求查找成功与查找不成功时的平均查找长度。

解:(1)按照次序构造,如下可得该二分查找树:
设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码
(2)根据二叉查找树,可知需要依次与36,53,77,85进行比较。
(3)查找成功时,ASL=(1×1+2×2+3×4+4×5)/12=37/12;
查找不成功时,ASL=(3×3+4×10)/13=49/13。

题21 树型查找——平衡二叉树

题型根据所给序列,构造平衡二叉树,且画出删除相应结点后的平衡二叉树

21、以关键字序列{16,3,7,11,9,26,18,14,15}构造一棵AVL树(平衡二叉树),构造完成后依次删除结点16,15,11。(同时需要用虚线标出需要进行平衡调整的3个结点)

解:首先,插入结点16,此时树为空,可直接插入,
然后插入结点3,由于3<16,应该放在结点16的左子树,此时无不平衡现象发生:
设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码
继续插入结点7,由于7>3,按照规则应该放在结点3的右子树上,此时不平衡【平衡二叉树可定义为一棵空树或一棵其左子树和右子树都是平衡二叉树,且左子树和右子树的高度差的绝对值不超过1】,应进行调整,如下:
设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码
插入11,无不平衡现象发生:
设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码
插入9,此时不平衡现象:
设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码
经过调整后的二叉树:
设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码
插入26,此时不平衡现象:
设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码
经过调整后,仍然满足左子树<根结点<右子树的规则:
设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码
插入18,此时不平衡现象:
设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码
经过调整后,如下:
设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码
插入14,此时无不平衡现象,正常插入:
设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码
插入15,此时出现不平衡现象,需调整:
设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码
调整后:
设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码
若删除结点16,由于结点16是个叶子结点,可以直接删除【删除叶子结点的情况】,并不会影响平衡二叉树的性质,如下即是删除后的树形:
设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码
若删除结点15,由于结点15只有左子树而无右子树,只需将该结点删掉,子树接上即可【删除只有单个子树的结点情况】,如下:
设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码
删除后:
设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码
若删除结点11,由于结点11既有左子树也有右子树,需要将这种情况转换为第一种或者第二种情况,可以沿着左(右)子树根结点的树根一直向下到最右(左)边的结点,用该结点代替要删除的结点可,这里由于代替的是叶子结点9,转换为第一种情况,直接将其删除即可,然后原结点11用该结点9代替。【删除左右子树都有的结点】
设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少,数据结构重点习题,数据结构,树,二叉树,哈夫曼树,哈夫曼编码文章来源地址https://www.toymoban.com/news/detail-774438.html

到了这里,关于【数据结构】——树和二叉树的相关习题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构—树和二叉树

    5.1树和二叉树的定义 树形结构 (非线性结构):结点之间有分支,具有层次关系。 5.1.1树的定义 树(Tree)是n(n≥0)个结点的有限集。 若n=0,称为空树; 若n>0,则它满足如下两个条件: 有且仅有一个特定的称为根(Root)的结点; 其余结点可分为m(m≥0)个互不相交的

    2024年02月14日
    浏览(46)
  • 树和二叉树 --- 数据结构

    目录 1.树的概念及结构 1.1树的概念 1.2树的表示 1.3树在实际生活中的运用 2.二叉树的概念及结构  2.1概念 2.2特殊的二叉树 2.3二叉树的性质 2.4二叉树的存储结构 树是一种 非线性 的数据结构,它是由n (n=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为 它看起来

    2024年02月15日
    浏览(44)
  • 数据结构--树和二叉树

    树是一种 非线性 的数据结构,它是由n(n=0)个有限结点组成一个具有层次关系的集合。把 它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。 有一个 特殊的结点,称为根结点 ,根节点没有前驱结点。 除根节点外,其余结点被分成M(M0)个互不相交

    2024年02月12日
    浏览(41)
  • 【数据结构】树和二叉树——堆

    目录 🍉一.树的概念及结构🍉 1.树的概念 2.树的相关术语 3.树的表示 4.树在实际中的应用 🍊二.二叉树的概念和结构🍊 1.二叉树的概念  2.特殊的二叉树 2.1.满二叉树 2..2.完全二叉树 3.二叉树的性质 4.二叉树的存储结构          4.1.顺序存储 4.2.链式存储 🍎三.堆的顺序结构

    2023年04月14日
    浏览(47)
  • 数据结构-树和二叉树篇

    思维导图(基于教材) 错题复盘+计算题(基于习题解析) 课后习题 从这章开始,要是上课听不懂的话,推荐去看B站青岛大学王卓王卓老师讲解的很细节,基本上每个知识点十几二十分钟,刚开始看的时候,可能会不习惯王老师的语气词,别退出,视频重要的是老师讲解的

    2024年01月17日
    浏览(47)
  • 【Java 数据结构】树和二叉树

    篮球哥温馨提示:编程的同时不要忘记锻炼哦! 目录 1、什么是树? 1.1 简单认识树  1.2 树的概念  1.3 树的表示形式 2、二叉树 2.1 二叉树的概念 2.2 特殊的二叉树 2.3 二叉树的性质 2.4 二叉树性质相关习题 3、实现二叉树的基本操作 3.1 了解二叉树的存储结构 3.2 简单构造一棵

    2024年01月16日
    浏览(45)
  • 【数据结构之树和二叉树】

    前言: 前篇学习了 数据结构的栈和队列,那么这篇继续学习树及其相关内容基础内容。 / 知识点汇总 / 概念 :树是一种非线性结构,是由有限个节点组成的具有层次关系的集合。倒立的树模样。 有一个特殊的结点,称为根节点,根节点没有前驱。 另外的子树有且只有一个

    2024年01月16日
    浏览(55)
  • 【数据结构】树和二叉树概念

    树是一种 非线性 的数据结构,它是由n(n=0)个有限结点组成一个具有层次关系的集合。 把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。 有一个 特殊的结点,称为根结点 ,根节点没有前驱结点 除根节点外, 其余结点被分成M(M0)个互不相交

    2024年02月09日
    浏览(39)
  • 数据结构之树和二叉树

    目录 一、树简介 二、二叉树 1、简介 2、二叉树的性质 3、满二叉树和完全二叉树  三、二叉树的遍历 四、二叉树遍历代码实现 五、二叉搜索树(Binary Search Tree) 1、简介 2、二插搜索树的局限性 六、平衡二叉搜索树(AVL树) 七、红黑树(Red-Black Tree) 1、简介 2、性质 3、使

    2024年02月05日
    浏览(40)
  • 数据结构期末复习(4)串 树和二叉树

    在数据结构中,串是由零个或多个字符组成的有限序列。它是一种线性数据结构,常用于表示和处理文本、字符串等信息。 串的特点包括: 顺序性:串中的字符按照一定的先后顺序排列,每个字符都有一个唯一的位置。 有限性:串的长度是有限的,它由字符的个数决定。

    2024年01月17日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包