树状数据结构

树的基本概念

  • 树的概念

    树是一种非线性层级数据结构，以唯一的根节点为起点，通过边连接子节点形成分支，无环且任意两节点仅一条路径；最底层无子节点的是叶子节点，整体呈现 “父 - 子” 从属关系，用于表达层级数据（如目录、组织架构）

  • 树的一些重要名词

    • 度

      名词 概念
      节的度 一个结点含有的子树个数为该结点的度
      终端结点（叶子结点） 度为0的结点
      非终端结点（分支结点） 度不为0的结点
      树的度 一颗树中，所有结点的度的最大值

    • 结点关系

      名词 概念
      双亲结点（父结点） 指结点的前驱结点（上一代）
      孩子结点（子结点） 指结点的后继结点（下一代）
      兄弟结点 拥有相同的父结点的结点（同辈）
      结点的祖先 从根结点到该结点上遇到的所有结点
      子孙 指后辈的所有结点
      两个结点之间的路径 两个结点之间的最短路径
      路径长度 两点路径中，边的个数

    • 其他

      名词 概念
      结点的层次 从根开始，根为第一层，后面依次类推
      树的高度或深度 所有结点的层次的最大值
      森林 由m（m>0）颗互不相交的多棵树的集合
      （数据结构中并查集的本质就是一个森林）

    推论：结点个数 = 边数 + 1

    树 = 根结点 + 子树（递归表达式）

    树是用递归定义的结构，往后关于树的很多问题，都可以用递归进行解决

  • 树的表示与定义方法

    • C++中，树的一种表示方法

      typedef struct TreeNode {
    int data;
    vector<struct TreeNode*> childs;
} TreeNode;

    • 孩子表示法（也叫左孩子，右兄弟表示法）

      孩子表示法

      typedef struct TreeNode {
    struct TreeNode* firstchild;
    struct TrrNode* botherNode;
} TreeNode;

    • 双亲表示法

      • 存储结构：用一个数组存储所有节点，每个节点包含两部分信息：
        • 数据域：存储节点本身的数据
        • 双亲域：记录当前节点的父节点在数组中的索引（根节点的双亲域通常设为 - 1）
      • 示例：若数组索引 0~4 分别存储节点 A~E，其中 A 是根节点（双亲域 =-1），B 和 C 的双亲域 = 0（父节点为 A），D 的双亲域 = 1（父节点为 B），则数组可清晰表达 “A→B→D、A→C” 的树结构。
      • 特点：
        • 优势：查找某节点的父节点效率高（直接访问双亲域，O (1)），结构简单
        • 劣势：查找子节点需遍历整个数组（O (n)），适合频繁查询父节点的场景
        • 适用：存储静态树结构（如固定的组织架构）

  • 有序树与无序树

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

    除了二叉树，其他情况下基本都是无序树（方便存储）

  • 有根树、无根树

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

    这个认知主要会影响树的存储，因为存储时最重要的就是存下逻辑关系

    算法竞赛中，遇到的大多是无根树

vector数组实现

  • 实例中的树结构

    在算法中，一般给出的树都是有编号的，这样会简化我们之后存储树的操作。一般提供两个信息：结点的个数 n，以及n-1条x结点与y结点相连的边（看不出父子关系）

    例如：一共有9个结点，1号结点为根结点，接下来8行，每行两个数x、y，表示x、y之间有一条边

  • 代码实现

    #include <iostream>
#include <vector>

using namespace std;

const int N = 1e5 + 10;
vector<int> edges[N];

void addEdge(const int& a, const int& b) {
    edges[a].push_back(b);
    edges[b].push_back(a);
}

int main(int argc, char** argv) {
    int n = 0;
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int a = 0, b = 0;
        cin >> a >> b;
        addEdge(a, b);
    }

    return 0;
}

链式前向星实现

  • 原理介绍

    本质是用链表来存储所有的孩子，而链表是用数组模拟实现的（静态链表）

    步骤：

    • 创建一个足够大的数组h，作为所有结点的哨兵位
    • 创建两个足够大的数组e和ne，一个作为数据域，一个作为指针域
    • 一个变量id，标记新结点的存储位置
    • 当x有一个孩子y时，就把y头插到x的链表中，头节点为x（id++; e[id] = y; ne[id] = h[x]; h[x] = id;）

  • 代码实现

    #include <iostream>

using namespace std;

const int N = 1e5 + 10;
int e[2 * N], ne[2 * N], id, h[N];

void addEdge(const int& e1, const int& e2) {
    auto push_front = [](const int& list, const int& data) {
        e[++id] = data;
        ne[id] = h[list];
        h[list] = id;
    };
    push_front(e1, e2);
    push_front(e2, e1);
}

int main() {
    int n = 0;
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int a = 0, b = 0;
        cin >> a >> b;
        addEdge(a, b);
    }

    return 0;
}

深度优先遍历（DFS）

  • 概念

    深度优先搜索的核心：每次都尝试向更深的结点走，当一条路走完时，再回去找别的路

    image-20260315161816178

  • 代码实现

    • 基于 vector 实现的遍历

      #include <iostream>
#include <vector>

using namespace std;

const int N = 1e5 + 10;
vector<int> edges[N];

void addEdge(const int& a, const int& b) {
    edges[a].push_back(b);
    edges[b].push_back(a);
}

void dfs_stack(const int& root, bool* const st) {
    cout << root << " ";
    st[root] = true;
    for (auto cur: edges[root]) {
        if (!st[cur]) {
            dfs_stack(cur, st);
        }
    }
}

void dfs(const int& root) {
    bool st[N] = {false};
    dfs_stack(root, st);
    cout << endl;
}

int main(int argc, char** argv) {
    int n = 0;
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int a = 0, b = 0;
        cin >> a >> b;
        addEdge(a, b);
    }
    dfs(1);
    dfs(1);

    return 0;
}

      测试用例：

      11
1 3
7 3
3 10
1 5
4 5
2 1
11 2
6 11
11 8
11 9

      image-20260315161959927

    • 基于 链式前向星 实现的遍历

      #include <iostream>

using namespace std;

const int N = 1e5 + 10;
int e[2 * N], ne[2 * N], id, h[N];

void addEdge(const int& e1, const int& e2) {
    auto push_front = [](const int& list, const int& data) {
        e[++id] = data;
        ne[id] = h[list];
        h[list] = id;
    };
    push_front(e1, e2);
    push_front(e2, e1);
}

void dfs_stack(const int& root, bool* const st) {
    cout << root << " ";
    st[root] = true;
    for (int cur = h[root]; cur; cur = ne[cur]) {
        if (!st[e[cur]]) {
            dfs_stack(e[cur], st);
        }
    }
}

void dfs(const int& root) {
    bool st[N] = {false};
    dfs_stack(root, st);
    cout << endl;
}

int main() {
    int n = 0;
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int a = 0, b = 0;
        cin >> a >> b;
        addEdge(a, b);
    }
    dfs(1);
    dfs(1);

    return 0;
}

      注：和vector实现输出结果不同的原因是，这里是头插的，而vector中是尾插的，所以扫描链表的时候顺序不一样

广度优先遍历（BFS)

  • 概念

    层序遍历，也是搜索树或图的一种算法。所谓广度优先，就是每次都尝试访问同一层的结点，如果同一层都访问完了，再访问下一层。实现时，只需要借助队列即可实现，先把第一个结点的孩子放入队列，每次出队列时，把下一层（孩子）的元素入队列。直到队列为空

  • 代码实现

    • 基于vector数组实现的树BFS遍历（递归思想）

      #include <iostream>
#include <queue>
#include <vector>

using namespace std;

const int N = 1e5 + 10;
vector<int> edges[N];

void addEdge(const int& a, const int& b) {
    edges[a].push_back(b);
    edges[b].push_back(a);
}

void bfs_stack(const int& root, bool* const st, queue<int>& q) {
    cout << root << " ";
    st[root] = true;

    for (auto cur: edges[root]) {
        if (!st[cur]) {
            q.push(cur);
        }
    }
    q.pop();

    // 注意fornt()方法需要先判空
    if (!q.empty()) {
        bfs_stack(q.front(), st, q);
    }
}

void bfs(const int& root) {
    // 初始化一些数据
    bool st[N] = {false};
    queue<int> q;

    // 进入递归
    q.push(root);
    bfs_stack(root, st, q);
    cout << endl;
}

int main() {
    int n = 0;
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int a = 0, b = 0;
        cin >> a >> b;
        addEdge(a, b);
    }
    bfs(1);
    bfs(1);

    return 0;
}

    • 基于vector数组实现的树BFS遍历（循环思想）

      #include <iostream>
#include <queue>
#include <vector>

using namespace std;

const int N = 1e5 + 10;
vector<int> edges[N];

void addEdge(const int& a, const int& b) {
    edges[a].push_back(b);
    edges[b].push_back(a);
}

void bfs(const int& root) {
    // 初始化一些数据
    bool st[N] = {false};
    queue<int> q;

    // 进入循环
    q.push(root);
    while (!q.empty()) {
        cout << q.front() << " ";
        st[q.front()] = true;

        for (auto cur: edges[q.front()]) {
            if (!st[cur]) {
                q.push(cur);
            }
        }
        q.pop();
    }
    cout << endl;
}

int main() {
    int n = 0;
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int a = 0, b = 0;
        cin >> a >> b;
        addEdge(a, b);
    }
    bfs(1);
    bfs(1);

    return 0;
}

    • 基于链式前向星实现的树BFS遍历

      #include <iostream>
#include <queue>

using namespace std;

const int N = 1e5 + 10;
int e[N * 2], ne[N * 2], id, h[N];

void addEdge(const int& a, const int& b) {
    auto push_front = [](const int& list, const int& data) {
        e[++id] = data;
        ne[id] = h[list];
        h[list] = id;
    };
    push_front(a, b);
    push_front(b, a);
}

void bfs(const int& root) {
    // 初始化一些数据
    bool st[N] = {false};
    queue<int> q;

    // 进入循环
    q.push(root);
    while (!q.empty()) {
        cout << q.front() << " ";
        st[q.front()] = true;

        for (int cur = h[q.front()]; cur; cur = ne[cur]) {
            if (!st[e[cur]]) {
                q.push(e[cur]);
            }
        }
        q.pop();
    }
    cout << endl;
}

int main() {
    int n = 0;
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int a = 0, b = 0;
        cin >> a >> b;
        addEdge(a, b);
    }
    bfs(1);
    bfs(1);

    return 0;
}

DFS、BFS的理解

  • 深度优先遍历（DFS）

    • 时间复杂度

      DFS会遍历所有的边两遍，若结点的个数为n，则遍历次数为2 * (n - 1)，即时间复杂度为O(N)

    • 空间复杂度

      若树退化成一个链表（都只有一个孩子），则所有元素都会压栈，故空间复杂度为O(N)

  • 广度优先遍历（BFS）

    • 时间复杂度

      每个结点都会入队、出队一次，故结点个数为n时，遍历次数为2 * n，即时间复杂度为O(N)

    • 空间复杂度

      若一个结点的孩子是其他所有结点，那么就会全部入队列，故空间复杂度为O(N)

  • 从DFS中加深对递归的理解

    void dfs_stack(int root) {
    cout << u << " ";
    st[root] = true; // 标记访问过的结点

    // 遍历所有的孩子
    for (auto v: edges[root]) {
        dfs(v);
    }
}

    image-20260315162948866

  • 递归实例 - 斐波那契数列

    // 斐波那契数列
int fib(int n) {
    if (n == 0 || n == 1)
        return n;
    return fib(n - 1) + fib(n - 2);
}

  • 学习递归的阶段

    • 初始递归：C++编程课
    • 加深理解：树等数据结构中（只能看懂递归代码）
    • 消除恐惧：递归算法学习
    • 熟练应用：搜索算法掌握
« 线性表 ← 返回列表 二叉树 »