admin 管理员组文章数量: 1086019
2024年3月20日发(作者：bool数据类型是什么意思)
习 题
1． 对于如图6-21所示的二叉树，试给出：
（1）它的顺序存储结构示意图。
（2）它的二叉链表存储结构示意图。
（3）它的三叉链表存储结构示意图。
B
D
E
A
C
F
G
H
图6-21 题1图
2． 证明：在结点数多于1的哈夫曼树中不存在度为1的结点。
3． 证明：若哈夫曼树中有
n
个叶结点，则树中共有2
n
-1个结点。
4． 证明：由二叉树的前序序列和中序序列可以唯一地确定一棵二叉树。
5． 已知一棵度为
m
的树中有
n
1
个度为1的结点，
n
2
个度为2的结点，……，
n
m
个度为
m
的结点，问该树中共有多少个叶子结点？有多少个非终端结点？
6． 设高度为
h
的二叉树上只有度为0和度为2的结点，问该二叉树的结点数可能
达到的最大值和最小值。
7． 求表达式(
a
+
b
*(
c
-
d
))-
e
/
f
的波兰式（前缀式）和逆波兰式（后缀式）。
8． 画出和下列已知序列对应的二叉树。
（1）二叉树的先序次序访问序列为：GFKDAIEBCHJ。
（2）二叉树的中序访问次序为：DIAEKFCJHBG。
9． 画出和下列已知序列对应的二叉树。
（1）二叉树的后序次序访问序列为：CFEGDBJLKIHA。
（2）二叉树的中序访问次序为：CBEFDGAJIKLH。
10． 画出和下列已知序列对应的二叉树。
（1）二叉树的层次序列为：ABCDEFGHIJ。
（2）二叉树的中序次序为：DBGEHJACIF。
11．给定一棵用二叉链表表示的二叉树，其根指针为root。试写出求二叉树结点的数
目的算法（递归算法或非递归算法）。
12．设计一个算法，要求该算法把二叉树的叶结点按从左至右的顺序链成一个单链表。
二叉树按二叉链表方式存储，链接时用叶结点的rchild域存放链指针。
13．给定一棵用二叉链表表示的二叉树，其根指针为root。试写出求二叉树的深度的
算法。
14． 给定一棵用二叉链表表示的二叉树，其根指针为root。试写出求二叉树各结点
的层数的算法。
15．给定一棵用二叉链表表示的二叉树，其根指针为root。试写出将二叉树中所有结
点的左、右子树相互交换的算法。
16．一棵
n
个结点的完全二叉树以一维数组作为存储结构，试设计非递归算法对该完
全二叉树进行前序遍历。
17．在二叉树中查找值为
x
的结点，试设计打印值为
x
的结点的所有祖先结点的算法。
18．已知一棵二叉树的后序遍历序列和中序遍历序列，写出可以唯一确定一棵二叉树
的算法。
19．在中序线索二叉树上插入一个结点
p
作为树中某结点
q
的左孩子，试给出实现上
述要求的算法。
20．给出在中序线索二叉树上删除某结点
p
的左孩子结点的算法。
版权声明：本文标题：数据结构 第6章习题 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1710947183a580912.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论