第十章 树

思维导图：

1.树的定义和树的存储结构

1.1 树的定义

1.1.1 定义

树（Tree）是n（n>=0）个节点的有限集。当n=0时称为空树。在任意一棵非空树中：

有且仅有一个特定的被称为根（Root）的节点
当n>1时，其余节点可分为m（m>0）个互不相交的有限集T1、T2、……、Tm，其中每个集合本身又是一棵树，并且称为根的子树（SubTree），如下图所示：

对于上面这棵树而言，A是它的根节点，左侧橙色部分和右侧黄色部分分别是这棵树的两个子树，而分别在以B、C为根节点的子树中还有子树，所以我们可以说树是递归定义的，树的特性对于它们的子树以及子树的子树而言同样是适用的。

对于树的定义有3点需要特别强调一下：

层次结构：树具有根节点、子节点和叶节点，呈现出一种分层的结构。
无环性：树是一种无环结构，即0任意两个节点之间只有唯一的一条路径。
单一根节点：树只有一个根节点，从根节点可以访问树中的所有其他节点。
1.2 节点的关系和分类
对于一棵树而言，里边有一些常用概念是需要大家掌握的：

节点（Node）：树中的每个元素称为节点，即图中的A、B、C、...、H、I、J。
根节点（Root Node）：树的顶层节点，没有父节点，即图中的节点A。
父节点（Parent Node）：直接连接某个节点的上层节点。比如:
B、C节点的父节点为根节点A
E、F节点的父节点为节点C
G、H、I节点的父节点为根节点D
子节点（Child Node）：由某个节点直接连接的下层节点。比如:
A节点的子节点为节点B、C
C节点的子节点为节点E、F
D节点的子节点为节点G、H、I
子孙节点：以某节点为根的子树中的任意节点都是该节点的子孙
叶子节点（Leaf Node）：没有子节点的节点。图中的G、H、I、J就是叶子节点。
兄弟节点（Sibling Nodes）：具有相同父节点的节点。
堂兄弟节点：在树中的层次相同，但是父节点不同。举例：
节点D和节点E、F互为堂兄弟节点
节点G、H、I和节点、J互为堂兄弟节点
层次（Level）：从根开始定义，根为第一层，根的孩子为第二层，以此类推。图中相同颜色的节点表示相同的层次，从根节点向下一共四层。
路径（Path）：从一个节点到另一个节点所经过的节点序列。
高度（Height）：节点到叶节点的最长路径长度。
从根节点到叶子节点得到的高度就是树的高度
根节点A到叶子节点F的高度是3，到叶子节点G、H、I、J的高度是4，所以根节点的高度是4，树的高度也是4
深度（Depth）：节点到根节点的路径长度。比如：
从A_{E深度为3，从A}H深度为4
子树（Subtree）：由一个节点及其所有后代节点组成的树。
度（Degree）：节点的子节点数量，树的度是所有节点度的最大值。
叶子节点的度为0
树的度是树内各个节点度的最大值
节点E的度为1，节点A的度为2，节点D的度为3，树的度为3
有序树/无序树：如果树以及它的子树中所有子节点从左至右是有次序的，不能互换的，此时将这棵树称为有序树，否则称为无序树。
森林（Forest）：m（m>=0）棵互不相交的树的集合。
线性表与树结构有很多地方是不同的，下表是关于二者的对比：

位置 线性结构 树结构
第一个元素/根节点 无前驱 无双亲, 唯一
最后一个元素/叶子节点 无后继 无孩子, 可以有多个
中间元素/节点 一个前驱, 一个后继 一个双亲多个孩子
温馨提示：上表中所说的双亲（Parent）就是当前节点的父节点，只有一个而不是两个。

2. 树的存储结构
   关于数到存储结构和线性表一样有两种：线性存储和链式存储。先看顺序存储结构，如果是线性表可以用一段连续的存储单元一对一的进行数据元素的存储，对于树这种一对多的结构应该如何进行存储呢？

在数据结构中，树的表示法有多种，常见的包括双亲表示法、孩子表示法和孩子兄弟表示法。每种表示法都有其优点和适用的场景。下面详细介绍这些表示法。

2.1 双亲表示法
双亲表示法是一种用数组来表示树的方法，在存储树节点的时候，在每个节点中附设一个指示器指示其双亲节点在数组中的位置。

基于上面的描述，我们需要定义出这样的一个树节点结构（假设节点存储的数据是整形）：

C++
1
2
3
4
5
struct TreeNode
{
int data;
int parent;
};
data：节点存储的数据
parent：父节点在数组中的位置，根节点没有父节点，用 -1 表示
我们可以通过一个表格来直观的描述一下节点在数组中的关系：

下标 data parent
0 A -1
1 B 0
2 C 0
3 D 1
4 E 2
5 F 2
6 G 3
7 H 3
8 I 3
9 J 4
我们来看一段示例代码：

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

include

include

// 定义树节点结构
struct TreeNode
{
int value; // 节点的值
int parent; // 父节点的索引

TreeNode(int val, int par) : value(val), parent(par) {}

};

// 添加节点的函数
void addNode(std::vector& tree, int value, int parentIndex)
{
tree.push_back(TreeNode(value, parentIndex));
}

int main()
{
std::vector tree;

// 创建根节点，根节点的父节点索引为 -1
addNode(tree, 1, -1); // 索引 0
addNode(tree, 2, 0);  // 索引 1
addNode(tree, 3, 0);  // 索引 2
addNode(tree, 4, 1);  // 索引 3
addNode(tree, 5, 1);  // 索引 4

// 输出树的结构
for (size_t i = 0; i < tree.size(); ++i) 
{
    std::cout << "Node value: " << tree[i].value;
    if (tree[i].parent != -1) 
    {
        std::cout << ", Parent value: " << tree[tree[i].parent].value;
    }
    else {
        std::cout << ", This is the root node.";
    }
    std::cout << std::endl;
}

return 0;

}
输出的结果如下:

C++
1
2
3
4
5
Node value: 1, This is the root node.
Node value: 2, Parent value: 1
Node value: 3, Parent value: 1
Node value: 4, Parent value: 2
Node value: 5, Parent value: 2
通过测试输出的日志信息可知，我们可以快速的通过每个节点中的parent域找到它们的父节点（也就是双亲节点），时间复杂度为O(1)。但是如果我们想知道当前节点的子节点是谁，就需要遍历整棵树才能得到结果。

如果我们对上面的TreeNode结构进行优化给它添加用于描述孩子节点位置的成员就可以快速找到当前节点的子节点了:

C++
1
2
3
4
5
6
7
8
9
10
struct TreeNode
{
int data;
int parent;
int child1;
int child2;
...
...
...
};
但是此时问题来了，对于一棵树中的节点而言，我怎么知道它有多少个子节点呢？如果child成员定义的太多会浪费存储空间，如果定义的太少就不能存储所有的子节点信息。这该如何是好呢？

2.2 孩子表示法
孩子表示法是一种为每个节点存储其所有子节点的表示方法，在存储的时候可以使用数组也可以使用链表。

孩子表示法中，每个节点都有一个指针列表或数组，指向它的所有子节点。我们可以使用 std::vector 来存储子节点指针。关于节点结构可以这样定义：

C++
1
2
3
4
5
struct TreeNode
{
int value;
std::vector<TreeNode*> children;
};
value：节点的值，可以根据实际需求修改为其他数据类型
children：子节点列表，存储的是当前节点所有的子节点
如果想要根据上面的树节点结构构造这样一棵树，代码应该怎么写呢？

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

include

include

using namespace std;

struct TreeNode
{
int value; // 节点的值
vector<TreeNode*> children; // 子节点列表

TreeNode(int val) : value(val) {}

};

// 添加子节点的函数
void addChild(TreeNode* parent, TreeNode* child)
{
parent->children.push_back(child);
}

int main()
{
// 创建节点
TreeNode* root = new TreeNode(1);
TreeNode* child1 = new TreeNode(2);
TreeNode* child2 = new TreeNode(3);
TreeNode* child3 = new TreeNode(4);
TreeNode* child4 = new TreeNode(5);
TreeNode* child5 = new TreeNode(6);
TreeNode* child6 = new TreeNode(7);
TreeNode* child7 = new TreeNode(8);

// 构建树
addChild(root, child1);
addChild(root, child2);
addChild(root, child3);
addChild(child2, child4);
addChild(child2, child5);
addChild(child1, child6);
addChild(child3, child7);

vector<TreeNode*> nodes;
nodes.emplace_back(root);
nodes.emplace_back(child1);
nodes.emplace_back(child2);
nodes.emplace_back(child3);

// 输出根节点的子节点值
for (auto node : nodes)
{
    for (auto child : node->children)
    {
        cout << "parent value: " << node->value << ", Child value: " << child->value << endl;
    }
}

// 释放内存（在实际应用中应注意内存管理）
delete root;
delete child1;
delete child2;
delete child3;
delete child4;
delete child5;
delete child6;
delete child7;

return 0;

}
在上面的程序中先创建了若干个树节点，然后通过 addChild 函数将子节点添加到了父节点对应的vector容器中，通过这种方式能够非常轻松的基于父节点找到它所有的子节点，但是想要通过子节点访问其父节点就变得麻烦了。那么有没有一种方法既可以快速的通过子节点访问到它的父节点并且能够通过父节点快速访问到它的所有的子节点呢？

当然有，就是孩子双亲表示法，也就是在孩子表示法的节点基础上再添加一个指向双亲的数据域：

C++
1
2
3
4
5
6
struct TreeNode
{
int value;
TreeNode* parent;
std::vector<TreeNode*> children;
};
value：节点的值，可以根据实际需求修改为其他数据类型
parent：记录当前节点的父节点的位置（地址）。
children：子节点列表，存储的是当前节点所有的子节点
做了这样的修改之后，可以在程序中再添加一个setParent方法，用于给各个节点设置父节点（根节点的父节点可以指定为 nullptr），代码比较简单，此处就略过了，可以自己私下写一写。

2.3 孩子兄弟表示法
在孩子兄弟表示法中，树被转化为了一种特殊的树，我们可以做这样的约定：每个节点的左侧子节点表示该节点的第一个子节点，而右侧子节点表示该节点的下一个兄弟节点。也就是说在内存中这棵树的存储结构和实际的逻辑结构是不一样的。

根据描述我们可以定义这样的一个树节点：

C++
1
2
3
4
5
6
struct TreeNode
{
int value;
TreeNode* firstChild;
TreeNode* nextSibling;
};
value：节点的值，可以根据实际需求修改为其他数据类型

firstChild：指向第一个子节点（地址）

nextSibling：指向下一个兄弟节点（地址）

如果想要在内存中存储这样的一棵树，我们需要使用孩子兄弟表示法对其进行转换可以得到下面这个图：

在上面的图中红色线表示节点之间的关系为父子，绿色的线表示节点之间的关系为兄弟，但是这样看起来似乎还是不太直观，我们来换一种画法：

图中的左侧节点（橙色）表示和父节点之间原来的实际关系为父子，右侧节点（黄色）表示节点和父节点之间原来的实际关系为兄弟。可见内存中存储的树结构和实际的树结构已经完全不一样了，但是树节点中存储的属性，我们完全可以把原来的树还原出来。

示例C++代码如下：

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

include

using namespace std;

struct TreeNode
{
int value; // 节点的值
TreeNode* firstChild; // 指向第一个子节点
TreeNode* nextSibling; // 指向下一个兄弟节点

TreeNode(int val) : value(val), firstChild(nullptr), nextSibling(nullptr) {}

};

// 添加子节点的函数
void addChild(TreeNode* parent, TreeNode* child)
{
if (!parent->firstChild)
{
parent->firstChild = child;
}
else
{
TreeNode* sibling = parent->firstChild;
while (sibling->nextSibling)
{
sibling = sibling->nextSibling;
}
sibling->nextSibling = child;
}
}

// 打印树的函数
void printTree(TreeNode* node)
{
if (node == nullptr) return;
cout << "当前节点为: " << node->value ;
if (node->firstChild)
{
cout <<", " << node->value << "的子节点为: ";
cout << node->firstChild->value;
TreeNode* sibling = node->firstChild->nextSibling;
while (sibling)
{
cout << ", " << sibling->value;
sibling = sibling->nextSibling;
}
}
else
{
cout << ", " << node->value << "没有子节点! ";
}
cout << endl;
printTree(node->firstChild);
printTree(node->nextSibling);
}

int main()
{
// 创建节点
TreeNode* root = new TreeNode(1);
TreeNode* child1 = new TreeNode(2);
TreeNode* child2 = new TreeNode(3);
TreeNode* child3 = new TreeNode(4);
TreeNode* child1_1 = new TreeNode(5);
TreeNode* child2_1 = new TreeNode(6);
TreeNode* child2_2 = new TreeNode(7);
TreeNode* child2_3 = new TreeNode(8);
TreeNode* child3_1 = new TreeNode(9);

// 构建树
addChild(root, child1);
addChild(root, child2);
addChild(root, child3);
addChild(child1, child1_1);
addChild(child2, child2_1);
addChild(child2, child2_2);
addChild(child2, child2_3);
addChild(child3, child3_1);

// 打印树结构
printTree(root);

// 释放内存（在实际应用中应注意内存管理）
delete root;
delete child1;
delete child2;
delete child3;
delete child1_1;
delete child2_1;
delete child2_2;
delete child2_3;
delete child3_1;

return 0;

}
程序输出的结果如下:

C++
1
2
3
4
5
6
7
8
9
当前节点为: 1, 1的子节点为: 2, 3, 4
当前节点为: 2, 2的子节点为: 5
当前节点为: 5, 5没有子节点!
当前节点为: 3, 3的子节点为: 6, 7, 8
当前节点为: 6, 6没有子节点!
当前节点为: 7, 7没有子节点!
当前节点为: 8, 8没有子节点!
当前节点为: 4, 4的子节点为: 9
当前节点为: 9, 9没有子节点!
在程序中构建的树和上面的例子是一样的，我们是是通过孩子兄弟表示法进行了存储，并且在打印的时候又还原了这棵树，通过对比可以确认结果是没问题的。

孩子兄弟表示法就是充分利用了二叉树的特性和算法来处理一棵非二叉树，那么，什么样的树可以被称之为二叉树呢？