树

树

exdoubled Lv4
  2025-11-05 15:00 2025-11-05 15:00 Created   2025-12-18 15:01:42 2025-12-18 15:01:42 Updated    4.4k Words  19 Mins  

无根树： 没有指定根节点的树，意味着它没有深度、高度、祖先、父子关系等概念

有根树： 有指定根节点的树

当有根树的有向边转化为无向边时，即为无根树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct TreeNode {
    int val; // 节点值
    TreeNode* left; // 左子节点
    TreeNode* right; // 右子节点

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

struct NaryTreeNode {
    int val; // 节点值
    std::vector<NaryTreeNode*> children; // 子节点列表

    NaryTreeNode(int x) : val(x) {}
};

树的遍历

树的遍历是指按照某种顺序访问树中的所有节点。常见的树遍历方法有以下几种：

  • 前序遍历(先根遍历)（Pre-order Traversal）：先访问根节点，然后依次访问左子树和右子树
  • 中序遍历（In-order Traversal）：先访问左子树，然后访问根节点，最后访问右子树
  • 后序遍历(后根遍历)（Post-order Traversal）：先访问左子树，然后访问右子树，最后访问根节点

递归的实现

前序遍历

1
2
3
4
5
6
void preOrder(TreeNode* root) {
    if (root == nullptr) return;
    visit(root); // 访问根节点
    preOrder(root->left); // 递归遍历左子树
    preOrder(root->right); // 递归遍历右子树
}

中序遍历

1
2
3
4
5
6
void inOrder(TreeNode* root) {
    if (root == nullptr) return;
    inOrder(root->left); // 递归遍历左子树
    visit(root); // 访问根节点
    inOrder(root->right); // 递归遍历右子树
}

后序遍历

1
2
3
4
5
6
void postOrder(TreeNode* root) {
    if (root == nullptr) return;
    postOrder(root->left); // 递归遍历左子树
    postOrder(root->right); // 递归遍历右子树
    visit(root); // 访问根节点
}

非递归的实现

前序遍历

1
2
3
4
5
6
7
8
9
10
11
12
void preOrder(TreeNode* root) {
    if (root == nullptr) return;
    std::stack<TreeNode*> stack;
    stack.push(root);
    while (!stack.empty()) {
        TreeNode* node = stack.top();
        stack.pop();
        visit(node); // 访问根节点
        if (node->right) stack.push(node->right); // 先右后左
        if (node->left) stack.push(node->left);
    }
}

中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void inOrder(TreeNode* root) {
    std::stack<TreeNode*> stack;
    TreeNode* current = root;
    while (current != nullptr || !stack.empty()) {
        while (current != nullptr) {
            stack.push(current);
            current = current->left; // 一直向左走
        }
        current = stack.top();
        stack.pop();
        visit(current); // 访问根节点
        current = current->right; // 转向右子树
    }
}

后序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void postOrder(TreeNode* root) {
    if (root == nullptr) return;
    std::stack<TreeNode*> stack1, stack2;
    stack1.push(root);
    while (!stack1.empty()) {
        TreeNode* node = stack1.top();
        stack1.pop();
        stack2.push(node);
        if (node->left) stack1.push(node->left); // 先左后右
        if (node->right) stack1.push(node->right);
    }
    while (!stack2.empty()) {
        visit(stack2.top()); // 访问根节点
        stack2.pop();
    }
}

前缀表达式就是前序遍历，中缀表达式就是中序遍历，后缀表达式就是后序遍历

树的存储

等长链表表示法

根据树的度为每个节点分配固定数量的指针域

优点：简单，管理容易

缺点：浪费空间，灵活性差

注意，由于分配的内存空间是固定的，所以占用空间只与节点总数有关，而与树的结构无关

1
2
3
4
5
6
7
8
9
10
struct TreeNode {
    int val; // 节点值
    TreeNode* children[MaxDegree]; // 固定数量的子节点指针

    TreeNode(int x) : val(x) {
        for (int i = 0; i < MaxDegree; ++i) {
            children[i] = nullptr;
        }
    }
};

变长链表表示法

采用边长链表存储每个节点的子节点

和上面类似，但是有几个指针域就有几个分叉，不会存在空指针域

优点：避免了定长链表的空间浪费

缺点：需要额外管理子女节点链表

1
2
3
4
5
6
struct TreeNode {
    int val; // 节点值
    std::list<TreeNode*> children; // 子节点列表

    TreeNode(int x) : val(x) {}
};

左儿子-右兄弟表示法

每个节点包含两个指针：一个指向其第一个子节点（左儿子），另一个指向其下一个兄弟节点（右兄弟）

这是一种将多叉树转化为二叉树的表示方法

由于二叉树的度数为 \(2\) 则可以节省空间

优点：节省空间，适用于多叉树

缺点：访问子节点和兄弟节点需要额外的指针跳转

1
2
3
4
5
6
7
struct TreeNode {
    int val; // 节点值
    TreeNode* leftChild; // 指向第一个子节点
    TreeNode* rightSibling; // 指向下一个兄弟节点

    TreeNode(int x) : val(x), leftChild(nullptr), rightSibling(nullptr) {}
};

进行多叉树到二叉树的转化后

多叉树的先根遍历为二叉树的前序遍历

多叉树的后根遍历为二叉树的中序遍历

多叉树转二叉树实现

通过左儿子右兄弟的方法

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
template <class T> 
node<T>* convertToBinaryTree(node1<T>* root) {
    if (root == nullptr) return nullptr;

    // 创建新的二叉树节点
    node<T>* newNode = new node<T>(root->data);
    node<T>* pre_pt = nullptr; // 用于存储前一个兄弟节点

    // 递归处理每个子节点
    for (auto son_pt : root->children) {
        // 递归地将子树转换为二叉树
        node<T>* child = convertToBinaryTree(son_pt);
        
        // 如果没有子节点，则将该节点作为左孩子
        if (newNode->leftChild == nullptr) {
            newNode->leftChild = child;
        } else {
            // 否则，更新右兄弟
            pre_pt->rightSibling = child;
        }

        // 更新前一个兄弟节点
        pre_pt = child;
    }

    return newNode;
}

双亲表示法

每个节点包含一个指向其父节点的指针

并查集是一种典型的双亲表示法应用

优点：便于访问父节点

缺点：不便于访问子节点，空间浪费

1
2
3
4
5
6
struct TreeNode {
    int val; // 节点值
    TreeNode* parent; // 指向父节点

    TreeNode(int x) : val(x), parent(nullptr) {}
};

数组的实现

1
2
int data[MAX_N]; // 存储节点值
int parent[MAX_N]; // 存储父节点索引，指向自己表示根节点

层号表示法

按照前序写出树中全部结点，在节点前带上节点的层号

也就是层序遍历+前序遍历唯一确定一颗树

1
2
3
4
5
6
struct TreeNode {
    int val; // 节点值
    int level; // 节点层号

    TreeNode(int x, int l) : val(x), level(l) {}
};

如果 \(k\) 是树种的一个结点，那么为 \(k\) 规定一个整数 \(\text{lev}(k)\) 作为 \(k\) 的层号，要求

  • 如果 \(k'\) 是 \(k\) 的子节点，那么 \(\text{lev}(k')>\text{lev}(k)\)
  • 如果 \(k'\) 和 \(k''\) 是 \(k\) 的不同子节点，且 \(k'\) 在 \(k''\) 的左边，那么 \(\text{lev}(k')=\text{lev}(k'')\)
  • 层号和节点所在的层次含义不同
  • 按前序写出树种全部节点，并在结点前带上节点的层号

广义表表示法

根节点表示广义表的表头

广义表表示需要特别强调左右子树的区别

通过树构建广义表

  • 深度优先遍历整棵树
  • 进入节点时，添加 \(+x\)，即将节点压入序列
  • 如果有子节点
    • 左括号压入序列
    • 递归遍历节点的每个子节点
    • 右括号压入序列
  • 退出节点 \(x\)

广义表构建树

  • 依次从保存广义表的字符串中输入字符
  • 若是字母则表示结点值，建立新结点，作为左子 女 \(k=1\) 或右子女 \(k=2\) 链接到其父结点上
  • 左括号则代表子树开始， \(k\) 置 \(1\) ，右括号代表子树结束
  • 遇到逗号则代表左子女为根的子树处理完毕， \(k\) 置 \(2\)
  • 使用一个栈，在进入子树前将根节点指针进栈，处理完子树后出栈，继续处理根节点的其他子女

仅保留广义表表示中的括号

左括号用 \(+x\) 替代，右括号用 \(-x\) 替代

得到一个序列，称为欧拉序列

任意一对 \(+x,-x\) 之间的元素构成以 \(x\) 为根节点的子树的欧拉序列

霍夫曼树和霍夫曼编码

霍夫曼树(Huffman Tree)是一种带权路径长度最短的二叉树，常用于数据压缩中的霍夫曼编码

带权路径长度(WPL, Weighted Path Length)是指树中所有叶子节点的权值与其到根节点路径长度的乘积之和

霍夫曼编码(Huffman Coding)是一种无损数据压缩算法，通过构建霍夫曼树为每个符号分配可变长度的二进制编码，频率高的符号分配较短的编码，频率低的符号分配较长的编码，从而实现数据压缩

构建霍夫曼树的步骤：

  1. 初始化：将每个符号及其对应的权值作为一个独立的节点，放入一个优先队列（最小堆）中
  2. 构建树：重复以下步骤直到队列中只剩下一个节点为止：
  • 从队列中取出两个权值最小的节点，作为新节点的左子节点和右子节点
  • 创建一个新节点，其权值为两个子节点权值之和
  • 将新节点插入队列中
  1. 生成编码：从根节点开始，为每个左子节点分配一个 ‘0’，为每个右子节点分配一个 ‘1’，直到到达叶子节点，生成对应的霍夫曼编码
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
void HuffmanCoding(const std::vector<int>& weights) {
    struct Node {
        int weight;
        Node* left;
        Node* right;
        Node(int w) : weight(w), left(nullptr), right(nullptr) {}
    };

    auto cmp = [](Node* a, Node* b) { return a->weight > b->weight; };
    std::priority_queue<Node*, std::vector<Node*>, decltype(cmp)> minHeap(cmp);

    for (int w : weights) {
        minHeap.push(new Node(w));
    }

    while (minHeap.size() > 1) {
        Node* left = minHeap.top(); minHeap.pop();
        Node* right = minHeap.top(); minHeap.pop();
        Node* parent = new Node(left->weight + right->weight);
        parent->left = left;
        parent->right = right;
        minHeap.push(parent);
    }

    Node* root = minHeap.top();
    generateCodes(root, "", codes);
}

void generateCodes(Node* node, const std::string& code, std::unordered_map<char, std::string>& codes) {
    if (!node) return;
    if (!node->left && !node->right) {
        codes[node->symbol] = code; // 叶子节点，存储编码
    }
    generateCodes(node->left, code + "0", codes);
    generateCodes(node->right, code + "1", codes);
}

使用了优先队列（堆）构造，时间复杂度 \(O(n\log n)\)

如果是有序数组，可以达到 \(O(n)\) 的时间复杂度，具体可以参考作业的合并果子

为什么霍夫曼编码的贪心选择过程是正确的？

可以通过交换论证法证明霍夫曼编码的贪心选择过程是正确的

假设我们有一个最优树，但它没有选择当前权值最小的两个节点进行合并

可以通过交换这两个节点与当前选择的节点来构造一个新的树，证明新树的总权值路径长度不会增加

从而说明选择当前权值最小的两个节点是正确的

霍夫曼编码是一种最优的前缀编码，但不是最优的熵编码，一般作为压缩算法的一个环节出现

算术编码是一种最优的熵编码，但也更复杂

多叉霍夫曼树

多叉霍夫曼树是霍夫曼树的一种扩展，允许每个节点有多个子节点，而不仅限于二叉树的两个子节点

构建多叉霍夫曼树的步骤类似于二叉霍夫曼树，但在每次合并节点时，可以选择多个权值最小的节点进行合并，具体步骤与二叉的有些许不同，需要补充 \(0\) 节点使得节点数 \(-1\) 满足 \((d-1)\) 的倍数

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
void buildDaryHuffmanTree(const std::vector<int>& weights, int d) {
    struct Node {
        int weight;
        std::vector<Node*> children;
        Node(int w) : weight(w) {}
    };

    auto cmp = [](Node* a, Node* b) { return a->weight > b->weight; };
    std::priority_queue<Node*, std::vector<Node*>, decltype(cmp)> minHeap(cmp);

    for (int w : weights) {
        minHeap.push(new Node(w));
    }

    // 补充0节点
    int n = weights.size();
    int remainder = (d - 1 - (n - 1) % (d - 1)) % (d - 1);
    for (int i = 0; i < remainder; ++i) {
        minHeap.push(new Node(0));
    }

    while (minHeap.size() > 1) {
        Node* parent = new Node(0);
        for (int i = 0; i < d; ++i) {
            if (minHeap.empty()) break;
            Node* child = minHeap.top(); minHeap.pop();
            parent->children.push_back(child);
            parent->weight += child->weight;
        }
        minHeap.push(parent);
    }

    Node* root = minHeap.top();
    // 生成编码的过程类似于二叉霍夫曼树
}

树的直径

树的直径时指树中任意两个节点之间的最长路径长度

树可能会有多条直径

计算树的直径的常用方法是两次深度优先搜索(DFS)或广度优先搜索(BFS)

从任意节点出发，使用DFS或BFS找到距离该节点最远的节点，记为节点A

然后从节点A出发，再次使用DFS或BFS找到距离节点A最远的节点，记为节点B

则路径A到B的长度即为树的直径

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
vector<vector<int>> adj;

int dfs(int u){
    vector<bool> visited(n+1, false);
    stack<pair<int, int>> s; // (节点, 距离)
    
    s.push({u, 0});
    visited[u] = true;
    int maxDist = 0;
    int farthestNode = u;
    while(!s.empty()){
        int node = s.top().first;
        int dist = s.top().second;
        s.pop();
        if(dist > maxDist){
            maxDist = dist;
            farthestNode = node;
        }
        for(int v : adj[node]){
       		if(!visited[v]){
            	visited[v] = true;
            	s.push({v, dist + 1});
        	}
        }
    }
    return farthestNode;
}

void findDiameter(int n) {
    adj.resize(n);
    // 构建树的邻接表

    // 第一次DFS/BFS
    int farthestNode = dfs(0); // 从任意节点出发

    // 第二次DFS/BFS
    int secondNode = dfs(farthestNode); // 从farthestNode出发
}

树的同构

无根树的同构等价于图同构

有根树 \((T,u)\) 和 \((Y,v)\) 是同构的当且仅当

  • \(T\) 和 \(Y\) 的是同构的
  • 树 \(T\) 的根节点通过映射 \(u \to v\) 映射到树 \(Y\) 的根节点

有根树是可以哈希来判断

1
2
3
4
5
6
7
8
9
10
template<class T> int TreeHash(Node<T>* now_pt, const vector<int> &prime, const int &pp){
    if(now_pt->child.empty()) return 1;
    int now_hash = 1;
    for(auto son_pt : now_pt->child){
        int son_hash = TreeHash<T>(son_pt, prime, pp);
        now_hash = son_hash * prime[now_pt->size] + now_hash;
        now_hash %= pp;
    }    
    return now_hash;
}

更多可以参考 Wiki 的 树同构 章节

树的重心

树的重心是无根树的概念

对于树上的每一个点，计算其所有子树种中最大的子树节点数

重心是指所有点中，最大的子树节点数最小的点

节点 \(P\) 是树 \(T\) 的重心，当且仅当以 \(P\) 为根时，所有子树大小不超过树大小的一半

必要性：

不妨假设 \(A\) 是重心，以 \(A\) 为根时有子树 \(B\) 的大小超过 \(\frac{|T|}{2}\)， \(A\) 和其他子树的节点数量和小于一半，则以 \(B\) 为根，最大子树大小减少 \(1\) ，和重心定义矛盾

充分性：

若以 \(B\) 为根时，对于 \(B\) 的任一子树 \(A\) 都不超过 \(\frac{|T|}{2}\)，如果以 \(A\) 或 \(A\) 子树中任一节点为根，则 \(B\) 所在的子树大小不小于树节点数量的一半，即任意节点的子树大小都不会小于 \(\frac{|T|}{2}\)，所以 \(B\) 是重心

如果有多个重心，则任意两个重心之间一定有边直接连接

一棵树至多有两个重心

从任意节点出发，dfs遍历整棵树，得到每个子节点向下的节点数

计算节点 \(x\) 向下的子树节点数

利用总结点数-子树节点数 = 其他子树节点数

计算所有子树节点的最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void findCentroid(TreeNode* root, int totalNodes, int& centroid, int& minMaxSubtreeSize) {
    if (!root) return;

    int maxSubtreeSize = 0;
    int subtreeSize = 1; // 包括自己

    for (TreeNode* child : root->children) {
        findCentroid(child, totalNodes, centroid, minMaxSubtreeSize);
        subtreeSize += child->subtreeSize;
        maxSubtreeSize = std::max(maxSubtreeSize, child->subtreeSize);
    }

    // 计算其他子树的大小
    maxSubtreeSize = std::max(maxSubtreeSize, totalNodes - subtreeSize);

    // 更新重心
    if (maxSubtreeSize < minMaxSubtreeSize) {
        minMaxSubtreeSize = maxSubtreeSize;
        centroid = root->val; // 或者其他标识符
    }

    root->subtreeSize = subtreeSize; // 存储子树大小
}

LCA 最近公共祖先

朴素算法

每次选择 \(u,v\) 中深度较大的节点，移动到父节点，两个节点相遇的位置就是 \(LCA\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> pa;
vector<int> depth;
int LCA(int a, int b){
    if (depth[a] < depth[b]) swap(a, b);
    
    while (depth[a] > depth[b]) {
        a = pa[a]; // 向上移动到父节点
    }
    
    while (a != b) {
        a = pa[a]; // 向上移动到父节点
        b = pa[b];
    }
    
    return a; // 返回最近公共祖先
}

最坏情况下，向上跳转次数为树的高度 \(O(h)\)，对于 \(n\) 个节点的树，时间复杂度为 \(O(nh)\)

单次查询时间复杂度 \(O(n)\)

在随机树上的单次查询时间复杂度为 \(O(\log(n))\)

倍增算法

倍增算法每一次找到 \(2^k\) 个祖先

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
vector<vector<int>> up; // up[i][j] 表示节点 i 的 2^j 祖先

vector<int> depth; // depth[i] 表示节点 i 的深度

void dfs(int node, int parent) {
    up[node][0] = parent; // 直接父节点
    for (int j = 1; j < LOG; ++j) {
        if (up[node][j - 1] != -1) {
            up[node][j] = up[up[node][j - 1]][j - 1]; // 2^j 祖先
        } else {
            up[node][j] = -1; // 没有祖先了
        }
    }
    
    for (int child : tree[node]) {
        if (child != parent) {
            depth[child] = depth[node] + 1; // 更新深度
            dfs(child, node);
        }
    }
}
void preprocess(int root) {
    memset(up, -1, sizeof(up)); // 初始化
    depth[root] = 0; // 根节点深度为 0
    dfs(root, -1); // 从根节点开始 DFS
}
int LCA(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v); // 确保 u 深度大于等于 v

    // 使 u 和 v 在同一深度
    for (int j = LOG - 1; j >= 0; --j) {
        if (depth[up[u][j]] >= depth[v]) {
            u = up[u][j];
        }
    }

    if (u == v) return u; // 如果相等，直接返回

    // 向上查找 LCA
    for (int j = LOG - 1; j >= 0; --j) {
        if (up[u][j] != up[v][j]) {
            u = up[u][j];
            v = up[v][j];
        }
    }

    return up[u][0]; // 返回 LCA 的父节点
}

预处理时间复杂度 \(O(n\log n)\)

预处理空间复杂度 \(O(n\log n)\)

查询时间复杂度 \(O(\log n)\)

欧拉序列

欧拉序列是树的一种线性表示

欧拉序列生成算法

  • 深度优先遍历整棵树
  • 进入节点时，将节点值添加到序列中，递归遍历所有子节点，每次递归结束一个子节点后，将节点值再次添加到序列中

最近公共祖先 - OI Wiki

DFS序

冷门科技 —— DFS 序求 LCA - 洛谷专栏

[算法学习]——通过RMQ与dfs序实现O(1)求LCA（含封装板子） - 知乎

  • Title: 树
  • Author: exdoubled
  • Created at : 2025-11-05 15:00:00
  • Updated at : 2025-12-18 15:01:42
  • Link: https://github.com/exdoubled/exdoubled.github.io.git/sjjg/sjjg06/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
树
  1. 树的遍历
  2. 树的存储
    1. 等长链表表示法
    2. 变长链表表示法
    3. 左儿子-右兄弟表示法
    4. 双亲表示法
    5. 层号表示法
    6. 广义表表示法
  3. 霍夫曼树和霍夫曼编码
  4. 多叉霍夫曼树
  5. 树的直径
  6. 树的同构
  7. 树的重心
  8. LCA 最近公共祖先
    1. 朴素算法
    2. 倍增算法
    3. 欧拉序列
    4. DFS序