树的结构定义与存储方式：vector 数组及链式前向星

一、树的概念

1.1 树的定义

树型结构是一类重要的非线性数据结构。

有一个特殊的结点，称为根结点，根结点没有前驱结点。
除根结点外，其余结点被分成 k 个互不相交的集合，其中每一个集合又是树，称这棵树为根节点的子树。
结论：树是递归定义的

1.2 树的基本术语

结点的度：树中一个结点孩子的个数称为该结点的度。
树的度：树中结点最大的度数称为树的度。
树的高度（深度）：树中结点的最大层数称为树的高度 (深度)。
路径：树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的，路径长度为序列中边的个数（且为最短路）。

1.3 有序树和无序树

有序树：结点的子树按照从左往右的顺序排列，不能更改。
无序树：结点的子树之间没有顺序，随意更改。

1.4 有根树和无根树

有根树：树的根节点已知，是固定的。
无根树：树的根节点未知，谁都可以是根结点。

注：这个认知主要会影响我们对于树的存储。在存储树结构的时候，最重要的就是要存下逻辑关系。如果是无根树，父子关系不明确，此时我们需要把所有的情况都存下来。如 a 和 b 之间有一条边，我们不仅要存 a 有一个孩子 b，也要存 b 有一个孩子 a。（有时有根树也需要这样存储）

二、树的存储

树结构相对线性结构来说就比较复杂。存储时，既要保存值域，也要保存结点与结点之间的关系。实际中树有很多种存储方式：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。现阶段，只要掌握孩子表示法，学会用孩子表示法存储树，并且在此基础上遍历整棵树。后续会在并查集中学习双亲表示法。至于其它存储形式，在学习算法阶段不要求掌握。

2.1 孩子表示法

孩子表示法是将每个结点的孩子信息存储下来。如果是在无根树中，父子关系不明确，我们会将与该结点相连的所有点都存储下来。

2.2 实现方式

2.2.1 vector 数组实现

2.2.1.1 方法解析

vector 是可变长数组，如果只涉及尾插，效率还是可以的。而树结构这种一对多的关系，正好可以利用尾插，把所有的关系全部存起来。

因此，可以创建一个大小为 n + 1 的 vector 数组 edges[n + 1]。
其中 edges[i] 里面就保存着 i 号结点所连接的结点。

2.2.1.2 代码

#include <iostream>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
vector<int> edges[N];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        // a 和 b 之间有一条边
        edges[a].push_back(b);
        edges[b].push_back(a);
    }
    return 0;
}

2.2.2 链式前向星

2.2.2.1 方法解析

链式前向星的本质就是用数组来模拟链表。本质：其实就是把 b 头插到 a 所在的链表后面。

2.2.2.2 代码

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
// 链式前向星
int h[N], e[N * 2], ne[N * 2], id;
int n;

// 其实就是把 b 头插到 a 所在的链表后面执行一次头插操作
void add(int a, int b) {
    id++;
    e[id] = b;
    ne[id] = h[a];
    h[a] = id;
}

int main() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        // a 和 b 之间有一条边
        add(a, b);
        add(b, a);
    }
    return 0;
}

2.2.3 两种方式的对比和总结

关于 vector 数组以及链式前向星：

前者由于用到了容器 vector，实际运行起来相比较于后者更耗时，因为 vector 是动态实现的。
但是在如今的算法学习与刷题中，一般不会无聊到卡这种常数时间。也就是 vector 虽然慢，但不会因此而超时。
总结：做题的时候，选择一种自己喜欢的方式即可。

树的结构定义与存储方式：vector 数组及链式前向星

一、树的概念

1.1 树的定义

1.2 树的基本术语

1.3 有序树和无序树

1.4 有根树和无根树

二、树的存储

2.1 孩子表示法

2.2 实现方式

2.2.1 vector 数组实现

2.2.1.1 方法解析

2.2.1.2 代码

2.2.2 链式前向星

2.2.2.1 方法解析

2.2.2.2 代码

2.2.3 两种方式的对比和总结

更多推荐文章

相关免费在线工具

树的结构定义与存储方式：vector 数组及链式前向星

一、树的概念

1.1 树的定义

1.2 树的基本术语

1.3 有序树和无序树

1.4 有根树和无根树

二、树的存储

2.1 孩子表示法

2.2 实现方式

2.2.1 vector 数组实现

2.2.1.1 方法解析

2.2.1.2 代码

2.2.2 链式前向星

2.2.2.1 方法解析

2.2.2.2 代码

2.2.3 两种方式的对比和总结

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具