2024年1月4日发(作者：)
习 题
1． 对于如图6-21所示的二叉树，试给出：
（1）它的顺序存储结构示意图。
（2）它的二叉链表存储结构示意图。
（3）它的三叉链表存储结构示意图。
B
D
E
F
A
C
G
H
图6-21 题1图
2． 证明：在结点数多于1的哈夫曼树中不存在度为1的结点。
3． 证明：若哈夫曼树中有n个叶结点，则树中共有2n-1个结点。
4． 证明：由二叉树的前序序列和中序序列可以唯一地确定一棵二叉树。
5． 已知一棵度为m的树中有n1个度为1的结点，n2个度为2的结点，……，nm个度为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的左孩子结点的算法。
发布者：admin，转转请注明出处：http://www.yc00.com/web/1704375611a1346781.html
评论列表（0条）