数据结构之树与森林

树的存储结构

树的存储结构主要有顺序存储和链式存储两种方式。本节将重点介绍双亲表示法。

1. 双亲表示法

双亲表示法（Parent Representation）是一种树的存储方式，它使用数组来存储树的每个节点，并在每个节点中增加一个伪指针，指示该节点的双亲节点在数组中的位置。

基本特性：

根节点：在数组中，根节点的下标为0，且其双亲指针的值为-1（或NULL），表示其没有父节点。
非根节点：每个非根节点在数组中记录其父节点的下标。
数据结构：通过结构体定义节点和树的结构。

示意图：

(a) 一棵树

       A
      / \
     B   C
    /|   |\
   D E   F G

(b) 双亲表示

索引 | 数据 | 父节点
-------------------
  0  |  A   |  -1
  1  |  B   |   0
  2  |  C   |   0
  3  |  D   |   1
  4  |  E   |   1
  5  |  F   |   2
  6  |  G   |   2

(c) 双亲指针图示

2. 数据结构定义

#define MAX_TREE_SIZE 100 // 树中最多结点数

typedef struct {
    ElemType data; // 数据元素
    int parent;    // 双亲位置域
} PTNode; // 树的结点定义

typedef struct {
    PTNode nodes[MAX_TREE_SIZE]; // 双亲表示
    int n; // 结点数
} PTree; // 树的类型定义

3. 优缺点

优点：

快速访问父节点：可以快速获取任意节点的父节点，时间复杂度为 $O(1)$。
简单实现：结构简单，易于实现。

缺点：

查找孩子节点效率低：需要遍历整个结构来找到一个节点的所有孩子，时间复杂度为 $O(n)$，其中 $n$ 为节点数。
空间浪费：若树不平衡，部分数组空间可能会浪费，因为数组的大小是固定的。
修改操作复杂：对于添加、删除操作，可能需要移动大量元素，操作效率较低。

4. 应用场景

双亲表示法适用于以下场景：

节点数量较少的情况，尤其是当树的高度较小且结构较为平衡时。
需要频繁查找父节点的应用，如某些类型的查询和分析。
需要简单实现的数据结构，易于理解和维护。

以下是关于树的孩子表示法和孩子兄弟表示法的详细中文笔记，包括其定义、结构、优缺点及应用场景。

2. 孩子表示法

孩子表示法（Child Representation）是一种树的存储方式，采用链表来链接每个节点的孩子节点，形成线性结构。对于树中的每个节点，其孩子节点都通过一个单链表来表示。

基本特性：

每个节点：每个节点都有一个指向其第一个孩子的指针，以及指向下一个孩子的指针。
叶子节点：叶子节点的孩子链表为空表。

示意图：

(a) 孩子表示法

       A
      / \
     B   C
    /|   |
   D E   F

3. 孩子兄弟表示法

孩子兄弟表示法（Child-Sibling Representation）是将树的节点表示为二叉树的一种存储方式。每个节点包括三个部分：节点的值、指向第一个孩子的指针以及指向下一个兄弟节点的指针。通过兄弟指针，可以沿着链表找到该节点的所有兄弟节点。

基本特性：

每个节点：包括数据域、指向第一个孩子的指针和指向下一个兄弟的指针。

数据结构定义：

typedef struct CSNode {
    ElemType data; // 数据域
    struct CSNode *firstchild; // 指向第一个孩子
    struct CSNode *nextsibling; // 指向下一个兄弟
} CSNode, *CsTree; // 数据结构定义

示意图：

(b) 孩子兄弟表示法

       A
      / \
     B   C
    / \   \
   D   E   F

优缺点

孩子表示法

优点：

查找孩子节点方便：可以直接通过指针访问每个节点的孩子，时间复杂度为 $O(1)$。
简单直观：结构清晰，易于理解和实现。

缺点：

查找双亲节点困难：需要遍历每个节点的孩子链表，时间复杂度为 $O(n)$。
空间复杂性：对于稀疏树，可能会造成内存浪费。

孩子兄弟表示法

优点：

灵活性：可以方便地实现树与二叉树之间的转换。
便于查找孩子节点：使用孩子指针可以轻松找到节点的第一个孩子。
查找兄弟节点简便：通过兄弟指针可以直接访问节点的兄弟。

缺点：

查找双亲节点困难：如果没有额外的父节点指针，查找双亲节点较为复杂。
实现复杂：相较于孩子表示法，结构稍复杂。

应用场景

孩子表示法适用场景：

适用于节点数目较少且结构相对平衡的树。
需要频繁查找孩子节点的应用，如某些类型的查询和分析。

孩子兄弟表示法适用场景：

适用于树的结构动态变化较大，需要频繁进行插入和删除操作的情况。
需要在树和二叉树之间进行频繁转换的场景。
需要经常访问兄弟节点的情况。

选择题

问题 1

下列关于树的说法中，正确的是()。

I. 对于有 $n$ 个结点的二叉树，其高度为 $O(\log n)$
II. 完全二叉树中，若一个结点没有左孩子，则它必是叶结点
III. 高度为 $h$ $(h>0)$ 的完全二叉树对应的森林所含的树的个数一定是 $h$
IV. 一棵树中的叶子数一定等于与其对应的二叉树的叶子数

选项：
A. I和II
B. IV
C. III
D. II

答案： D

解释：

I 错误：对于有 $n$ 个结点的二叉树，其高度的最坏情况为 $n$（即单支树），而最佳情况为 $O(\log n)$（即平衡树）O(n)$。
II 正确：完全二叉树的特性之一是，若一个结点没有左孩子，则它必是叶结点。
III 错误：高度为 $h$ 的完全二叉树对应的森林的树的个数并不一定是 $h$，而是取决于具体的结构。
IV 错误：树中的叶子数和其对应的二叉树的叶子数可能不同，尤其在多个叶子结点共享同一双亲时。

问题 2

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

A. 指向最左兄弟
B. 指向最右兄弟
C. 一定为空
D. 不一定为空

答案： D

解释：
森林中的每棵树都可以被视为二叉树，根结点的右指针指向森林中下一棵树的根结点。如果森林中只有一棵树，则右指针为空，因此右指针不一定为空。

问题 3

设森林中有3棵树，第一、第二、第三棵树的结点个数分别为 $M_1$、$M_2$ 和 $M_3$。与森林 F 对应的二叉树根结点的右子树上的结点个数是()。

A. $M_1$
B. $M_1 + M_2$
C. $M_2$
D. $M_2 + M_3$

答案： D

解释：
森林与二叉树的转换规则是“左孩子右兄弟”。在将森林转换为二叉树时，所有的树根结点都被视为兄弟节点。因此，第一棵树的根结点的右子树上会包含第二棵和第三棵树的所有结点，所以根结点的右子树上的结点个数是 $M_2 + M_3$。

问题 4

设森林 $F$ 对应的二叉树为 $B$，它有 $m$ 个结点，$B$ 的根为 $p$，$p$ 的右子树结点个数为 $n$，森林 $F$ 中第一棵树的结点个数是()。

选项：
A. $m - n$
B. $m - n - 1$
C. $n + 1$
D. 条件不足，无法确定

答案： A

解释：
森林转换成二叉树时采用孩子兄弟表示法，根结点及其左子树为森林中的第一棵树。右子树为其他剩余的树。所以，第一棵树的结点个数为m-n。

问题 5

森林 $T = (T_1, T_2, \ldots, T_k)$ 转化为二叉树 $BT$ 的过程为：

A. 将中间子树 $T_{mid} \; (mid = (1 + m)/2)$ 的根作为 $BT$ 的根；将 $ (T_1, T_2, , T_{mid-1})$ 转换为 $BT$ 的左子树；将 $ (T_{mid+1}, , T_k)$ 转换为 $BT$ 的右子树。
B. 将子树 $T$ 的根作为 $BT$ 的根；将 $T$ 的子树森林转换成 $BT$ 的左子树；将 $ (T_2, T_3, , T_k)$ 转换成 $BT$ 的右子树。
C. 将子树 $T$ 的根作为 $BT$ 的根；将 $T$ 的左子树森林转换为 $BT$ 的左子树；将 $T$ 的右子树森林转换为 $BT$ 的右子树；其他以此类推。
D. 将森林 $T$ 的根作为 $BT$ 的根；将 $ (T_1, , T_k)$ 转化为该根下的结点，得到一棵树，然后将这棵树再转化为二叉树 $BT$。

答案： B

解释：
在将森林转化为二叉树的过程中，我们通常采用“左孩子右兄弟”的规则。具体而言，森林中每棵树的根节点被视为兄弟节点关系，并将第一个树的根设为二叉树的根。因此，答案是将子树的根作为二叉树的根，右子树由其他树的根组成。

问题 6

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

选项：
A. $n - 1$
B. $n$
C. $n + 1$
D. $n + 2$

答案： C

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

问题 7

若 $T$ 是由有序树 $T$ 转换而来的二叉树，则 $T$ 中结点的后根序列就是 $T$ 中结点的( )序列。

选项：
A. 先序
B. 中序
C. 后序
D. 层序

答案： B

解释： 如图，满足中序遍历。

问题 8

某二叉树结点的中序序列为 BDAECF，后序序列为 DBEFCA，则该二叉树对应的森林包括( )棵树。

选项：
A. 1
B. 2
C. 3
D. 4

答案： C

解释：

画出图形，之后根据左孩子右兄弟进行划分。

问题 9

设 $X$ 是树 $T$ 中的一个非根结点，$B$ 是 $T$ 所对应的二叉树。在 $B$ 中，$X$ 是其双亲结点的右孩子，下列结论中正确的是( )。

选项：
A. 在树 $T$ 中，$X$ 是其双亲结点的第一个孩子
B. 在树 $T$ 中，$X$ 一定无右边兄弟
C. 在树 $T$ 中，$X$ 一定是叶子结点
D. 在树 $T$ 中，$X$ 一定有左边兄弟

答案： D

解释：
在二叉树 $B$ 中，$X$ 是其双亲的右孩子，因此在树 $T$ 中，$X$ 必定有一个左兄弟。因为二叉树的结构是左孩子在前，右孩子在后，所以如果 $X$ 是右孩子，它必然有左孩子。

问题 10

在森林的二叉树表示中，结点 $M$ 和结点 $N$ 是同一父结点的左儿子和右儿子，则在该森林中( )。

选项：
A. $M$ 和 $N$ 有同一双亲
B. $M$ 和 $N$ 可能无公共祖先
C. $M$ 是 $N$ 的儿子
D. $M$ 是 $N$ 的左兄弟

答案： B

解释：
在森林的二叉树表示中，如果 $M$ 和 $N$ 是同一父结点的左儿子和右儿子，意味着它们在同一棵树中。因此，$M$ 和 $N$ 不可能有公共祖先，如果它们的父结点是二叉树的根结点。因此，答案为 $M$ 和 $N$ 可能无公共祖先。

以下是关于森林与二叉树转换的相关选择题，包括问题、选项、正确答案和解释。

问题 11

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

选项：
A. 只有 I
B. I 和 II
C. I 和 III
D. I、II 和 III

答案： B

解释：
在森林与二叉树的转换中，父子关系在对应的森林关系中可能是兄弟关系或原本就是父子关系。具体情况分析如下：

情形 I: $v$ 是 $u$ 的第一个孩子，符合要求。
情形 II: $u$ 和 $v$ 是兄弟结点的关系，即 $v$ 是 $u$ 的第二个孩子。在转换时，$v$ 成为 $u$ 的第一个孩子的右孩子，也符合要求。
情形 III: $u$ 的父结点与 $v$ 的父结点是兄弟关系，虽然这不能使 $u$ 是 $v$ 的父结点的父结点，因此不符合。综上，只有情形 I 和 II 成立，因此答案为 B。

问题 12

已知一棵有 2011 个结点的树，其叶结点个数为 116，该树对应的二叉树中无右孩子的结点个数是( )。

选项：
A. 115
B. 116
C. 1895
D. 1896

答案： D

解释：
在转换为二叉树时，每个分支结点的所有子结点中的最右子结点无右孩子，根结点转换后也没有右孩子。无右孩子的结点个数可以通过以下公式计算： $ = + 1 = 2011 - 116 + 1 = 1896 $ 因此答案为 D。

问题 13

将森林 $F$ 转换为对应的二叉树 $T$，$F$ 中叶结点的个数等于( )。

选项：
A. $T$ 中叶结点的个数
B. $T$ 中度为 1 的结点个数
C. $T$ 中左孩子指针为空的结点个数
D. $T$ 中右孩子指针为空的结点个数

答案： C

解释：
在将森林转换为二叉树时，原森林中的叶结点在转换后仍然是叶结点。因此，原森林中叶结点的个数等于转换后二叉树中左孩子指针为空的结点个数，因为每个叶子结点在二叉树中都没有左子树。故选择 C。

以下是关于森林与二叉树转换的相关选择题，包括问题、选项、正确答案和解释。

问题 14

若森林 $F$ 有 15 条边、25 个结点，则 $F$ 包含树的个数是( )。

选项：
A. 8
B. 9
C. 10
D. 11

答案： C

解释：
树有一个很重要的性质，即在n个结点的树中有n-1条边，“那么对于每棵树，其结点数比边数多1”。题中的森林中的结点数比边数多10(即 25-15=10)，显然共有 10棵树。

问题 15

若将一棵树 $T$ 转化为对应的二叉树 $BT$，则下列对 $BT$ 的遍历中，其遍历序列与 $T$ 的后根遍历序列相同的是( )。

选项：
A. 先序遍历
B. 中序遍历
C. 后序遍历
D. 按层遍历

答案： B

解释：
上面写过的中序遍历。

问题 16

已知森林 $F$ 及与之对应的二叉树 $T$，若 $F$ 的先根遍历序列是 $a, b, c, d, e, f$，中根遍历序列是 $b, a, d,f， e, c$，则 $T$ 的后根遍历序列是( )。

选项： b,f,e,d,c,a。

答案： B

解释：
根据先根遍历和中根遍历可以构造出二叉树结构。通过先根序列 $a$ 为根节点，在中根序列中 $b, d, e$ 在 $a$ 的左边，$c$ 在右边，可以得到二叉树的结构。由此，得到后根遍历序列为 $b, d, e, c, a$，所以答案为 B。

问题 17

某森林 $F$ 对应的二叉树为 $T$，若 $T$ 的先序遍历序列是 $a, b, d, c, e, g, f$，中序遍历序列是 $b, d, a, e, g, c, f$，则 $F$ 中树的棵数是( )。

选项：
A. 1
B. 2
C. 3
D. 4

答案： C

解释：
通过先序遍历和中序遍历可以构造出二叉树的结构。根据构造，T中的结点a、c、f为F中树的根结点

综合应用题

01. 问题

给定一棵树的先根遍历序列和后根遍历序列，能否唯一确定一棵树？若能，请举例说明；若不能，请给出反例。

一棵树的先根遍历结果与其对应二叉树的先序遍历结果相同，树的后根遍历结果与其对应二叉树表示的中序遍历结果相同。

由于二叉树的先序序列和中序序列能够唯一地确定这棵二叉树，因此，根据题目给出的条件，利用树的先根遍历序列和后根遍历序列能够唯一地确定这棵树。

02. 问题

将下面一个由 3 棵树组成的森林转换为二叉树。

03. 问题

已知某二叉树的先序序列和中序序列分别为：

先序序列：ABDEHCFIMGJKL
中序序列：DBHEAIMFCGKLJ

最后根据左孩子右兄弟可以得到。

04. 问题

解答

当森林（树）以孩子兄弟表示法存储时，若节点没有孩子（fch == NULL），则它必是叶子。总的叶子节点个数是孩子子树（fch）上的叶子数和兄弟子树（nsib）上的叶子节点个数之和。以下是具体的算法代码实现：

typedef struct node {
    // 数据域
    ElemType data;
    // 孩子与兄弟域
    struct node* fch;  // 第一个孩子
    struct node* nsib; // 下一个兄弟
} *Tree;

// 计算以孩子兄弟表示法存储的森林的叶子数
int Leaves(Tree t) {
    // 树为空返回0
    if (t == NULL) 
        return 0;
    
    // 若节点无孩子，则该节点必是叶子
    if (t->fch == NULL) 
        return 1 + Leaves(t->nsib); // 返回叶子节点和其兄弟子树中的叶子节点数
    
    // 递归计算孩子子树和兄弟子树中的叶子数之和
    return Leaves(t->fch) + Leaves(t->nsib);
}

代码解释

数据结构定义：定义了 node 结构体，包含数据域和两个指针，分别指向第一个孩子和下一个兄弟。
Leaves 函数：
- 首先检查树是否为空，若为空，则返回 0。
- 检查当前节点是否有孩子，若没有孩子，则当前节点是叶子节点，返回 1 加上兄弟子树的叶子节点数。
- 如果有孩子，则递归计算孩子子树和兄弟子树中的叶子节点数之和。

05. 问题

以孩子-兄弟链表为存储结构，设计递归算法求树的深度。

解答

由孩子-兄弟链表表示的树，求高度的算法思想如下：采用递归算法，若树为空，则高度为零；否则，高度为第一子女树高度加1和兄弟子树高度中的较大者。以下是具体的算法代码实现：

typedef struct node {
    // 数据域
    ElemType data;
    // 孩子与兄弟域
    struct node* firstchild;   // 第一个孩子
    struct node* nextsibling;   // 下一个兄弟
} *CsTree;

// 递归求以孩子-兄弟链表表示的树的深度
int Height(CsTree bt) {
    // 如果树为空，返回0
    if (bt == NULL) 
        return 0;

    // 计算第一子女树的高度
    int hc = Height(bt->firstchild);
    // 计算兄弟树的高度
    int hs = Height(bt->nextsibling);

    // 返回高度的最大值 + 1
    return (hc > hs ? hc : hs) + 1;
}

代码解释

数据结构定义：定义了 node 结构体，包含数据域和两个指针，分别指向第一个孩子和下一个兄弟。
Height 函数：
- 首先检查树是否为空，若为空，则返回 0。
- 递归计算第一个孩子的高度 hc 和兄弟的高度 hs。
- 返回 hc 和 hs 中较大值加 1（表示当前节点的高度）。

06.问题

已知一棵树的层次序列及每个结点的度，编写算法构造此树的孩子-兄弟链表。

解答

我们可以根据给定的层次序列和各个结点的度，逐个链接结点以构建树的孩子-兄弟链表。下面是具体的算法实现：

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

#define maxNodes 15

typedef char DataType; // 数据类型定义
typedef struct csNode {
    DataType data; // 数据域
    struct csNode* firstchild; // 第一个孩子
    struct csNode* nextsibling; // 下一个兄弟
} *csTree;

void createCSTree(csTree* T, DataType e[], int degree[], int n) {
    // 根据树结点的层次序列 e[] 和各结点的度 degree 构造树的孩子-兄弟链表
    csNode* pointer = (csNode*)malloc(maxNodes * sizeof(csNode)); // 动态分配内存

    for (int i = 0; i < n; i++) {
        pointer[i] = (csNode*)malloc(sizeof(csNode)); // 为每个结点分配内存
        pointer[i]->data = e[i]; // 赋值数据
        pointer[i]->firstchild = NULL; // 初始化孩子指针
        pointer[i]->nextsibling = NULL; // 初始化兄弟指针
    }

    int k = 0; // k为子女结点序号
    for (int i = 0; i < n; i++) {
        int d = degree[i]; // 结点 i 的度数
        if (d > 0) {
            // 建立结点 i 与其第一个子女 k 之间的链接
            pointer[i]->firstchild = pointer[k + 1]; // k+1是第一个子女的索引
            k++; // 更新子女结点序号
            for (int j = 2; j <= d; j++) {
                k++;
                pointer[k - 1]->nextsibling = pointer[k]; // 建立兄弟结点之间的链接
            }
        }
    }

    *T = pointer[0]; // 返回树的根结点
    free(pointer); // 释放临时数组
}

int main() {
    csTree tree;
    DataType e[maxNodes] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'}; // 层次序列
    int degree[maxNodes] = {3, 0, 2, 0, 0, 1, 0}; // 各结点的度
    int n = 7; // 结点个数

    createCSTree(&tree, e, degree, n);

    // 进一步操作或测试树...

    return 0;
}

代码解释

数据结构定义：
- csNode 结构体用于表示树的结点，包含数据域、指向第一个孩子的指针和指向下一个兄弟的指针。
createCSTree 函数：
- 接受一个指向树的指针、层次序列和度数组以及结点数量。
- 使用动态内存分配为每个结点分配内存，并初始化各个指针。
- 根据度数建立每个结点与其第一个子女的链接，并将兄弟结点链接起来。
主函数：
- 定义了层次序列和度数组，调用 createCSTree 函数构造树。

07. 问题

若一棵非空 $ k $（$ k > 2 $）叉树 $ T $ 中的每个非叶节点都有 $ k $ 个孩子，回答下列问题并给出推导过程。

解答

若 $ T $ 有 $ m $ 个非叶节点，则 $ T $ 中的叶节点有多少个？

在正则 $ k $ 叉树中，结点分为两类：叶结点（个数记为 $ n $）和度为 $ k $ 的分支结点（个数记为 $ m $）。对于一棵树 $ T $，我们有以下关系：
- 树的边数 $ e = n + m - 1 $（其中 $ n $ 是叶子结点数，$ m $ 是非叶子结点数，$ n + m $ 是总结点数，树有 $ n + m - 1 $ 条边）
- 每个非叶子结点有 $ k $ 个孩子，因此从 $ m $ 个非叶节点发出的边数为 $ e = mk $。
由此，我们可以得到以下方程：

$ n + m - 1 = mk $

整理得：

$ n = (k - 1)m + 1 $

所以，树 $ T $ 中的叶节点数为：

$ n = (k - 1)m + 1 $
若 $ T $ 的高度为 $ h $（单节点的树 $ h = 1 $），则 $ T $ 的节点数最多和最少分别为多少个？
- 最多结点数：当树是“满”树时，除了最后一层，每层都有 $ k $ 倍于上一层的结点数。
  - 第 $ j $ 层的结点数为 $ k^{j-1} $，$ j $ 从 1 到 $ h $。
  - 因此，总结点数 $ M $ 为：
  $ M = 1 + k + k^2 + + k^{h-1} = $
- 最少结点数：最少结点数的情况下，树的结构为：
  - 第一层有 1 个根结点；
  - 第二层有 1 个分支结点，其余为叶结点；
  - 之后的每一层有 1 个分支结点和 $ k - 1 $ 个叶结点。
  所以，总结点数 $ M $ 为：
  
  $ M = 1 + (h - 1)k $