树

需掌握树的概念和存储结构，以及与森林和二叉树之间的转换，在选择题中考察。

树的基本概念

结点属性

  • 双亲（parent）：如果一个结点包含子结点，则该结点被称为其子结点的双亲。
  • 兄弟（sibling）：具有相同双亲结点的结点互称为兄弟结点。
  • 孩子（child）：一个结点直接连接到另一个结点，并且位于较低的层级，则该结点被称为子结点或孩子。

度

A
B
C
D
E
F
L
M
H
I
J
K
G
结点
度
A, D
3
B, G
2
C, E
1
K, F, L, M, H, I, J
0
树的度 = max(结点度) = 3
  • 结点的度：结点的孩子数量
  • 树的度：等于树中所有结点度的最大值
  • 分支结点（非终端结点）：度大于 0 的结点
  • 叶子结点（终端结点）：度等于 0 的结点

深度

A
B
C
D
E
F
L
M
H
I
J
K
G
Depth 0
Depth 1
Depth 2
Depth 3
结点
深度
A
0
B, C, D
1
E, F, G, H, I, J
2
K, L, M
3
树的深度 = 3
  • 树的深度（Depth）：从根结点到最远叶子结点的最长路径上的边的数量。
  • 结点的深度：是指从根结点到该结点的路径长度。

高度

A
B
C
D
E
F
L
M
H
I
J
K
G
结点
高度
A
3
B, C
2
D, E, G
1
F, H, I, J, K, L, M
0
树的高度 = 3
0
0
0
0
0
0
0
1
1
1
2
2
3
  • 树的高度（Height）：从根结点到最远叶子结点的最长路径上的边的数量。
  • 结点的高度：从该结点到其最远叶子结点的最长路径上的边的数量。
注意

深度定义是从上往下的，高度定义是从下往上的。

一般不用在意这个，因为树的高度和深度是相同的，但是结点的高度和深度可能会不同。

路径

A
B
C
D
E
F
L
M
H
I
J
K
G
结点
权重
深度
F
H
I
J
K
L
M
5
3
8
7
11
15
2
2
2
2
2
3
3
3
带权路径长度
10
6
16
14
33
45
6
树的带权路径长度 = 10 + 6 + 16 + 14 + 33 + 45 + 6 = 130
  • 路径：在一棵树中，从一个结点到另一个结点所经过的所有结点，被称为这两个结点之间的路径。
  • 结点的权：每个结点被赋予的一个数值，通常表示该结点的重要性或频率。
  • 结点的带权路径长度：从根结点到该结点的路径长度与该结点权值的乘积。
  • 树的带权路径长度：所有叶子结点的带权路径长度之和。

树的存储结构

树的存储结构是指在计算机中如何表示和存储树这种数据结构， 这里主要了解双亲表示法、孩子表示法 和 孩子兄弟表示法即可。

双亲表示法

双亲表示法主要是使用一个数组，其中每个结点都有一个指示其双亲结点在数组中位置的索引。

#define MAXSIZE 100
typedef struct {
    int data;         // 结点数据
    int parent;       // 双亲的位置
} PTNode;

typedef struct {
    PTNode nodes[MAXSIZE];  // 结点数组
    int n;                  // 结点数
} PTree;
A
B
C
D
E
F
G
H
I
J
A
-1
B
0
C
0
D
0
E
1
F
1
G
3
H
6
I
6
J
6
Data
Parent
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
G
H
I
J
Tree
Data Structure
Representation

孩子表示法

孩子表示法将每个结点的孩子结点排列起来，以单链表作为存储结构。然后再用一个数组与之相配合。

#define MAXSIZE 100

// 孩子结点
typedef struct ChildNode {
    int child;                   // 孩子结点在数组中的位置
    struct ChildNode* next;     // 下一个孩子
} *ChildPtr;

// 表头结构
typedef struct {
    int data;                   // 结点数据
    ChildPtr firstchild;        // 第一个孩子的指针
} CTBox;

typedef struct {
    CTBox nodes[MAXSIZE];       // 结点数组
    int n;                      // 结点数
} CTree;
A
B
C
D
E
F
G
H
I
J
Tree
0
A
1
B
2
C
3
D
4
E
5
F
6
G
7
H
8
I
9
J
1
4
2
5
3
6
7
8
9
Representation

孩子兄弟表示法

孩子兄弟表示法是将树转化为二叉树的形式来存储。每个结点有两个指针，一个指向它的第一个孩子，另一个指向它的右兄弟。

typedef struct CSNode {
    int data;                     // 结点数据
    struct CSNode* firstchild;   // 第一个孩子
    struct CSNode* rightsib;     // 右兄弟
} CSNode, *CSTree;
A
B
C
D
E
F
G
H
I
J
Tree
A
^
B
^
E
^
F
^
C
D
^
^
H
^
I
^
J
^
G
^
Representation

森林的基本概念

森林（Forest）是一组互不相交的树的集合。换句话说，森林由若干棵树组成，每棵树都是一个独立的层次结构，且这些树之间没有连接关系。

B
D
E
F
I
J
C
G
H
K
  • 森林与树的区别：
    • 一棵树只有一个根结点，而森林可以有多个根结点（每棵树一个）。
    • 森林可以看作是多个树的并集，树是森林的一个特例（森林中只有一棵树）。
  • 森林的深度：森林中所有树的最大高度（从根到最远叶结点的路径长度）。

树、森林和二叉树的转换

树转化为二叉树

  • 若树的根结点有孩子，那么第一个孩子是二叉树的左孩子，其他的孩子结点依次作为前一个孩子结点的右孩子。
  • 对每个孩子执行上述步骤。
A
B
C
D
E
F
G
A
B
C
D
E
F
G
树转化为二叉树

森林转二叉树

  • 把森林中的每一棵树转换为二叉树。
  • 第一棵二叉树不动，从第二棵二叉树开始，依次将后一棵二叉树的根作为前一棵二叉树的右孩子。其结果是一个二叉树。
A
B
C
D
E
F
G
H
I
A
B
C
D
E
F
G
H
I
A
B
C
D
E
F
G
H
I
森林转化为二叉树

树和森林的遍历

树的遍历

对于一个给定的树，通常有以下两种遍历方式：

  1. 先根遍历（类似于二叉树的前序遍历）：
    • 访问树的根结点。
    • 递归地先根遍历根的每一棵子树。
  2. 后根遍历（类似于二叉树的后序遍历）：
    • 递归地后根遍历根的每一棵子树。
    • 访问树的根结点。

注意树是没有中根遍历的，除非这棵树是二叉树。

#define MAXCHILD 20

typedef struct TreeNode {
    int value;
    int numChildren; // 子结点的数量
    struct TreeNode *children[MAXCHILD]; // 子结点指针数组
} TreeNode;
void preOrderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    // 先访问根结点
    // 然后遍历子结点
    for (int i = 0; i < root->numChildren; ++i) {
        preOrderTraversal(root->children[i]);
    }
}
void postOrderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }

    // 先遍历子结点
    for (int i = 0; i < root->numChildren; ++i) {
        postOrderTraversal(root->children[i]);
    }
    // 然后访问根结点
}

对于上图所示的树：其先根遍历为 A, B, E, F, C, D, G，后根遍历为E, F, B, C, G, D, A。

观察可以得到如下结论：

  • 树的先根遍历和其对应的二叉树的先序遍历相同
  • 树的后根遍历和其对应的二叉树的中序遍历相同

森林的遍历

对于一个给定的森林，遍历方式如下：

  1. 先根遍历（与树的先根遍历相似）：依次先根遍历森林中的每一棵树。
  2. 后根遍历（与树的后根遍历相似）：依次后根遍历森林中的每一棵树。
  3. 中根遍历（普通的树构成的森林是不存在中序遍历的，这里的中序遍历指代的是二叉树森林）：依次中序遍历森林中的每一棵二叉树。

对于上图所示的森林：其先根遍历为 A, B, C, D, E, F, G, H, I，后根遍历为 B, C, D, A, F, E, H, I, G，中根遍历为 B, C, D, A, F, E, H, I, G

观察可以得到如下结论：

  • 森林的先根遍历和其对应的二叉树的先序遍历相同
  • 森林的中根遍历和其对应的二叉树的中序遍历相同