# 树习题

## 基本概念

**例题** 在一棵度为$4$的树$T$中，若有$20$个度为$4$的结点，$10$个度为$3$的结点，$1$个度为$2$的结点，$10$个度为$1$的结点，则树$T$的叶结点个数是()。

$A.41$

$B.82$

$C.113$

$D.122$

解：$B$。设树中度为$i$（$i=0,1,2,3,4$）的结点数分别为$n_i$，树中结点总数为$n$，则$n$=分支数$+1$，而分支数又等于树中各结点的度之和，即$n=1+0n_0+n_1+2n_2+3n_3+4n_4=n_0+n_1+n_2+n_3+n_4$。依题意，$n_1+2n_2+3n_3+4n_4=10+2+30+80= 122$，$n_1+n_2+n_3+n_4=10+1+10+20=41$，可得出$n_0=82$，即树$T$的叶结点的个数是$82$。

## 二叉树

### 二叉树性质

**例题** 下列关于二叉树的说法中，正确的是()。

$A.$度为$2$的有序树就是二叉树

$B.$含有$n$个结点的二叉树的高度$\lfloor\log_2n\rfloor+1$

$C.$在完全二叉树中，若一个结点没有左孩子，则它必是叶结点

$D.$在任意一棵非空二叉排序树中，删除某结点后又将其插入，则所得二叉排序树与删除前原二叉排序树相同

解：$C$。在二叉树中，若某个结点只有一个孩子，则这个孩子的左右次序是确定的，而在度为$2$的有序树中，若某个结点只有一个孩子，则这个孩子就无须区分其左右次序，$A$错误。选项$B$仅当是完全二叉树时才有意义，对于任意一棵二叉树，高度可能为$\lfloor\log_2n\rfloor+1\sim n$。在二叉排序树中插入结点时，一定插入在叶结点的位置，故若先删除分支结点再插入，则会导致二叉排序树的重构，其结果就不再相同，$D$错误。根据完全二叉树的定义，在完全二叉树中，若有度为$1$的结点，则只可能有一个，且该结点只有左孩子而无右孩子，选项$C$正确。

**例题** 设二叉树有$2n$个结点，且$m<n$，则不可能存在()的结点。

$A.n$个度为$0$

$B.2m$个度为$0$

$c.2m$个度为$1$

$D.2m$个度为$2$

解：$C$。由二叉树的性质可知$n_0=n_2+1$，结点总数$=2n=n_0+n_1+n_2=n_1+2n_2+1$，则$n_1=2(n-n_2)-1$，所以$n$为奇数，说明该二叉树中不可能有$2m$个度为$1$的结点。

**例题** 已知一棵完全二叉树的第$6$层（设根为第$1$层）有$8$个叶结点，则该完全二叉树的结点个数最多是()。

$A.39$

$B.52$

$C.111$

$D.119$

解：$C$。第$6$层有叶结点，完全二叉树的高度可能为$6$或$7$，显然树高为$7$时结点最多。完全二叉树与满二叉树相比，只是在最下一层的右边缺少了部分叶结点，而最后一层之上是个满二叉树，并且只有最后两层上有叶结点。若第$6$层上有$8$个叶结点，则前$6$层为满二叉树，而第$7$层缺失了$8\times2=16$个叶结点，故完全二叉树的结点个数最多为$2^7-1-16=111$。

**例题** 一棵有$124$个叶子结点的完全二叉树，最多有()个结点。

$A.247$

$B.248$

$C.249$

$D.250$

解：$B$。在非空的二叉树当中，由度为$0$和$2$的结点数的关系$n_0=n_2+1$可知$n_2=123$；总结点数$n=n_0+n_1+n_2=247+n_1$，其最大值为$248$（由于完全二叉树$n_1$的取值为$1$或$0$，当$n=1$时结点最多）。注意，由完全二叉树总结点数$n$的奇偶性可以确定$n_1$的值，但不能根据$n_0$来确定的$n_1$值。

### 二叉树遍历

#### 序列遍历概念

**例题** ()的遍历仍需要栈的支持。

$A.$前序线索树

$B.$中序线索树

$C.$后序线索树

$D.$所有线索树

解：$C$。前序遍历（中左右）、中序遍历（左中右）的最后访问的结点都是左或右叶结点，叶结点是没有子树的，所以两个指针域空出来了，可以存放线索指针用于回溯。但是后序遍历（左右中），最后访问的是子树的根结点，子树根结点的两个指针域都指向子树了，所以不能空出来存放线索信息，只能借助栈存储。

#### 二叉树个数

**例题** 先序序列为$a,b,c,d$的不同二叉树的个数是()。

$A.13$

$B.14$

$C.15$

$D.16$

解：由于只有先序序列和中序序列才能确定一个二叉树，所以现在已知先序序列，要求多少个二叉树就要求中序序列能有多少个。由于二叉树遍历的递归算法可以由带有栈的非递归算法实现，所以栈可以将序列转换为二叉树。所以这个问题就等于入栈先序序列，出栈中序序列。这就是卡特兰数$\dfrac{1}{n+1}C_{2n}^n=\dfrac{1}{n+1}\dfrac{(2n)!}{n!\times n!}=\dfrac{1}{5}\dfrac{8!}{4!\times4!}=14$。

#### 结点关系

**例题** 在二叉树中有两个结点$m$和$n$，若$m$是$n$的祖先，则使用()可以找到从$m$到$n$的路径。

$A.$先序遍历

$B.$中序遍历

$C.$后序遍历

$D.$层次遍历

解：$C$。首先无论是什么遍历方式都会是从左到右的顺序，所以最先找到的一定是左边的结点，最后找到的一定是右边的结点。$m$是$n$的祖先。先序遍历访问次序：左根右，当$n$在左边遍历时会找到$m$到$n$的路径，而当$n$在右边时，由于已经遍历完根结点和左子树，则根和左部分的结点没用了就会出栈（使用递归算法时函数数据由栈保存），则$m$就丢掉了，也就不能找到$m$到$n$的路径。同理中序遍历也是会丢掉根和左部分，若$n$在右边则会丢失路径。层次遍历每遍历都会丢掉根结点，所以也不能找到。而后序遍历最后遍历根结点，所以根结点会一直保留到子结点全部遍历完才会丢弃，则此时就能找到$n$到$m$的路径。

**例题** 若$X$是二叉中序线索树中一个有左孩子的结点，且$X$不为根，则$X$的前驱为()。

$A.X$的双亲

$B.X$的右子树中最左的结点

$C.X$的左子树中最右结点

$D.X$的左子树中最右叶结点

解：$C$。在二叉中序线索树中，某结点若有左孩子，则按照中序“左根右”的顺序，该结点的前驱结点为左子树中最右的一个结点（注意，并不一定是最右叶子结点）。

#### 遍历序列

**例题** 在二叉树的前序序列、中序序列和后序序列中，所有叶子结点的先后顺序()。

$A.$都不相同

$B.$完全相同

$C.$前序和中序相同，而与后序不同

$D.$中序和后序相同，而与前序不同

解：$B$。在三种遍历方式中，访问左右子树的先后顺序是不变的，只是访问根结点的顺序不同，因此叶子结点的先后顺序完全相同。此外，读者可以采用特殊值法，画一个结点数为三的满二叉树，采用三种遍历方式来验证答案的正确性。

**例题** 若一棵二叉树的前序遍历序列和后序遍历序列分别为$1,2,3,4$和$4,3,2,1$，则该二叉树的中序遍历序列不会是()。

$A.1,2,3,4$

$B.2,3,4,1$

$C.3,2,4,1$

$D.4,3,2,1$

解：$C$。前序序列为$NLR$，后序序列为$LRN$，由于前序序列和后序序列刚好相反，故不可能存在一个结点同时有左右孩子，即二叉树的高度为$4$。$1$为根结点，由于根结点只能有左孩子（或右孩子)，因此在中序序列中，$1$或在序列首或在序列尾，$A,B,C,D$皆满足要求。仅考虑以$1$的孩子结点$2$为根结点的子树，它也只能有左孩子(或右孩子)，因此在中序序列中，$2$或在序列首或在序列尾，$A, B,D$皆满足要求，故选$C$。

## 树与森林

### 森林与树的转换

**例题** 利用二叉链表存储森林时，根结点的右指针是()。

$A.$指向最左兄弟

$B.$指向最右兄弟

$C.$一定为空

$D.$不一定为空

解：$D$。森林与二叉树具有对应关系，因此，我们存储森林时应先将森林转换成二叉树，转换的方法就是“左孩子右兄弟”，与树不同的是，若存在第二棵树，则二叉链表的根结点的右指针指向的是森林中的第二棵树的根结点。若此森林只有一棵树，则根结点的右指针为空。因此，右指针可能为空也可能不为空。

### 转换结点关系

**例题** 将森林转换为对应的二叉树，若在二叉树中，结点$u$是结点$v$的父结点的父结点，则在原来的森林中，$u$和$v$可能具有的关系是()。

Ⅰ.父子关系

Ⅱ.兄弟关系

Ⅲ.$u$的父结点与$v$的父结点是兄弟关系

$A.$只有Ⅱ

$B.$Ⅰ和Ⅱ

$C.$Ⅰ和Ⅲ

$D.$Ⅰ、Ⅱ和Ⅲ

解：$B$。森林与二叉树的转换规则为“左孩子右兄弟”。在最后生成的二叉树中，父子关系在对应的森林关系中可能是兄弟关系或原本就是父子关系。情形Ⅰ：若结点$v$是结点$u$的第二个孩子结点，在转换时，结点$v$就变成结点$u$的第一个孩子的右孩子，符合要求。情形Ⅱ：结点$u$和$v$是兄弟结点的关系，但二者之中还有一个兄弟结点$k$，转换后结点$v$就变为结点$k$的右孩子，而结点$k$则是结点$u$的右孩子，符合要求。情形Ⅲ：结点$v$的父结点要么是原先的父结点，要么是兄弟结点。若结点$u$的父结点与$v$的父结点是兄弟关系，则转换之后不可能出现结点$u$是结点$v$的父结点的父结点的情形。

#### 结点数量

**例题** 设$F$是一个森林，$B$是由$F$变换来的二叉树。若$F$中有$n$个非终端结点，则$B$中右指针域为空的结点有()个。

$A.n-1$

$B.n$

$C.n+1$

$D.n+2$

解：$C$。根据森林与二叉树转换规则“左孩子右兄弟”。二叉树$B$中右指针域为空代表该结点没有兄弟结点。森林中每棵树的根结点从第二个开始依次连接到前一棵树的根的右孩子，因此最后一棵树的根结点的右指针为空。另外，每个非终端结点，其所有孩子结点在转换之后，最后一个孩子的右指针也为空，故树$B$中右指针域为空的结点有$n+1$个。

## 树的应用

### 哈夫曼树

#### 编码字符数

**例题** 设哈夫曼编码的长度不超过$4$，若已对两个字符编码为$1$和$01$，则还最多可对()个字符编码。

$A.2$

$B.3$

$C.4$

$D.5$

解：$C$。在哈夫曼编码中，一个编码不能是任何其他编码的前缀。已对两个字符编码为$1$和$01$，则第一位第二位都只能是$0$。$3$位编码可能是$001$，对应的$4$位编码只能是$0000$和$0001$。$3$位编码也可能是$000$，对应的$4$位编码只能是$0010$和$0011$。若全采用$4$位编码，则可以为$0000,0001,0010,0011$。题中问的是最多，故选$C$。

<!-- 若哈夫曼编码的长度只允许小于等于$4$，则哈夫曼树的高度最高是$5$，已知一个字符编码为$1$，另一个字符编码是$01$，这说明第二层和第三层各有一个叶子结点，为使得该树从第3层起能够对尽可能多的字符编码，余下的二叉树应该是满二叉树，底层可以有$4$个叶结点，最多可以再对$4$个字符编码。 -->

#### 结点数

**例题** 若度为$m$的哈夫曼树中，叶子结点个数为$n$，则非叶子结点的个数为()。

$A.n-1$

$B.\lfloor n/m\rfloor-1$

$C.\lceil(n-1)/(m-1)\rceil$

$D.\lceil n/(m-1)\rceil-1$

解：$C$。一棵度为$m$的哈夫曼树应只有度为$0$和$m$的结点，设度为$m$的结点（叶子结点）有$n_m$个，度为$0$的结点有$n_0$个，又设结点总数为$n$，$n=n_0+n_m$。因有$n$个结点的哈夫曼树有$n-1$条分支，则根据总结点与度数关系的公式（$n=n_1+2n_2+\cdots+mn_m+1$）得到$mn_m=n-1=n_m+n_0-1$，整理得$(m-1)n_m=n_0-1$，$n_m=(n-1)/(m-1)$。

#### 路径

**例题** 下列选项给出的是从根分别到达两个叶结点路径上的权值序列，属于同一棵哈夫曼树的是()。

$A.24,10,5$和$24,10,7$

$B.24,10,5$和$24,12,7$

$C.24,10,10$和$24,14,11$

$D.24,10,5$和$24,14,6$

解：$D$。首先根据两个叶子，以及访问到叶子的前一个结点，这个结点一定是叶子的父亲结点。再根据哈夫曼树的结点一定有兄弟，即不存在度为$1$的结点。因此可以知道兄弟的权值，这样，给定的一个序列就可以推出两个叶子，两个序列推出四个叶子，这样就可以根据是否选择最小的两个叶子结点组合在一起作为判据，决定这个序列是否成立了。

对于$D$，第一组最后一个是叶子结点为$5$的权值，中间的是$10$，则另一个叶子结点权值是$10-5=5$。这里不能继续推出。然后看第二组最后一个是叶子结点的权值为$6$，则另一个叶子结点权值为$14-6=8$。所以可以构造哈夫曼树：

```txt
   24
    |
 ------
 10  14
 |    |
---  ---
| |  | |
5 5  6 8
```

同理分析$A$，$24,10,5$和$24,10,7$两组的第二个权值相加为$20\neq24$，权值根本不相等不是哈夫曼树。

同理$B$，$24,10,5$和$24,12,7$第二个权值相加也不等于第一个值，所以也不对。

对于$C$，$24,10,10$和$24,14,11$数值相加都能对的上，计算两个叶子权值$10-10=0$、$14-11=3$。具体构造出哈夫曼树：

```txt
   24
    |
 -------
 10   14
 |     |
----  ----
|  |  |  |
10 0  11 4
```

看叶子节点的值，最小的是$0$和$4$，他们应该结合在一起，所以构造有问题。

### 并查集

**例题** 假设初始化$0\sim9$的并查集，按照$1-2$、$3-4$、$5-6$、$7-8$、8-9$、$1-8$、$0-5$、$1-9$的顺序进行查找和合并，求最后集合数量。

解：初始化时$0\sim9$一共十个集合。$1-2$时合并$\{1,2\}$。$3-4$时合并$\{3,4\}$、$5-6$时合并$\{5,6\}$、$7-8$时合并$\{7,8\}$、$8-9$时合并$\{7,8,9\}$、$1-8$时合并$\{1,2,7,8,9\}$、$0-5$时合并$\{0,5,6\}$、$1-9$时属于同一集合不用合并。最后为$\{0,5,6\}$、$\{1,2,7,8,9\}$、$\{3,4\}$，所以有三个。