习    题
1．    对于如图6-21所示的二叉树，试给出：
（1）它的顺序存储结构示意图。
（2）它的二叉链表存储结构示意图。
（3）它的三叉链表存储结构示意图。

图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的左孩子结点的算法。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。