# 第4章 树和二叉树

## 第一部分：知识点整理

### 1. 常见的数据结构分类
*   **集合（Set）**：一组无序且唯一的项的组合。不含任何元素的集合称为空集。
*   **线性结构（Linear Structure）**：一对一关系。如线性表、栈、队列、数组等。
*   **树形结构（Tree Structure）**：一对多关系。由 $n$ 个有限节点组成一个具有层次关系的集合。
*   **图形结构（Graph Structure）**：多对多关系。

---

### 2. 树（Tree）的基本概念与术语说明

为了便于理解，我们以一棵具体的树为例，用纯文本结构图进行展示，并结合该图对各项术语进行拆解：

```text
                            [ A ] (根结点, 第1层)
                         /    |    \
                       /      |      \
                     /        |        \
                 [ B ]      [ C ]      [ D ] (第2层)
                /     \       |       /  |  \
              [ E ]  [ F ]  [ G ]   [ H ][ I ][ J ] (第3层)
                     /   \                     |
                   [ K ] [ L ]               [ M ] (第4层)
```

#### 树的基本术语对照解析：

---

### 3. 树的表示方法与 C++ 实现

除了上述直观的树状图外，树的表示方法还有：
*   **嵌套集合表示法**（文氏图表示）
*   **凹入表示法**（类似书本目录的缩进）
*   **广义表表示法**：例如 `(A(B(E(K, L), F), C(G), D(H(M), I, J)))`
*   **孩子-兄弟表示法（二叉链表）**：将一般树转为二叉形式。每个结点含三个部分：数据、指向第一个孩子的指针、指向下一个兄弟的指针。

#### C++ 代码：孩子-兄弟表示法
```cpp
#include <iostream>

// 树的孩子-兄弟表示法结点定义
template <typename T>
struct CSNode {
    T data;                  // 结点数据域
    CSNode* firstChild;      // 指向该结点的第一个孩子结点（左指针）
    CSNode* nextSibling;     // 指向该结点的下一个兄弟结点（右指针）

CSNode(T val) : data(val), firstChild(nullptr), nextSibling(nullptr) {}
};
```

---

### 4. 二叉树（Binary Tree）的定义与类型

#### (1) 二叉树的定义
二叉树是 $n$（$n \ge 0$）个结点的有限集合，它或者是空集，或者由一个根结点及两棵互不相交的、分别称为根结点的**左子树**和**右子树**的二叉树组成。
*   **特点**：每个结点至多只有两棵子树（度 $\le 2$），且子树有左右之分，次序不能颠倒。

#### (2) 满二叉树与完全二叉树的文本形态对比

```text
满二叉树 (深度为 3, 共 7 个结点):
               [ 1 ]
             /       \
          [ 2 ]     [ 3 ]
         /     \   /     \
       [ 4 ]  [ 5][ 6 ]  [ 7 ]

完全二叉树 (最底层右侧允许缺少结点):
               [ 1 ]
             /       \
          [ 2 ]     [ 3 ]
         /     \   /
       [ 4 ]  [ 5][ 6 ]
```

*   **满二叉树**：每一层上的结点数都达到了最大值，叶子结点一个也不少。
*   **完全二叉树**：前 $h-1$ 层都是满的，最底层自左向右填充，右侧可以缺少若干连续结点。

---

### 5. 二叉树的性质
1.  在二叉树的第 $i$ 层上至多有 $2^{i-1}$ 个结点（$i \ge 1$）。
2.  深度为 $h$ 的二叉树至多有 $2^h - 1$ 个结点（$h \ge 1$）。
3.  对任何一棵二叉树，如果其叶结点数为 $n_0$，度为 2 的结点数为 $n_2$，则一定满足：
    $$n_0 = n_2 + 1$$
4.  具有 $n$ 个结点的完全二叉树的深度为 $\lfloor \log_2 n \rfloor + 1$。
5.  对一棵有 $n$ 个结点的完全二叉树，按层序自上而下、自左至右进行 $1$ 至 $n$ 编号，对任一结点 $i$：
    *   若 $i = 1$，则结点 $i$ 是根，无父结点；若 $i > 1$，则其双亲结点编号为 $\lfloor i/2 \rfloor$。
    *   若 $2i > n$，则结点 $i$ 无左孩子（必为叶子）；否则其左孩子编号为 $2i$。
    *   若 $2i + 1 > n$，则结点 $i$ 无右孩子；否则其右孩子编号为 $2i + 1$。

---

### 6. 二叉树的存储结构与 C++ 实现

二叉链表是二叉树最常用的链式存储方式。

```text
+------------+------------+------------+
|   lchild   |    data    |   rchild   |
|  (左孩子)  |  (数据域)  |  (右孩子)  |
+------------+------------+------------+
```

#### C++ 代码：二叉链表实现
```cpp
#include <iostream>

// 二叉树结点定义
template <typename T>
struct BiTNode {
    T data;                 // 数据域
    BiTNode* lchild;        // 左孩子指针
    BiTNode* rchild;        // 右孩子指针

BiTNode(T val) : data(val), lchild(nullptr), rchild(nullptr) {}
};
```
在有 $n$ 个结点的二叉链表中，一共有 $2n$ 个指针域，其中 $n-1$ 个指向具体孩子，其余 **$n+1$** 个为空指针域。

---

### 7. 二叉树的遍历方案

二叉树的遍历一般有三种路径，可以通过以下递归代码实现：

```cpp
// 访问结点的操作（示例中仅打印数据）
template <typename T>
void Visit(BiTNode<T>* node) {
    if (node) {
        std::cout << node->data << " ";
    }
}

// 先序遍历 (Root -> Left -> Right)
template <typename T>
void PreOrder(BiTNode<T>* root) {
    if (root != nullptr) {
        Visit(root);
        PreOrder(root->lchild);
        PreOrder(root->rchild);
    }
}

// 中序遍历 (Left -> Root -> Right)
template <typename T>
void InOrder(BiTNode<T>* root) {
    if (root != nullptr) {
        InOrder(root->lchild);
        Visit(root);
        InOrder(root->rchild);
    }
}

// 后序遍历 (Left -> Right -> Root)
template <typename T>
void PostOrder(BiTNode<T>* root) {
    if (root != nullptr) {
        PostOrder(root->lchild);
        PostOrder(root->rchild);
        Visit(root);
    }
}
```

---

## 第二部分：题目与练习

### 1. 课本基础练习题（对应 PDF 第 4 页）

#### 练习题：参照下图，回答下列问题

```text
                            [ A ]
                         /    |    \
                       /      |      \
                     /        |        \
                 [ B ]      [ C ]      [ D ]
                /     \       |       /  |  \
              [ E ]  [ F ]  [ G ]   [ H ][ I ][ J ]
                     /   \                     |
                   [ K ] [ L ]               [ M ]
```

1.  **该树有哪些结点**：`A, B, C, D, E, F, G, H, I, J, K, L, M`
    *   **其中的叶子结点有**：`E, K, L, G, H, I, M`
    *   **分支结点有**：`A, B, C, D, F, J`
2.  **结点 A 的度为**：`3`；**结点 B 的度为**：`2`；**树的度为**：`3`。
3.  **A 节点到 K 节点经过的路径**：`A -> B -> F -> K`
4.  **H 结点的兄弟结点有**：`I, J`；**堂兄弟结点有**：`E, F, G`
5.  **F 结点的祖先结点有**：`B, A`；**子孙结点有**：`K, L`
6.  **该树的深度为**：`4`；**树的宽度为**：`6`

---

### 2. 历年竞赛真题与解析

#### 【NOIP2019 普及组】
**题目**：一棵二叉树如下图所示。若采用顺序存储结构，即用一维数组元素存储该二叉树中的结点（根结点的下标为 1，若某结点的下标为 $i$，则其左孩子位于下标 $2i$ 处、右孩子位于下标 $2i+1$ 处），则该数组的最大下标至少为（ ）。

```text
                           [ A ] (1)
                          /     \
                      [ B ](2)  [ F ] (3)
                         \         \
                        [ C ](5)   [ G ] (7)
                        /   \         \
                    [ D ](10)[ E ](11)[ H ] (15)
```

*   **选项**：A. 6  B. 10  C. 15  D. 12
*   **答案**：**C**
*   **解析**：根据题目给定的规则可知，下标最大的结点为树中深度最大且最靠右的结点（即结点 `H`），其下标的推导过程为：
    *   根结点 `A` 的下标为 $1$；
    *   `A` 的右孩子 `F` 的下标为 $1 \times 2 + 1 = 3$；
    *   `F` 的右孩子 `G` 的下标为 $3 \times 2 + 1 = 7$；
    *   `G` 的右孩子 `H` 的下标为 $7 \times 2 + 1 = 15$。
    因此，该数组的最大下标至少为 15。

#### 【NOIP2019 普及组】
**题目**：假设一棵二叉树的后序遍历序列为 `DGJHEBIFCA`，中序遍历序列为 `DBGEHJACIF`，则其前序遍历序列为（ ）
*   **选项**：A. ABCDEFGHIJ  B. ABDEGHJCFI  C. ABDEGJHCFI  D. ABDEGHJFIC
*   **答案**：**B**
*   **解析**：
    1.  后序遍历的最后一位是根结点，故 `A` 是整棵树的根。
    2.  在中序遍历中找到 `A`，其左侧 `DBGEHJ` 为左子树，右侧 `CIF` 为右子树。
    3.  左子树对应后序序列为 `DGJHEB`（末尾为 `B`，故 `B` 是左子树根）。
    4.  在中序 `DBGEHJ` 中，`B` 左侧为 `D`（左子树），右侧 `GEHJ`（右子树）。
    5.  依此类推递归建树，最后按“根-左-右”顺序前序遍历，即可求得答案为 `ABDEGHJCFI`。

#### 【NOIP2018 普及组】
**题目**：根节点深度为 0，一棵深度为 $h$ 的满 $k（k>1）$叉树，即除最后一层无任何子节点外，每一层上的所有结点都有 $k$ 个子结点的树，共有（ ）个结点。
*   **选项**：A. $(k^{h+1}-1)/(k-1)$  B. $k^{h-1}$  C. $k^h$  D. $(k^{h-1})/(k-1)$
*   **答案**：**A**
*   **解析**：
    深度为 $h$ 的树（根节点深度为 0），其各层节点数呈等比数列：
    $$s = k^0 + k^1 + k^2 + \dots + k^h$$
    利用等比数列求和公式，可得总节点数：
    $$s = \frac{k^{h+1} - 1}{k - 1}$$

#### 【NOIP2018 提高组】
**题目**：下列说法中，是树的性质的有（ ）。【不定项选择】
*   **选项**：A. 无环  B. 任意两个结点之间有且只有一条简单路径  C. 有且只有一个简单环  D. 边的数目恰是顶点数目减 1
*   **答案**：**ABD**

#### 【NOIP2016 提高组】
**题目**：一棵二叉树如右图所示（共有6个结点），若采用二叉树链表存储该二叉树。如果没有左孩子或者右孩子，则对应的为空指针。那么该链表中空指针的数目为（ ）。
*   **选项**：A. 6  B. 7  C. 12  D. 14
*   **答案**：**B**
*   **解析**：对于具有 $n$ 个结点的二叉树，其二叉链表共有 $2n$ 个指针域。其中，除根结点以外的 $n-1$ 个结点都有指针指向它们（即非空指针有 $n-1$ 个）。
    空指针的数目 = $2n - (n - 1) = n + 1$。
    本题中 $n = 6$，因此空指针数目为 $6 + 1 = 7$。

---

### 3. 精选自测题（树和二叉树习题 1 & 2）

#### 单项选择题
1.  **下列说法中正确的是**（ ）
    *   A．任何一棵二叉树中至少有一个结点的度为 2
    *   B．任何一棵二叉树中每个结点的度都为 2
    *   C．任何一棵二叉树中的度肯定等于 2
    *   D．任何一棵二叉树中的度可以小于 2
    *   *答案*：**D** （例如空树、只有根结点的树，其度均小于 2）
2.  **若二叉树有10个度为2的结点，5个度为1的结点，则度为0的结点个数为**（ ）
    *   A. 9  B. 11  • C. 15  D. 不确定
    *   *答案*：**B** （根据公式 $n_0 = n_2 + 1$，已知 $n_2 = 10$，所以 $n_0 = 11$）
3.  **一棵完全二叉树上有 1001 个结点，其中叶子结点的个数是**（ ）
    *   A. 250  B. 500  C. 254  D. 505  E. 以上都不对
    *   *答案*：**E** （计算过程：完全二叉树中，度为1的结点个数 $n_1$ 只能是 0 或 1。由于总结点数 $1001$ 为奇数，故 $n_1 = 0$。根据公式 $n = n_0 + n_1 + n_2$ 以及 $n_2 = n_0 - 1$，得 $1001 = n_0 + 0 + n_0 - 1 \Rightarrow 2n_0 = 1002 \Rightarrow n_0 = 501$。选项中无 501，故选 E）
4.  **已知一棵二叉树的前序遍历结果为 `ABCDEF`，中序遍历结果为 `CBAEDF`，则后序遍历的结果为**（ ）
    *   A. CBEFDA  B. FEDCBA  C. CBEDFA  D. 不定
    *   *答案*：**A**
5.  **在二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序**（ ）
    *   A. 都不相同  B. 完全相同  C. 先序和中序相同，而与后序不同  D. 中序和后序相同，而与先序不同
    *   *答案*：**B**

#### 填空题
1.  深度为 $k$ 的完全二叉树至少有 **$2^{k-1}$** 个结点，至多有 **$2^k - 1$** 个结点。
2.  高度为 8 的完全二叉树至少有 **$64$** 个叶子结点。
    *   *(解析：第1层到第7层是满二叉树，共 $2^7-1=127$ 个结点。第8层至少有 $1$ 个结点。根据叶子结点计算：$2^{8-2} - 1 + 1 + 1 = 64$)*
3.  具有 $n$ 个结点的二叉树中，一共有 **$2n$** 个指针域，其中 **$n-1$** 个指向孩子，其余 **$n+1$** 个为 NULL。
4.  二叉树的先序序列和中序序列相同的条件是：**任何结点至多只有右子树，没有左子树或是空树**；
    二叉树的中序序列和后序序列相同的条件是：**任何结点至多只有左子树，没有右子树或是空树**；
    二叉树的先序序列和后序序列相同的条件是：**只有根结点**。

第4章树和二叉树

第一部分：知识点整理

1. 常见的数据结构分类

集合（Set）：一组无序且唯一的项的组合。不含任何元素的集合称为空集。
线性结构（Linear Structure）：一对一关系。如线性表、栈、队列、数组等。
树形结构（Tree Structure）：一对多关系。由 $n$ 个有限节点组成一个具有层次关系的集合。
图形结构（Graph Structure）：多对多关系。

2. 树（Tree）的基本概念与术语说明

为了便于理解，我们以一棵具体的树为例，用纯文本结构图进行展示，并结合该图对各项术语进行拆解：

                            [ A ] (根结点, 第1层)
                         /    |    \
                       /      |      \
                     /        |        \
                 [ B ]      [ C ]      [ D ] (第2层)
                /     \       |       /  |  \
              [ E ]  [ F ]  [ G ]   [ H ][ I ][ J ] (第3层)
                     /   \                     |
                   [ K ] [ L ]               [ M ] (第4层)

树的基本术语对照解析：

术语	定义说明	图中实例对应
根结点 (Root)	树中最顶层、没有双亲的唯一结点。	A 是这棵树的根结点。
结点的度 (Degree)	一个结点拥有的子树（直接后继）数目。	结点 A 的度为 3（有 B, C, D 三个孩子）；结点 F 的度为 2；结点 E 的度为 0。
树的度	一棵树中所有结点度的最大值。	该树中结点度最大为 3（A 和 D 的度均为 3），所以树的度为 3。
叶子结点 / 终端结点	度为零的结点（即没有子树的结点）。	图中的 E, K, L, G, H, I, M 均为叶子结点。
分支结点 / 非终端结点	度大于零的结点（除了叶子以外的所有结点，包括根）。	A, B, C, D, F, J 均为分支结点。
双亲与孩子 (Parent / Child)	指向子树根结点的结点称为双亲，子树的根称为孩子。	B 是 A 的孩子；A 是 B 的双亲。
兄弟结点 (Sibling)	具有同一双亲结点的其他子结点。	B, C, D 拥有共同的双亲 A，它们互为兄弟；K 和 L 互为兄弟。
堂兄弟 (Cousins)	其双亲在同一层的结点。	E 的双亲是 B，G 的双亲是 C。由于 B 和 C 都在第 2 层，所以 E 和 G 互为堂兄弟。
祖先结点 (Ancestor)	从根到该结点所经路径上的所有结点。	结点 K 的祖先包括 F, B, A。
子孙结点 (Descendant)	以某结点为根的子树中任意结点。	结点 B 的子孙有 E, F, K, L。
结点的层次 (Level)	从根开始算起，根为第 1 层，其孩子为第 2 层，依此类推。	第 1 层：A 第 2 层：B, C, D 第 3 层：E, F, G, H, I, J 第 4 层：K, L, M
树的深度/高度 (Depth)	树中结点的最大层次数。	该树共有 4 层，因而深度为 4。
树的宽度 (Width)	整棵树中结点个数最多那一层的结点数。	第 3 层包含的结点数量最多（E, F, G, H, I, J 共 6 个），故宽度为 6。

3. 树的表示方法与 C++ 实现

除了上述直观的树状图外，树的表示方法还有： * 嵌套集合表示法（文氏图表示） * 凹入表示法（类似书本目录的缩进） * 广义表表示法：例如 (A(B(E(K, L), F), C(G), D(H(M), I, J))) * 孩子-兄弟表示法（二叉链表）：将一般树转为二叉形式。每个结点含三个部分：数据、指向第一个孩子的指针、指向下一个兄弟的指针。

C++ 代码：孩子-兄弟表示法

#include <iostream>

// 树的孩子-兄弟表示法结点定义
template <typename T>
struct CSNode {
    T data;                  // 结点数据域
    CSNode* firstChild;      // 指向该结点的第一个孩子结点（左指针）
    CSNode* nextSibling;     // 指向该结点的下一个兄弟结点（右指针）

    CSNode(T val) : data(val), firstChild(nullptr), nextSibling(nullptr) {}
};

4. 二叉树（Binary Tree）的定义与类型

(1) 二叉树的定义

二叉树是 $n$（$n \ge 0$）个结点的有限集合，它或者是空集，或者由一个根结点及两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。 * 特点：每个结点至多只有两棵子树（度 $\le 2$），且子树有左右之分，次序不能颠倒。

(2) 满二叉树与完全二叉树的文本形态对比

满二叉树 (深度为 3, 共 7 个结点):
               [ 1 ]
             /       \
          [ 2 ]     [ 3 ]
         /     \   /     \
       [ 4 ]  [ 5][ 6 ]  [ 7 ]


完全二叉树 (最底层右侧允许缺少结点):
               [ 1 ]
             /       \
          [ 2 ]     [ 3 ]
         /     \   /
       [ 4 ]  [ 5][ 6 ]

满二叉树：每一层上的结点数都达到了最大值，叶子结点一个也不少。
完全二叉树：前 $h-1$ 层都是满的，最底层自左向右填充，右侧可以缺少若干连续结点。

5. 二叉树的性质

在二叉树的第 $i$ 层上至多有 $2^{i-1}$ 个结点（$i \ge 1$）。
深度为 $h$ 的二叉树至多有 $2^h - 1$ 个结点（$h \ge 1$）。
对任何一棵二叉树，如果其叶结点数为 $n_0$，度为 2 的结点数为 $n_2$，则一定满足： $$n_0 = n_2 + 1$$
具有 $n$ 个结点的完全二叉树的深度为 $\lfloor \log_2 n \rfloor + 1$。
对一棵有 $n$ 个结点的完全二叉树，按层序自上而下、自左至右进行 $1$ 至 $n$ 编号，对任一结点 $i$：
- 若 $i = 1$，则结点 $i$ 是根，无父结点；若 $i > 1$，则其双亲结点编号为 $\lfloor i/2 \rfloor$。
- 若 $2i > n$，则结点 $i$ 无左孩子（必为叶子）；否则其左孩子编号为 $2i$。
- 若 $2i + 1 > n$，则结点 $i$ 无右孩子；否则其右孩子编号为 $2i + 1$。

6. 二叉树的存储结构与 C++ 实现

二叉链表是二叉树最常用的链式存储方式。

+------------+------------+------------+
|   lchild   |    data    |   rchild   |
|  (左孩子)  |  (数据域)  |  (右孩子)  |
+------------+------------+------------+

C++ 代码：二叉链表实现

#include <iostream>

// 二叉树结点定义
template <typename T>
struct BiTNode {
    T data;                 // 数据域
    BiTNode* lchild;        // 左孩子指针
    BiTNode* rchild;        // 右孩子指针

    BiTNode(T val) : data(val), lchild(nullptr), rchild(nullptr) {}
};

在有 $n$ 个结点的二叉链表中，一共有 $2n$ 个指针域，其中 $n-1$ 个指向具体孩子，其余 $n+1$ 个为空指针域。

7. 二叉树的遍历方案

二叉树的遍历一般有三种路径，可以通过以下递归代码实现：

// 访问结点的操作（示例中仅打印数据）
template <typename T>
void Visit(BiTNode<T>* node) {
    if (node) {
        std::cout << node->data << " ";
    }
}

// 先序遍历 (Root -> Left -> Right)
template <typename T>
void PreOrder(BiTNode<T>* root) {
    if (root != nullptr) {
        Visit(root);
        PreOrder(root->lchild);
        PreOrder(root->rchild);
    }
}

// 中序遍历 (Left -> Root -> Right)
template <typename T>
void InOrder(BiTNode<T>* root) {
    if (root != nullptr) {
        InOrder(root->lchild);
        Visit(root);
        InOrder(root->rchild);
    }
}

// 后序遍历 (Left -> Right -> Root)
template <typename T>
void PostOrder(BiTNode<T>* root) {
    if (root != nullptr) {
        PostOrder(root->lchild);
        PostOrder(root->rchild);
        Visit(root);
    }
}

第二部分：题目与练习

1. 课本基础练习题（对应 PDF 第 4 页）

练习题：参照下图，回答下列问题

                            [ A ]
                         /    |    \
                       /      |      \
                     /        |        \
                 [ B ]      [ C ]      [ D ]
                /     \       |       /  |  \
              [ E ]  [ F ]  [ G ]   [ H ][ I ][ J ]
                     /   \                     |
                   [ K ] [ L ]               [ M ]

该树有哪些结点：A, B, C, D, E, F, G, H, I, J, K, L, M
- 其中的叶子结点有：E, K, L, G, H, I, M
- 分支结点有：A, B, C, D, F, J
结点 A 的度为：3；结点 B 的度为：2；树的度为：3。
A 节点到 K 节点经过的路径：A -> B -> F -> K
H 结点的兄弟结点有：I, J；堂兄弟结点有：E, F, G
F 结点的祖先结点有：B, A；子孙结点有：K, L
该树的深度为：4；树的宽度为：6

2. 历年竞赛真题与解析

【NOIP2019 普及组】

题目：一棵二叉树如下图所示。若采用顺序存储结构，即用一维数组元素存储该二叉树中的结点（根结点的下标为 1，若某结点的下标为 $i$，则其左孩子位于下标 $2i$ 处、右孩子位于下标 $2i+1$ 处），则该数组的最大下标至少为（）。

                           [ A ] (1)
                          /     \
                      [ B ](2)  [ F ] (3)
                         \         \
                        [ C ](5)   [ G ] (7)
                        /   \         \
                    [ D ](10)[ E ](11)[ H ] (15)

选项：A. 6 B. 10 C. 15 D. 12
答案：C
解析：根据题目给定的规则可知，下标最大的结点为树中深度最大且最靠右的结点（即结点 H），其下标的推导过程为：
- 根结点 A 的下标为 $1$；
- A 的右孩子 F 的下标为 $1 \times 2 + 1 = 3$；
- F 的右孩子 G 的下标为 $3 \times 2 + 1 = 7$；
- G 的右孩子 H 的下标为 $7 \times 2 + 1 = 15$。因此，该数组的最大下标至少为 15。

【NOIP2019 普及组】

题目：假设一棵二叉树的后序遍历序列为 DGJHEBIFCA，中序遍历序列为 DBGEHJACIF，则其前序遍历序列为（） * 选项：A. ABCDEFGHIJ B. ABDEGHJCFI C. ABDEGJHCFI D. ABDEGHJFIC * 答案：B * 解析： 1. 后序遍历的最后一位是根结点，故 A 是整棵树的根。 2. 在中序遍历中找到 A，其左侧 DBGEHJ 为左子树，右侧 CIF 为右子树。 3. 左子树对应后序序列为 DGJHEB（末尾为 B，故 B 是左子树根）。 4. 在中序 DBGEHJ 中，B 左侧为 D（左子树），右侧 GEHJ（右子树）。 5. 依此类推递归建树，最后按“根-左-右”顺序前序遍历，即可求得答案为 ABDEGHJCFI。

【NOIP2018 普及组】

题目：根节点深度为 0，一棵深度为 $h$ 的满 $k（k>1）$叉树，即除最后一层无任何子节点外，每一层上的所有结点都有 $k$ 个子结点的树，共有（）个结点。 * 选项：A. $(k^{h+1}-1)/(k-1)$ B. $k^{h-1}$ C. $k^h$ D. $(k^{h-1})/(k-1)$ * 答案：A * 解析：深度为 $h$ 的树（根节点深度为 0），其各层节点数呈等比数列： $$s = k^0 + k^1 + k^2 + \dots + k^h$$ 利用等比数列求和公式，可得总节点数： $$s = \frac{k^{h+1} - 1}{k - 1}$$

【NOIP2018 提高组】

题目：下列说法中，是树的性质的有（）。【不定项选择】 * 选项：A. 无环 B. 任意两个结点之间有且只有一条简单路径 C. 有且只有一个简单环 D. 边的数目恰是顶点数目减 1 * 答案：ABD

【NOIP2016 提高组】

题目：一棵二叉树如右图所示（共有6个结点），若采用二叉树链表存储该二叉树。如果没有左孩子或者右孩子，则对应的为空指针。那么该链表中空指针的数目为（）。 * 选项：A. 6 B. 7 C. 12 D. 14 * 答案：B * 解析：对于具有 $n$ 个结点的二叉树，其二叉链表共有 $2n$ 个指针域。其中，除根结点以外的 $n-1$ 个结点都有指针指向它们（即非空指针有 $n-1$ 个）。空指针的数目 = $2n - (n - 1) = n + 1$。本题中 $n = 6$，因此空指针数目为 $6 + 1 = 7$。

3. 精选自测题（树和二叉树习题 1 & 2）

单项选择题

下列说法中正确的是（）
- A．任何一棵二叉树中至少有一个结点的度为 2
- B．任何一棵二叉树中每个结点的度都为 2
- C．任何一棵二叉树中的度肯定等于 2
- D．任何一棵二叉树中的度可以小于 2
- 答案：D （例如空树、只有根结点的树，其度均小于 2）
若二叉树有10个度为2的结点，5个度为1的结点，则度为0的结点个数为（）
- A. 9 B. 11 • C. 15 D. 不确定
- 答案：B （根据公式 $n_0 = n_2 + 1$，已知 $n_2 = 10$，所以 $n_0 = 11$）
一棵完全二叉树上有 1001 个结点，其中叶子结点的个数是（）
- A. 250 B. 500 C. 254 D. 505 E. 以上都不对
- 答案：E （计算过程：完全二叉树中，度为1的结点个数 $n_1$ 只能是 0 或 1。由于总结点数 $1001$ 为奇数，故 $n_1 = 0$。根据公式 $n = n_0 + n_1 + n_2$ 以及 $n_2 = n_0 - 1$，得 $1001 = n_0 + 0 + n_0 - 1 \Rightarrow 2n_0 = 1002 \Rightarrow n_0 = 501$。选项中无 501，故选 E）
已知一棵二叉树的前序遍历结果为 ABCDEF，中序遍历结果为 CBAEDF，则后序遍历的结果为（）
- A. CBEFDA B. FEDCBA C. CBEDFA D. 不定
- 答案：A
在二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序（）
- A. 都不相同 B. 完全相同 C. 先序和中序相同，而与后序不同 D. 中序和后序相同，而与先序不同
- 答案：B

填空题

深度为 $k$ 的完全二叉树至少有 $2^{k-1}$ 个结点，至多有 $2^k - 1$ 个结点。
高度为 8 的完全二叉树至少有 $64$ 个叶子结点。
- (解析：第1层到第7层是满二叉树，共 $2^7-1=127$ 个结点。第8层至少有 $1$ 个结点。根据叶子结点计算：$2^{8-2} - 1 + 1 + 1 = 64$)
具有 $n$ 个结点的二叉树中，一共有 $2n$ 个指针域，其中 $n-1$ 个指向孩子，其余 $n+1$ 个为 NULL。
二叉树的先序序列和中序序列相同的条件是：任何结点至多只有右子树，没有左子树或是空树；二叉树的中序序列和后序序列相同的条件是：任何结点至多只有左子树，没有右子树或是空树；二叉树的先序序列和后序序列相同的条件是：只有根结点。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com

第4章 树与二叉树

第4章 树和二叉树

第一部分：知识点整理

1. 常见的数据结构分类

2. 树（Tree）的基本概念与术语说明

树的基本术语对照解析：

3. 树的表示方法与 C++ 实现

C++ 代码：孩子-兄弟表示法

4. 二叉树（Binary Tree）的定义与类型

(1) 二叉树的定义

(2) 满二叉树与完全二叉树的文本形态对比

5. 二叉树的性质

6. 二叉树的存储结构与 C++ 实现

C++ 代码：二叉链表实现

7. 二叉树的遍历方案

第二部分：题目与练习

1. 课本基础练习题（对应 PDF 第 4 页）

练习题：参照下图，回答下列问题

2. 历年竞赛真题与解析

【NOIP2019 普及组】

【NOIP2019 普及组】

【NOIP2018 普及组】

【NOIP2018 提高组】

【NOIP2016 提高组】

3. 精选自测题（树和二叉树习题 1 & 2）

单项选择题

填空题

第4章树与二叉树

第4章树和二叉树