【数据结构入门精讲 | 第十二篇】考研408、公司面试树专项练习（一）

在上一篇文章中我们介绍了树的知识点，在这一篇中我们将进行树的专项练习。

方法介绍：

已知中序及后序，求前序
如后序为DABEC,中序为DEBAC，求前序
则后序倒着写，中序横着写
C
E
B
A
D
  D E B A C
接着寻找一一对应
C         c
E  e
B     b
A       a
D d  
  D E B A C
所以
得到树的结构为
    c
   e
  d  b
      a
 先序遍历只需要逆时针即可，所以为CEDBA










已知中序及先序，求后序
如中序为CBAEDF,前序为ABCDEF，求后序
则先序顺着写，中序横着写
A
B
C
D
E
F
  C B A E D F
接着寻找一一对应
A     a
B  b
C c
D         d
E       e
F           f
  C B A E D F
所以
得到树的结构为
      a
   b    d
 c     e  f
后序遍历只需要逆时针遍历节点右侧的点即可即可，所以为CBEFDA

判断题

1.一棵树中位于同一层上的结点称为兄弟结点。（错）
解析：拥有同一个父节点的节点互为兄弟节点。

2.如果由结点{ 1, 2, 3, 4 }组成的AVL树的深度是3（根结点的深度是1），则结点4有可能是根结点。（错）
解析：如果节点4是根节点，那么由于它是数值最大的节点，它下面必须有节点1、2、3，这将导致树的深度至少为4。

3.某二叉树的后序和中序遍历序列正好一样，则该二叉树中的任何结点一定都无右孩子。（对）
中序：左根右；后序：左右根。因此要使得序列一样，则无右孩子。

4.将1、2、3、4、5、6顺序插入初始为空的AVL树中，当完成这6个元素的插入后，该AVL树的先序遍历结果是：4、2、1、3、5、6。（对）

     4
    / \
   2   5
  / \   \
 1   3   6

5.如果由结点{ 1, 2, 3, 4 }组成的AVL树的深度是3（根结点的深度是1），则结点2或者结点3一定有两个子结点。（对）

6.在一棵由包含4、5、6等等一系列整数结点构成的二叉搜索树中，如果结点4和6在树的同一层，那么可以断定结点5一定是结点4和6的父亲结点。（错）
解析：二叉排序树的性质：若任意结点的左子树不空，则左子树上所有结点的值均不大于它的根结点的值。若任意结点的右子树不空，则右子树上所有结点的值均不小于它的根结点的值。

反例：

7.任何二叉搜索树中同一层的结点从左到右是有序的（从小到大）。（对）

8.对N（≥2）个权值均不相同的字符构造哈夫曼树，则树中任一非叶结点的权值一定不小于下一层任一结点的权值。（对）
因为由两个小的权相加得到父节点的权，所以父节点的权值一定大于等于任一子节点的权值。

9.哈夫曼编码是一种最优的前缀码。对一个给定的字符集及其字符频率，其哈夫曼编码不一定是唯一的，但是每个字符的哈夫曼码的长度一定是唯一的。（错）
第二层为一位，如1，第三层为两位，如11

10.哈夫曼树中一定没有度为 1 的结点。（对）
解析：要不然为2，要不然为0。

11.某二叉树的后序和中序遍历序列正好一样，则该二叉树中的任何结点一定都无左孩子。（错）
后序：左右根
中序：左根右
所以一定无右孩子

12.树是表示多对多关系的数据结构。（错）
解析：一对多。

13.存在一棵总共有2016个结点的二叉树，其中有16个结点只有一个孩子。（错）
解析：满二叉树总共的结点数为2的n次方-1，n是满二叉树的层数，所以该二叉树满的情况下是2048-1=2047。而2047-2016=31，也就是说，少了31个叶子结点，题目说16个结点只有一个孩子，那就先从16个叶节点上一层的父节点分别拿一个孩子，于是还剩15个结点未处理，15个除以2有余数，则多的一个要么17个只有一个孩子，要么15个只有一个孩子，不可能出现16个只有一个结点的孩子。

14.已知一棵二叉树的先序遍历结果是ABC,　则CAB不可能是中序遍历结果。（对）
解析：画图即可，不做过多赘述。

15.二叉树就是度为二的有序树。（错）
解析：存在一棵只有左孩子的二叉树，其度为1。

16.若一个结点是某二叉树的中序遍历序列的最后一个结点，则它必是该树的前序遍历序列中的最后一个结点。（错）
解析：不含右孩子的二叉树不满足以上结论。

17.某二叉树的前序和中序遍历序列正好一样，则该二叉树中的任何结点一定都无右孩子。(错)
解析：前序遍历：根左右
中序遍历：左根右
如果遍历序列想要一样，一定没有左孩子

18.对于一个有N个结点、K条边的森林，不能确定它共有几棵树。（错）
解析：设有M棵树，M={M1,M2,M3,M4…};
对于一棵树，有结论：边数=结点数-1,即v=n-1；
则有：
N=n1+n2+n3+n4+…
K=v1+v2+v3+v4+…=n1-1+n2-1+n3-1+n4-1+…=N-M
M=N-K
N-K是定值，可确定；

19.一个有N个结点、K条边的森林，共有N-K棵树（对）

20.存在一棵总共有2016个结点的二叉树，其中有16个结点只有一个孩子
答案：F
分析：
假设没有孩子的结点（叶结点）个数为n?，只有一个孩子的结点（度为1的结点）个数为n?，有两个孩子的结点（度为2的结点）个数为n?。
则n?+n?+n?=2016
∵n?=n?+1（二叉树的性质：叶结点个数等于度为2的结点个数加1）
∴n?+n?+n?=2016
?n?+1+16+n?=2016
?2n?=1999
n?除不尽，所以答案错误。

21.若一个结点是某二叉树的中序遍历序列的最后一个结点，则它必是该树的前序遍历序列中的最后一个结点。（错）
比如说两个点，一个点是另一个点的左子树

22.若A和B都是一棵二叉树的叶子结点，则存在这样的二叉树，其前序遍历序列为…A…B…，而中序遍历序列为…B…A…。（错）

23.对AVL树中的任一结点，其左子树的高度一定比其右子树的高度要高。（错）

24.在一棵二叉搜索树上查找63，序列39、101、25、80、70、59、63是一种可能的查找时的结点值比较序列。（错）
假设序列成立，则39、101均在右边，但25在左边，所以错。

25.将一棵完全二叉树存于数组中（根结点的下标为1）。则下标为23和24的两个结点是兄弟。（错）
画图即可

26.如果由结点{ 1, 2, 3, 4 }组成的AVL树的深度是3（根结点的深度是1），则结点2或者结点3一定有两个子结点。（对）
画图，根据定义可以发现要不然2为根节点，要不然3为根节点。

27.对 N（≥2）个权值均不相同的字符构造哈夫曼树，则树中任一非叶结点的权值一定不小于下一层任一结点的权值。（对）

28.3个结点的不同形态的二叉树共有（5）棵。

  o
 o
o


  o
 o
   o
   
   
  o
 o o
 
  o
    o
  o
  
  o
   o
    o

29.二叉树的先序和后序遍历序列能唯一确定这棵二叉树。（错）
大部分情况下不能。

30.在二叉树的第i层至多有2^(i-1)个节点。（对，树根为第一层。）

31.一个有n个顶点的连通图的生成树有且仅有n-1条边。（对）

32.对一颗二叉排序树按中序方法遍历得出的结点序列是从小到大的序列。（错，画图即可）

33.度为2的有序树一定是二叉树。（错）

34.后序遍历树与后序遍历由该树转换得到的二叉树有相同的遍历结果。（错）

35.在完全二叉树中，叶结点仅可能在最下层出现。（错）

      o
    o   o
  o  
这种情况下，叶节点可以在倒二层

满二叉树中不存在度为1的结点。（ 对 ）
有向图中所有顶点的出度之和等于图中的有向边数。（ 对 ）
无向图的邻接矩阵一定是对称的。（对）

选择题

1.

解析：n个符号代表n个互不相同的符号，n个叶子结点的哈夫曼树共2n-1个结点，解得n为58

2.对任意给定的含n个字符的有限集S，用二叉树表示S的哈夫曼编码集和定长编码集，分别得到
二叉树T1和T2。下列叙述中，正确的是（ D ）
A. T1与T2的结点数相同
B. T1的高度大于T2的高度
C. 出现频次不同的字符在T1中处于不同的层
D. 出现频次不同的字符在T2中处于相同的层

3.
选D，解析：

4.一棵有47个结点的树一定有______条边。（46）
解析：一棵树如果有 n 个结点,那么它一定恰好有 n-1 条边。

5.
选C，解析：假设d为2、3，画个图即可找出规律。

6.下列给定的关键字输入序列中，不能生成如下二叉排序树的是：

A.4, 2, 1, 3, 5
B.4, 5, 1, 2, 3
C.4, 5, 2, 1, 3
D.4, 2, 5, 3, 1
选B，解析：选项B生成二叉排序树的过程如下

显然B错。

7.

8.将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u和v可能具有的关系是：
1.父子关系； 2. 兄弟关系； 3. u的父结点与v的父结点是兄弟关系
选1和2，u的父结点与v的父结点是兄弟关系并不能使二叉树中结点u是结点v的父结点的父结点。

11.一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶子结点个数是( 82 )。
解析：20 * 4+10 * 3+1*2+10 * 1 +1（根结点）-20-10-1-10=82

先放32
接着2放在32左边
15比32小、比2大，放2右边
65比32大，放32右边
28比32小，比2大，比15大，放15右边

最后进行前序遍历即可
构建二叉搜索树不用平衡
构建AVL树才需要平衡

13.若一棵AVL树有 28 个结点，则该树的最大深度为__。空树的深度定义为0。
A.7
B.6
C.5
D.4
选B
解析：
方法：嵌套法
树空时，n0=0;
第一层n1=1;
公式：n(k)=n(k-1)+N(k-2)+1;
第二层n2=1+0+1=2;
第三层n3=2+1+1=4;
第四层n4=4+2+1=7;
第五层n5=7+4+1=12;
n1+…+n2=26
所以n6才能得到28个节点
所以深度为6

15.

C、D对称，所以不是
B根节点左边少右边多，但根节点的左节点左边多右边少，不满足

16.

17.

18.AVL 树是一棵具有以下性质的二叉搜索树：它是一棵空树或它的左右两棵子树的高度差的绝对值不超过 1，并且左右两棵子树都是 AVL 树。如果 AVL 树的深度为h（空树的深度定义为 0），则此树最少有（ ）个结点。
A.O(h)
B.O(2^h)
C.O(h*2^h)
D.O(h^2)

19.若要利用二叉树的算法来实现树的操作，应选择树的___存储结构。
A.双亲链表表示法
B.孩子链表表示法
C.双亲孩子表示法
D.孩子兄弟表示法
解析：选择树的孩子兄弟表示法存储结构。孩子兄弟表示法，也称为左儿子右兄弟表示法，是一种非常灵活的树的存储结构。在孩子兄弟表示法中，每个节点包含一个指向其第一个孩子的指针和一个指向其下一个兄弟的指针。使用孩子兄弟表示法存储树可以方便地利用二叉树的算法进行树的操作，因为孩子兄弟表示法将树转换为了二叉树的形式。例如，可以通过遍历孩子兄弟二叉树来实现树的深度优先遍历和广度优先遍历等操作。
因此，正确的选项是 D.孩子兄弟表示法。

20.利用后序线索链表进行二叉树的后序遍历时，若当前遍历结点存在右子树，则（D ）。
A、由当前结点的后继线索可找到后继结点
B、若当前结点是父结点的左子结点且父结点有右子树，则后继结点为父结点
C、若当前结点是根结点，则后继结点是其右子树中最左下结点
D、若当前结点是父结点的右子结点，则后继结点为父结点

填空题

1.若AVL树的深度是6（空树的深度定义为-1），则该树的最少结点数是：（33）

n = F(h+2) - 1；F是1 1 2 3 5 8…的斐波那契数列。

此题中说第5层，F(5+2) = F7 = 13，n = F(7) - 1 = 12。

2.空树的深度定义为-1，12个结点的AVL树的最大深度是？（5）

n0=-1
n1=0
n2=1
n3=2
n4=4
n5=7
7+4+2+1=14>12

补充：对于给定结点数，生成的AVL树深度最多为log2n（2为底数）

3.若某二叉树有 5 个叶结点，其权值分别为 10、12、16、21、30，则其最小的带权路径长度（WPL）是：（200）

结点的带权路径长度WPL：从树的根到该结点的路径长度（即经过的边数），与该结点上权值的乘积。树的带权路径长度WPL：树中所有叶子结点的带权路径长度之和。

两个小的数一直合并
最后得到：
根节点是第0层，计算叶子节点的权值*层数即可

WPL=(16+21+30)*2+(10+12)*3=200

4.已知8个数据元素为（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉搜索树后，最后两层上的结点总数为：（2）
解析：画图即可，不需要进行平衡操作

5.已知字符集{ a, b, c, d, e, f }，若各字符出现的次数分别为{ 6, 3, 8, 2, 10, 4 }，则对应字符集中各字符的哈夫曼编码可能是：00, 1011, 01, 1010, 11, 100

假设abcdef对应的权值为6、3、8、2、10、4
则每次选取最小的来构建哈夫曼树
          32
       14    19
     6   8   9 10
            4 5
              2 3
              
假设向左走为0，向右走为1
则6为00
8为01，由此00, 1011, 01, 1010, 11, 100是可能的

6.

7.

答案（25），解析：关键字23的插入位置为25的左孩子，此时破坏了平衡的性质，需要对平衡二叉树进行调整。最小不平衡子树就是该树本身，插入位置在根结点的右子树的左子树上，因此需要进行RL旋转，RL旋转过程如下图所示，旋转完成后根结点的关键字为25。

8.某二叉树中序遍历为ABCD，前序遍历为CABD，求后序遍历
解析：使用表格法即可

对若干个互不相同的符号进行哈夫曼编码，若生成的哈夫曼树共有 119 个结点，则共有（ ）个互不相同的符号。

对于哈夫曼树，有以下性质：
- 如果有 n 个互不相同的符号，则哈夫曼树的叶子节点数为 n。
- 哈夫曼树的非叶子节点数为 n-1。

题目中给出了哈夫曼树共有 119 个节点，其中包括了叶子节点和非叶子节点。我们可以得出以下等式：
n + (n-1) = 119

化简可得：
2n - 1 = 119
2n = 120
n = 60

因此，共有 60 个互不相同的符号。

二叉树的宽度

下列代码的功能是计算给定二叉树T的宽度。二叉树的宽度是指各层结点数的最大值。函数Queue_rear和Queue_front分别返回当前队列Q中队尾和队首元素的位置。

typedef struct TreeNode *BinTree;
struct TreeNode
{
   int Key;
   BinTree  Left;
   BinTree  Right;
};

int Width( BinTree T )
{
   BinTree  p;
   Queue Q;
   int Last, temp_width, max_width;

   temp_width = max_width = 0;
   Q = CreateQueue(MaxElements);
   Last = Queue_rear(Q);
   if ( T == NULL) return 0;
   else {
      Enqueue(T, Q);
      while (!IsEmpty(Q)) {
         p = Front_Dequeue(Q); 
         temp_width++; //填空
         if ( p->Left != NULL )  Enqueue(p->Left, Q);
         if ( p->Right != NULL )  Enqueue(p->Right, Q);  //填空
         if ( Queue_front(Q) > Last ) {
            Last = Queue_rear(Q);
            if ( temp_width > max_width ) max_width = temp_width;
            temp_width=0;//填空
         } /* end-if */
      } /* end-while */
      return  max_width;
   } /* end-else */
} 

R6-1 是否二叉搜索树

本题要求实现函数，判断给定二叉树是否二叉搜索树。

函数接口定义：

bool IsBST ( BinTree T );

其中BinTree结构定义如下：

typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

函数IsBST须判断给定的T是否二叉搜索树，即满足如下定义的二叉树：

定义：一个二叉搜索树是一棵二叉树，它可以为空。如果不为空，它将满足以下性质：

• 非空左子树的所有键值小于其根结点的键值。
• 非空右子树的所有键值大于其根结点的键值。
• 左、右子树都是二叉搜索树。

如果T是二叉搜索树，则函数返回true，否则返回false。

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>

typedef enum { false, true } bool;
typedef int ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

BinTree BuildTree(); /* 由裁判实现，细节不表 */
bool IsBST ( BinTree T );

int main()
{
    BinTree T;

    T = BuildTree();
    if ( IsBST(T) ) printf("Yes\n");
    else printf("No\n");

    return 0;
}
/* 你的代码将被嵌在这里 */

输入样例1：如下图
输出样例1：

Yes

输入样例2：如下图
输出样例2：

No

bool IsBST ( BinTree T )
{
    BinTree p;
    if((!T)||(!T->Left)&&(!T->Right))
        return true;      
        p=T->Left;
    if(p){
        while(p->Right)
            p=p->Right;
        if(p->Data>T->Data)
            return false;
    }
    p=T->Right;
    if(p){
        while(p->Left)
            p=p->Left;
        if(p->Data<T->Data)
            return false;
    }
    return true;
}

以上为树的判断题、选择题、填空题专项练习，下一篇我们将进行树的编程题专项练习。