Hello, NilEra :-)

2024-05-07发表2024-05-27更新数据结构/算法 / 树(Tree)17 分钟读完 (大约2598个字)

Tree

树(Tree)

[TOC]

树的基本概念

树是一种非常重要的非线性数据结构，树的一个节点可能会生出多个分支。一般而言，一棵树会包含一个根节点，向下延伸出若干子节点，每个末端的节点被称为叶子节点。

有根树

有根树存在一个根节点Root，如下：

对于图中概念的一些补充：

节点拥有的子节点个数叫做节点的度。
具有相同深度的节点处于同一层，方便表示。
节点和节点之间的线叫做边。
路径：指从树上一点到另外一点所经过的不重合的点和边的集合，题目中有时会单指点或边的集合。
一颗 $n$ 个节点的树，一定有 $n-1$ 条边

无根树

二叉树

二叉树是一种特殊的树。

所有节点的度都不超过2的树称为二叉树。
因为每个二叉树的节点最多只会有两个子结点，它的两个子节点一般会被称为左、右儿子，两棵子树一般会被称为左、右子树。
左、右儿子甚至根节点本身都有可能缺失（一个节点都没有可以称为空二叉树）。

满二叉树和完全二叉树

二叉树也有两个比较特殊的类型：满二叉树和完全二叉树。

满二叉树：所有层的节点全满。
- 满二叉树的一些规律
  - 第 $n$ 层的节点个数为 $2^{n-1}$
  - 深度为 $n$ 的满二叉树节点数为 $2^0 + 2^1 + 2^2 + \dots + 2^{n-1}= 2^n-1$
完全二叉树：除了最后一层以外，其他层的节点个数全满，而且最后一层的节点从左到右排满直到最后一个节点。
- 完全二叉树的一些规律
  - 完全二叉树的节点个数不会少于 $(2^{n-1}-1)+1 = 2^{n-1}$
  - 完全二叉树的节点个数不会多于 $2^{n} - 1$
  - 一棵完全二叉树，设当前节点为 $t$，其父节点为 $t/2$，其左儿子为 $2t$，其右儿子为 $2t+1$，借助该规律，我们可以将完全二叉树使用数组进行存储。
完全二叉树的存储
- 完全二叉树由于它的特性，可以简单用数组来模拟其结构
- 一般会以数组$[1]$位置为根节点建立二叉树
- 数组$[t]$位置的左儿子和右儿子对应的位置分别为$[2t]$和$[2t+1]$，父节点的位置为$[t/2]$。
- 堆、线段树等数据结构的建立也会参考这个方式

完全二叉树的建立（使用数组），使用这种方法建立非完全二叉树，会导致空间的浪费：

void build(int t) {
    // 添加数据
    UpdateData(t);

    // 如果子节点存在
    Build(2 * t);
    Build(2 * t + 1);
}

为了解决这个问题，我们可以使用其他方法来完成一般二叉树的存储，可以用数组下标模拟节点编号，用多个数组来记录节点信息。为了方便，我们也可以使用结构体来存储这些信息：

// 使用结构体来实现上述操作
struct TreeNode {
    int value;
    int l, r, fa;
}a[100010];

当然，作为一种树形结构，使用指针显然是更合适的方法：

// 使用指针来实现上述操作
struct TreeNode {
    int value;
    TreeNode* l;
    TreeNode* r;
    TreeNode* fa;
};

TreeNode* root;

使用指针的一些操作：

新建节点：

struct TreeNode {
    int value;
    TreeNode *l, *r, *fa;   // 初始为 NULL
    TreeNode(int x){ value = x; }
};

TreeNode* treeNode = new TreeNode(x);

根节点初始化：

1 2	TreeNode* root; root = new TreeNode(v);

插入节点：

void Insert(TreeNode* fa, TreeNode* p, int flag){
    // flag = 0 插入到左边
    // flag = 1 插入到右边
    if (!flag)
        fa->l = p;
    else
        fa->r = p;
    p->fa = fa;
}
TreeNode* treeNode = new TreeNode(v);
Insert(fa, treeNode, flag);

删除节点
1
// 删除节点

二叉树的遍历

二叉树的遍历可分为先序遍历、中序遍历和后序遍历，这三种方式以访问根节点的时间来区分。
先序遍历（Degree-Left-Right, DLR）：根→左→右
中序遍历（Left-Degree-Right, LDR）：左→根→右
先序遍历（Left-Right-Degree, LRD）：左→右→根

在该图中，先序遍历的结果为 1 2 4 5 3 6 7，先序遍历代码如下：

void preOrder(TreeNode* treeNode) {
    cout << p->value << endl;
    if(treeNode->l)     preOrder(treeNode->l);
    if(treeNode->r)     preOrder(treeNode->r);
}

preOrder(root);

在该图中，中序遍历的结果为 4 2 5 1 6 3 7，中序遍历代码如下：

void inOrder(TreeNode* treeNode) {
    if(treeNode->l)     inOrder(treeNode->l);
    cout << p->value << endl;
    if(treeNode->r)     inOrder(treeNode->r);
}

inOrder(root);

在该图中，后序遍历的结果为 4 5 2 6 7 3 1，后序遍历代码如下：

void postOrder(TreeNode* treeNode) {
    if(treeNode->l)     postOrder(treeNode->l);
    if(treeNode->r)     postOrder(treeNode->r);
    cout << p->value << endl;
}

postOrder(root);

除了上述的几种遍历方式，还有层级遍历（BFS）方式对树进行遍历。层级遍历是借助队列（Queue）来实现的，其过程可以描述如下：

层级遍历的代码如下：

TreeNode* q[N];
void bfs(TreeNode* root) {
    int front = 1, rear = 1;
    q[1] = root;
    while (front <= rear) {
        TreeNode* p = q[front];     // 选取队列中最前面的节点
        front++;
        cout << p->value <<endl;
        if(p->l)    q[++rear] = p->l;
        if(p->r)    q[++rear] = p->r;
    }
}

bfs(root);

计算节点的深度

我们可以在遍历树的时候同时进行节点深度的记录，简单来讲就是：
$$depth_{儿子} = depth_{父亲} + 1$$

有根树(Tree)

这里不再是二叉树这种特殊的树，而是一般意义的树。

树的存储方式

vector/链表

// vector 方式
vector<int> nodes[N + 1];
int n, father[N + 1];

// 在 x 和 y之间构建一条边
void addEdge(int x, int y) {
    nodes[x].push_back(y);
}

// 遍历 x 的所有儿子
int l = nodes[x].size();
for (int i = 0; i < l; i++) {
    nodes[x][i];
}

for (auto i: nodes[x]) {
    ...
}

// 链表方式
struct Node {
    int where;
    Node *next;
} *head[N + 1], a[M];

int n, father[N + 1], l = 0;

void addEdge(int x, int y) {
    a[++i].where = y;
    a[l].next = head[x];
    head[x] = &a[l];
}

// 遍历 x 的所有儿子
for (Node* p = head[x]; p; p->next) {
    p->where;
}

有根树遍历

遍历一棵树一般有 DFS 和 BFS 两种方式。
DFS：深度优先搜索，从一个节点开始，选择一条路径并走到底，并通过回溯来访问所有节点。
BFS：广度优先搜索，也称层级顺序探索，从一个节点开始，遍历该节点的所有子节点，或称按照深度从小到大的顺序依次遍历所有点。

有根树的DFS序
有根树的 DFS 序是指，从根节点开始的深度优先搜索过程中，依次记录的点所生成的序列。
对于上图，所生成的 DFS 序即为 ABCDEFGHIJKLMN。当然这个只是其中一种 DFS 序，因为 A 可以走向 B，也可以走向 E，当然也可以走向 F。不同的走向会有不同的 DFS 序。

vector<int> dfn;      // 用于存储 DFS 序, 常用 DFN 表示 DFS 序
                      // dfn 中的元素即为 DFS 序

void dfs(int x) {
    dfn.push_back(x);
    // for x的所有儿子y { dfs(y); }
    // 
    for (Node* p = x; p; p->next){ dfs(p->next) }
}

dfs(root);

有根树的BFS序
有根树的 BFS 序是指，从根节点开始的广度优先搜索过程中，依次记录的点所生成的序列。
对于上图，所生成的 BFS 序即为 ABENCDFMGJHIKL。当然这个只是其中一种 BFS 序，因为同一深度可能会有不同的遍历顺序，如深度为 $2$ 时，BEN、BNE、EBN、…都是可能出现的顺序，不同的顺序会有不同的 BFS 序。

void bfs(int root) {
    // 将 root 加入队列 q;
    q.push(root);

    // 遍历队列 q
    while(队列 q 非空) {
        x = q.top();    // 取队首元素
        q.pop();        // x 出队
        for x的所有儿子y {
            y 入队;
        }
    }
}

无根树(Unrooted Tree)

无根树即没有固定根结点的树，树中的节点只有相邻关系而没有父子关系。无根树有几种等价的形式化定义（建议搭配图论一起学习）：

有 $n$ 个结点， $n−1$ 条边的连通无向图
无向无环的连通图
任意两个结点之间有且仅有一条简单路径的无向图
任何边均为桥的连通图
没有圈，且在任意不同两点间添加一条边之后所得图含唯一的一个圈的图

如下图所示，即一棵无根树：

无根树中的任意一个节点可以被指定为根，变成一棵有根树。

无根树的遍历

遍历一棵无根树一般也有 DFS 和 BFS 两种方式。
遍历无根树时，可以从任意一个节点开始，以类似有根树的方式，遍历整棵树。唯一的区别是在进入一个新节点时，需要记录这个节点的来源节点，在遍历新节点的相邻节点时，避免重复访问来源节点即可。

无根树的 DFS

void dfs(int from, int x) {
    for x的所有响铃节点y {
        if (y != from) {
            dfs(x, y);
        }
    }
}

dfs(-1, x);

无根树的 BFS

void bfs(int x) {
    // 将 x 加入队列 q，x 的来源为空
    while (队列 q 非空) {
        x = q.top();
        from = x的来源节点;
        q.pop;
        for x的所有相邻节点 y {
            if (y != from) {
                y 入队;
                记录 y 的来源节点为 x;
            }
        }
    }
}

bfs(x);

树的直径

树的直径是指树上任意两个节点之间最长（路径的长度一般指的是路径经过的边的数量）的路径。
一棵树可以存在很多条直径，他们的长度相等。
树的直径的中间节点被称为树的中心（图中C节点），如果直径上有偶数个节点，那么中间的两个节点都可以是树的中心。
树的中心到其它点的最长路径最短。