第5章  树
【例5-1】写出如图5-1所示的树的叶子结点、非终端结点、每个结点的度及树深度。
解：
（1）叶子结点有：B、D、F、G、H、I、J。
（2）非终端结点有：A、C、E。
（3）每个结点的度分别是：A的度为4，C的度为2，E的度为3，其余结点的度为0。
（4）树的深度为3。
【例5-2】一棵度为2的树与一棵二叉树有什么区别？
解：度为2的树有两个分支，但分支没有左右之分；一棵二叉树也有两个分支，但有左右之分，左右子树的次序不能交换。
【例5-3】树与二叉树有什么区别？
解：区别有两点：
（1）二叉树的一个结点至多有两个子树，树则不然；
（2）二叉树的一个结点的子树有左右之分，而树的子树没有次序。
【例5-4】分别画出具有3个结点的树和三个结点的二叉树的所有不同形态。
解：如图5-2(a)所示，具有3个结点的树有两种不同形态。
    如图5-2(b)所示，具有3个结点的二叉树有以下五种不同形态。
【例5-5】如图5-3所示的二叉树，试分别写出它的顺序表示和链接表示（二叉链表）。
解：
（1）顺序表示。
1
2
3
4
5
6
7
8
9
10
11
a
b
c
d
e
^
^
^
^
f
g
（2）该二叉树的二叉链表表示如图5-4所示。
【例5-6】试出满足下列条件的所有二叉树：
（1）先序序列和中序序列相同；
（2）中序序列和后序序列相同；
（3）先序序列和后序序列相同。
解：
（1）先序序列和中序序列相同的二叉树为：空树或者任一结点均无左孩子的非空二叉树；
（2）中序序列和后序序列相同的二叉树为：空树或者任一结点均无右孩子的非空二叉树；
（3）先序序列和后序序列相同的二叉树为：空树或仅有一个结点的二叉树。
【例5-7】如图5-5所示的二叉树，要求：
（1）写出按先序、中序、后序遍历得到的结点序列。
（2）画出该二叉树的后序线索二叉树。
解：
（1）    先序遍历序列：ABDEFC
        中序遍历序列：DEFBAC
后序遍历序列：FEDBCA
（2）其后序线索二叉树如图5-6所示。
【例5-8】将图5-7所示的树转换为二叉树。
解：第一步，加线。第二步，抹线。第三步，旋转。过程如图5-8所示。
【例5-9】将如图5-9所示的二叉树转换为树。
解： 第一步，加线。第二步，抹线。第三步，调整。过程如图5-10所示。
【例5-10】将如图5-11所示的森林转换成二叉树。
解： 步骤略，结果如图5-12所示。
【例5-11】假定用于通信的电文由8个字符A、B、C、D、E、F、G、H组成，各字母在电文中出现的概率为5％、25％、4％、7％、9％、12％、30％、8％，试为这8个字母设计哈夫曼编码。
解： 根据题意，设这8个字母对应的权值分别为（5，25，4，7，9，12，30，8），并且n=8。
（1）设计哈夫曼树的步骤如图5-13所示。
（2）设计哈夫曼编码
利用第八步得到的哈夫曼树，规定左分支用0表示，右分支用1表示，字母A、B、C、D、E、F、G、H的哈夫曼编码如下表示：
A:0011        B:01            C:0010        D:1010
E:000        F:100        G:11            H:1011
习题5
一、单项选择题
1. 在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（  1. C）个。
A. 4            B. 5            C. 6            D. 7
2. 假设在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为（2. B ）个。
A. 15            B. 16            C. 17            D. 47
3. 假定一棵三叉树的结点数为50，则它的最小高度为（3. C ）。
A. 3             B. 4            C. 5            D. 6
4. 在一棵二叉树上第4层的结点数最多为（  4. D）。
A. 2            B. 4            C. 6            D. 8
5. 用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组中]，结点R[i]若有左孩子，其左孩子的编号为结点（5. B）。
A. R[2i+1]    B. R[2i]        C. R[i/2]        D. R[2i-1]
6. 由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（6. D  ）。
A. 24            B. 48            C. 72            D. 53
7. 线索二叉树是一种（  7. C）结构。
A. 逻辑        B. 逻辑和存储    C. 物理            D. 线性
8. 线索二叉树中，结点p没有左子树的充要条件是（  8. B）。
A. p->lc=NULL                B. p->ltag=1 
C. p->ltag=1 且p->lc=NULL      D. 以上都不对
9. 设n , m 为一棵二叉树上的两个结点，在中序遍历序列中n在m前的条件是（9. B）。
A. n在m右方                    B. n在m 左方   
C. n是m的祖先                  D. n是m的子孙
10. 如果F是由有序树T转换而来的二叉树，那么T中结点的前序就是F中结点的（10. B  ）。
A. 中序        B. 前序            C. 后序            D. 层次序
11. 欲实现任意二叉树的后序遍历的非递归算法而不必使用栈，最佳方案是二叉树采用（  11. A）存储结构。
先序中序后序遍历二叉树
A. 三叉链表    B. 广义表        C. 二叉链表        D. 顺序
12. 下面叙述正确的是（  12. D）。
A. 二叉树是特殊的树
B. 二叉树等价于度为2的树
C. 完全二叉树必为满二叉树
D. 二叉树的左右子树有次序之分

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