当前位置：首页 > news >正文

二叉树详解：从概念到应用，带你玩转树形结构

news 2026/3/26 18:40:18

前言

在学习了线性表（如数组、链表、栈、队列）之后，我们掌握了如何表示和处理具有“一对一”线性关系的数据。然而，现实世界中的许多关系并非简单的线性关系，而是呈现层次结构。例如，一个家族的族谱、计算机的文件系统、编译器对表达式的语法分析，甚至体育比赛的淘汰赛程，都天然具有树形层次。为了高效地处理这类问题，我们需要引入一种新的数据结构——树。

树是一种非线性数据结构，它由节点和连接节点的边组成，具有层次关系。其中最常用、最简单的一种树就是二叉树——每个节点最多有两个子节点的树。二叉树不仅自身应用广泛，也是许多高级数据结构（如二叉搜索树、堆、哈夫曼树、平衡树等）的基础。

本文将带你从零开始，全面深入地学习二叉树。我们会从二叉树的由来和基本概念讲起，逐步深入到存储方式、遍历方法，并通过大量经典例题（精选自洛谷等OJ）来巩固知识，最终掌握二叉树在各种实际问题中的应用。文章力求通俗易懂，代码详尽，希望能帮助你彻底弄懂二叉树。

1. 为什么需要树？——从现实到抽象

想象一棵真正的橡树：它有一个粗壮的树干，树干上分出一些大树枝，每个大树枝又继续分出小树枝，直到末端的叶子。这种分叉结构就是自然界中的树。计算机科学中的树正是对这种现实结构的抽象。

树干→ 树的根节点（Root）
树枝分叉→ 节点的子节点（Child）
末端的叶子→叶子节点（Leaf）

树形结构能够自然地表达数据之间的层次关系和分支关系。例如，要统计一棵苹果树上的苹果总数，你可以递归地进行：苹果总数 = 左树枝上的苹果 + 右树枝上的苹果。而每个树枝上的苹果又可以继续按照同样的方式统计，直到到达叶子（没有分支的枝条）。这正是递归思想的体现，而树本身就是递归定义的。

在计算机领域，树的应用无处不在：

操作系统文件目录：根目录下有多级子目录和文件。
HTML DOM树：网页标签的嵌套结构。
编译原理：源代码的语法分析树。
数据库索引：B+树。
算法设计：堆排序、哈夫曼编码、决策树等。

因此，掌握树，尤其是二叉树，是每个程序员必备的技能。

2. 二叉树的基本概念

2.1 定义

二叉树（Binary Tree）是每个节点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”。二叉树可以是空树，即没有任何节点。

二叉树的节点通常包含三部分：

数据域
指向左子节点的指针（或引用）
指向右子节点的指针（或引用）

2.2 常见术语

根节点：树的最顶层节点，一棵树只有一个根。
叶子节点：没有子节点的节点。
父节点与子节点：如果节点A有子节点B，则A是B的父节点，B是A的子节点。
兄弟节点：具有相同父节点的节点。
节点的度：节点拥有的子树个数。二叉树的节点度 ≤ 2。
树的深度（高度）：从根节点到最远叶子节点的路径上的节点数（有些定义是边数，本文按节点数计算）。
层：根节点为第1层，其子节点为第2层，以此类推。

2.3 特殊的二叉树

满二叉树：一棵深度为k的二叉树，如果它有2^k - 1个节点，即每一层的节点数都达到最大值，称为满二叉树。
完全二叉树：除了最后一层，其余层都是满的，并且最后一层的节点都尽量靠左排列。完全二叉树可以用数组高效存储。
二叉搜索树：左子树上所有节点的值均小于根节点，右子树上所有节点的值均大于根节点，且左右子树也分别是二叉搜索树。后面会重点讲解。

3. 二叉树的存储结构

在程序中，我们需要将抽象的二叉树具体表示出来。常用的存储方式有两种：顺序存储（数组）和链式存储（指针）。

3.1 顺序存储（数组）

对于完全二叉树（或满二叉树），我们可以使用一维数组来存储。这种存储方式非常紧凑，并且可以通过下标快速定位父子节点：

根节点放在下标1（或0，为了方便，常从1开始）
对于下标为 i 的节点：
- 左孩子下标为 2*i
- 右孩子下标为 2*i + 1
- 父节点下标为 i/2（整数除法）

这种存储方式的优点是简单、内存连续、访问快，但缺点是不适合非完全二叉树，会造成大量空间浪费。不过，许多实际问题可以利用完全二叉树的性质，比如堆、线段树，以及下面要讲的淘汰赛问题。

例题1：淘汰赛（世界杯问题）

题目描述有 2^n（n≤7）个国家参加世界杯决赛圈，进入淘汰赛环节。已经知道各个国家的能力值，且都不相等。能力值高的国家与能力值低的国家比赛时高者获胜。赛程安排：1号与2号比赛，胜者晋级；3号与4号比赛，胜者晋级……如此两两比赛，直到决出冠军。给出各个国家的能力值，请问亚军是哪个国家？

输入格式第一行一个整数 n，表示一共 2^n 个国家参赛。第二行 2^n 个整数，第 i 个整数表示编号为 i 的国家的能力值（1≤i≤2^n），能力值在 int 范围内，数据保证不存在平局。

输出格式仅一个整数，表示亚军国家的编号。

解题思路淘汰赛的赛程构成一棵满二叉树，叶子节点是初始的 2^n 个国家，每轮比赛合并两个国家，胜者进入父节点。冠军是根节点，亚军是决赛中输给冠军的那个国家，也就是根节点的另一个子节点（左子或右子）。但注意：亚军不一定是最初与冠军相邻的国家，因为在晋级过程中可能遇到各种对手。实际上，亚军是整棵树中除了冠军之外能力值最高的国家吗？不是！因为淘汰赛的偶然性，亚军并不一定是第二强的，但题目假设能力值决定胜负，所以能力值最高的必然是冠军，那么亚军就是所有直接输给冠军的国家中能力值最高的？也不完全对，因为冠军可能一路淘汰多个对手，但最终决赛的对手才是亚军。而决赛的对手，是在另一半区中一路胜出的那个国家。所以，我们只需要模拟比赛过程，找出冠军和亚军即可。

最简单的做法：用数组模拟比赛。将 2^n 个国家放在数组最底层（可以看作叶子），然后两两比赛，胜者上升到上一层，直到决出冠军。同时记录亚军——也就是冠军在决赛中击败的那个对手。但直接模拟需要 O(2^n) 的空间和时间，这里 n≤7，完全可行。

然而，更简洁的思路：亚军一定是在与冠军比赛的那一轮中输给冠军的国家，即冠军的最后一个对手。我们可以通过一次遍历找出冠军和亚军，但需要知道比赛的树形结构。其实，我们可以把赛程看作一棵树，冠军是根，亚军是根的两个子节点中的一个，但具体是哪个取决于半区的胜者。我们可以模拟：将国家编号 1~2^n 按照二叉树叶子顺序排列，然后自底向上合并，用数组 tree[] 存储每个节点的胜者编号。最后，亚军就是冠军的直接子节点中不是冠军的那个。但冠军的直接子节点可能有两个，我们如何知道哪个是亚军？实际上，冠军的父节点就是根，根的左右子分别是两个半区的胜者，亚军就是这两个中输给冠军的那个，也就是另一个。所以我们在模拟过程中，需要记录每个节点的胜者，以及该节点的左右子是谁。但我们可以简化：因为决赛的两个对手，分别来自左半区和右半区。我们可以分别求出左半区的最大能力值（即左半区冠军）和右半区的最大能力值，然后比较这两个值，较大的就是冠军，较小的就是亚军。但这样对吗？注意，能力值最大的国家在左半区，那么左半区冠军就是它，右半区冠军是右半区能力最大的，但亚军不一定是右半区最大的，因为右半区最大的可能比左半区第二大的小，但亚军就是右半区冠军，因为它进入决赛并输给了左半区冠军。所以，亚军就是冠军所在半区的对立半区中的最大能力值国家。如果冠军在左半区，那么亚军就是右半区的最强者。因此，我们只需要找出所有国家中能力值最大的（冠军）和它所在的半区，然后找出另一半区的最大能力值即可。但半区划分是递归的，不能简单地按初始位置一刀切，因为随着比赛进行，半区是动态变化的。实际上，对于满二叉树，我们可以通过编号规律：将国家按顺序编号，比赛过程就是构建一棵完全二叉树，根节点下标为1，叶子节点下标从 2^n 到 2^{n+1}-1（如果数组从1开始）。那么亚军就是与根节点直接相连的两个子节点中，能力值较小的那个（因为冠军能力值最大，它占据一个子节点，另一个子节点的能力值就是亚军）。因此，我们可以用数组模拟这棵满二叉树的建立。

代码实现（C++）

cpp

#include <iostream> #include <vector> #include <algorithm> using namespace std;  struct Node { int id; // 国家编号（叶子节点才有意义，内部节点可用来表示胜者编号） int power; // 能力值 };  int main() { int n; cin >> n; int m = 1 << n; // 2^n 个国家 vector<Node> tree(2 * m); // 用数组表示满二叉树，下标从1开始，叶子放在 m ~ 2*m-1  // 读入叶子节点（原始国家） for (int i = 0; i < m; i++) { cin >> tree[m + i].power; tree[m + i].id = i + 1; // 编号从1开始 }  // 自底向上构建比赛树 for (int i = m - 1; i >= 1; i--) { if (tree[2 * i].power > tree[2 * i + 1].power) { tree[i] = tree[2 * i]; // 左子胜出 } else { tree[i] = tree[2 * i + 1]; // 右子胜出 } }  // 冠军是 tree[1]，亚军是冠军的直接对手，即 tree[2] 和 tree[3] 中能力值较小的那个？ // 注意：tree[2] 和 tree[3] 是左右半区的胜者，其中一个是冠军，另一个是亚军。 // 因为冠军能力值最大，所以亚军就是 tree[2] 和 tree[3] 中能力值较小的那个。 if (tree[2].power > tree[3].power) { cout << tree[3].id << endl; } else { cout << tree[2].id << endl; }  return 0; }

思路分析：我们构建了一个大小为 2*m 的数组，其中 m=2^n，叶子节点从下标 m 开始存放，然后从 i=m-1 到 1 依次计算父节点，父节点取两个子节点中能力值较大的。最后根节点 tree[1] 是冠军，它的两个子节点 tree[2] 和 tree[3] 分别是左、右半区的冠军，亚军就是其中输给冠军的那个（即能力值较小的）。这个解法的时间复杂度 O(2^n)，空间 O(2^{n+1})，对于 n≤7 绰绰有余。

3.2 链式存储

对于一般的二叉树，更常用的是链式存储。每个节点定义为一个结构体，包含数据域和左右孩子指针。

cpp

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

这种存储方式灵活，不会浪费空间，但需要动态分配内存，操作时需注意指针安全。

例题3：二叉树的深度（链式存储基础）

题目描述有一个 n 个结点的二叉树。给出每个结点的两个子结点编号（均不超过 n），建立一棵二叉树（根节点的编号为 1），如果是叶子结点，则输入 0 0。建好这棵二叉树之后，请求出它的深度。二叉树的深度是指从根节点到叶子结点时，最多经过了几层。

输入格式第一行一个整数 n，表示结点数。之后 n 行，第 i 行两个整数 l、r，分别表示结点 i 的左右子结点编号。若 l=0 则表示无左子结点，r=0 同理。

输出格式一个整数，表示最大结点深度。

输入输出样例

text

输入： 7 2 7 3 6 4 5 0 0 0 0 0 0 0 0 输出： 4

解题思路这是一道非常基础的二叉树题目。我们只需要根据输入建立节点之间的链接，然后从根节点1开始递归计算深度即可。深度 = max(左子树深度, 右子树深度) + 1。注意递归边界：空节点深度为0。

代码实现

cpp

#include <iostream> #include <vector> #include <algorithm> using namespace std;  struct Node { int left, right; };  vector<Node> tree;  int dfs(int u) { if (u == 0) return 0; // 空节点 return max(dfs(tree[u].left), dfs(tree[u].right)) + 1; }  int main() { int n; cin >> n; tree.resize(n + 1); for (int i = 1; i <= n; i++) { cin >> tree[i].left >> tree[i].right; } cout << dfs(1) << endl; return 0; }

这里我们用数组模拟了链式结构，因为节点编号连续，直接用两个数组 left[] 和 right[] 表示左右孩子即可，不需要显式的指针。这是竞赛中常用的简化写法。

复杂度：O(n)，每个节点访问一次。

4. 二叉树的遍历

遍历是二叉树最基本的操作，按照访问根节点的顺序不同，可以分为深度优先遍历（前序、中序、后序）和广度优先遍历（层次遍历）。

4.1 深度优先遍历（DFS）

前序遍历：根节点 -> 左子树 -> 右子树
中序遍历：左子树 -> 根节点 -> 右子树
后序遍历：左子树 -> 右子树 -> 根节点

递归实现非常简洁。以之前定义的 tree 数组为例（每个节点有 left, right 编号），写出三种遍历：

cpp

void preorder(int u) { if (u == 0) return; cout << u << " "; // 访问根 preorder(tree[u].left); preorder(tree[u].right); }  void inorder(int u) { if (u == 0) return; inorder(tree[u].left); cout << u << " "; inorder(tree[u].right); }  void postorder(int u) { if (u == 0) return; postorder(tree[u].left); postorder(tree[u].right); cout << u << " "; }

4.2 广度优先遍历（BFS / 层次遍历）

层次遍历按照从上到下、从左到右的顺序访问每个节点。通常借助队列实现：

cpp

void levelOrder(int root) { queue<int> q; q.push(root); while (!q.empty()) { int u = q.front(); q.pop(); if (u == 0) continue; cout << u << " "; q.push(tree[u].left); q.push(tree[u].right); } }

4.3 非递归遍历

虽然递归简洁，但有时受限于栈深度，或者为了面试考察，我们需要掌握非递归实现（借助栈）。这里以前序遍历为例：

cpp

void iterativePreorder(int root) { stack<int> st; st.push(root); while (!st.empty()) { int u = st.top(); st.pop(); if (u == 0) continue; cout << u << " "; // 注意栈是后进先出，所以先压右孩子，再压左孩子 st.push(tree[u].right); st.push(tree[u].left); } }

中序和后序的非递归稍复杂，但也是经典练习。

5. 遍历序列与重建二叉树

二叉树的遍历序列携带了树的结构信息。已知两种遍历序列（必须包含中序），通常可以唯一确定一棵二叉树。

已知前序 + 中序→ 可以确定二叉树
已知后序 + 中序→ 可以确定二叉树
已知前序 + 后序→ 不能唯一确定，因为无法区分左右子树

为什么需要中序？因为中序能明确划分左右子树。例如前序的第一个节点是根，在中序中找到根，左边就是左子树，右边就是右子树，然后递归处理。

例题6：美国血统（USACO 3.4）

题目描述农夫约翰非常认真地对待他的奶牛们的血统。然而他不是一个真正优秀的记账员。他把他的奶牛们的家谱作成二叉树，并且把二叉树以更线性的“树的中序遍历”和“树的前序遍历”的符号加以记录而不是用图形的方法。你的任务是在被给予奶牛家谱的“树中序遍历”和“树前序遍历”的符号后，创建奶牛家谱的“树的后序遍历”的符号。每一头奶牛的姓名被译为一个唯一的字母。显然，这里的树不会有多于 26 个的顶点。

输入格式第一行一个字符串，表示该树的中序遍历。第二行一个字符串，表示该树的前序遍历。

输出格式单独的一行表示该树的后序遍历。

样例输入：

text

ABEDFCHG CBADEFGH

输出：

text

AEFDBHGC

解题思路这是一个经典的递归构造问题。设中序序列为in，前序序列为pre。前序的第一个字符pre[0]就是根节点。在中序中找到根的位置pos，则in[0..pos-1]是左子树的中序，in[pos+1..end]是右子树的中序。同时，左子树的节点个数为pos，所以前序中从pre[1]开始的前pos个字符就是左子树的前序，剩余的是右子树的前序。递归构造左右子树，然后输出根（后序的顺序是左、右、根）。

代码实现

cpp

#include <iostream> #include <string> using namespace std;  void postorder(string in, string pre) { if (in.empty()) return; char root = pre[0]; int pos = in.find(root); string left_in = in.substr(0, pos); string right_in = in.substr(pos + 1); string left_pre = pre.substr(1, pos); string right_pre = pre.substr(1 + pos); postorder(left_in, left_pre); postorder(right_in, right_pre); cout << root; }  int main() { string in, pre; cin >> in >> pre; postorder(in, pre); cout << endl; return 0; }

复杂度：每次 find 操作 O(n)，递归深度 O(n)，最坏 O(n²)。由于 n≤26，完全可以接受。

例题10：遍历问题（给定前序和后序求可能中序个数）

题目描述给定一棵二叉树的前序遍历和后序遍历，你却不能确定其中序遍历序列，考虑如下图中的几棵二叉树：所有这些二叉树都有着相同的前序遍历和后序遍历，但中序遍历却不相同。现给定前序遍历结果 s1 和后序遍历结果 s2，求可能的中序遍历序列的总数（结果不超过 2^63-1）。保证至少存在一棵二叉树满足给出的信息，s1,s2 中只含小写字母，且在某个字符串中不存在相同的字母。

输入格式共两行，第一行为前序遍历 s1，第二行为后序遍历 s2。

输出格式输出可能的中序遍历序列的总数。

样例输入：

text

abc cba

输出：

text

解题思路当一棵二叉树的某个节点只有左子树或只有右子树时，前序和后序无法区分是左还是右，从而会导致中序的不同。例如前序为 "ab"，后序为 "ba"，那么树可以是 a 的左孩子是 b，也可以是 a 的右孩子是 b，对应中序分别是 "ba" 和 "ab"。所以，中序的可能数量等于所有“只有一个孩子”的节点个数导致的组合数。具体地，对于前序和后序，我们可以递归分析：前序的第一个字符是根，后序的最后一个字符也是根。然后找出左子树的节点集合：前序中根之后的一部分，后序中根之前的一部分，它们必须一致。如果左子树非空，那么前序中根后的第一个字符就是左子树的根，它在后序中的位置可以用来划分左右子树。关键在于：当我们发现某个节点只有一个子树时（即左子树或右子树为空），就会产生两种可能（左或右）。因此，我们需要统计所有只有一个子树的节点个数 k，那么可能的中序总数就是 2^k（每个这样的节点有两种选择）。

具体算法：递归处理前序区间 [preL, preR] 和后序区间 [postL, postR]，前序第一个为根，后序最后一个为根。然后找出左子树的根（前序中根的下一个字符）在后序中的位置，从而确定左子树长度。如果左子树长度等于整个子树的节点数减1，说明只有左子树；如果左子树长度为0，说明只有右子树。但实际上，当只有一个子树时，我们无法确定是左还是右，所以计数乘2。但注意：如果左右子树都存在，则结构唯一确定，不增加计数。

实现时，我们递归处理，并返回可能的种数，相乘累积。

代码实现

cpp

#include <iostream> #include <string> using namespace std;  string pre, post;  long long dfs(int preL, int preR, int postL, int postR) { if (preL >= preR) return 1; // 空树或单节点，只有一种 if (pre[preL] != post[postR]) return 0; // 根不匹配，实际上不会发生 long long res = 1; int cnt = 0; // 统计子树的个数，实际上我们只关心是否只有一棵子树 // 左子树的根是 pre[preL+1] char leftRoot = pre[preL + 1]; // 在 post 中寻找 leftRoot，它在左子树的最后一个位置 int pos = postL; while (post[pos] != leftRoot) pos++; int leftSize = pos - postL + 1; // 左子树节点数 int rightSize = (preR - preL) - leftSize; // 右子树节点数 = 总节点数-1-左子树节点数 if (rightSize == 0) { // 只有左子树，此时有两种可能（左或右），但注意：如果左子树为空？实际上左子树非空，右子树空，所以只有左子树，那么有两种情况：左子树可以是原来的左，也可以是原来的右，但前序和后序序列不变？实际上，如果只有左子树，那么前序和后序无法区分这个子树是左还是右，所以有2种可能。 res *= 2; // 递归处理左子树 res *= dfs(preL + 1, preL + leftSize, postL, pos); } else { // 左右子树都有，唯一确定 res *= dfs(preL + 1, preL + leftSize, postL, pos); res *= dfs(preL + leftSize + 1, preR, pos + 1, postR - 1); } return res; }  int main() { cin >> pre >> post; cout << dfs(0, pre.size() - 1, 0, post.size() - 1) << endl; return 0; }

注意：本题要求结果不超过 2^63-1，所以用 long long 足够。

补充：中序+后序求先序（NOIP2001普及组）

题目描述给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，且二叉树的节点个数 ≤8）。

输入格式共两行，均为大写字母组成的字符串，表示一棵二叉树的中序与后序排列。

输出格式共一行一个字符串，表示一棵二叉树的先序。

样例输入：

text

BADC BDCA

输出：

text

ABCD

解题思路与之前类似，后序的最后一个字符是根，在中序中找到根，左边左子树，右边右子树，递归构建。直接输出先序（根左右）。

代码略（类似美国血统，只是从后序取根）。

6. 二叉搜索树

二叉搜索树（BST）是一种特殊的二叉树，它满足以下性质：

若左子树不空，则左子树上所有节点的值均小于根节点的值；
若右子树不空，则右子树上所有节点的值均大于根节点的值；
左右子树也分别为二叉搜索树。

这个性质使得二叉搜索树可以支持快速的查找、插入和删除操作，平均时间复杂度 O(log n)，最坏 O(n)（退化为链表）。为了避免最坏情况，出现了平衡树（如AVL、红黑树），但基本操作原理相似。

6.1 基本操作

查找

从根开始，比较目标值与当前节点值，若相等则找到；若小于则递归左子树；若大于则递归右子树。

插入

类似查找，找到合适的位置插入新节点（作为叶子）。

删除

分三种情况：

被删除节点是叶子：直接删除。
被删除节点只有一个孩子：用孩子替换该节点。
被删除节点有两个孩子：找到右子树的最小节点（或左子树的最大节点）替换该节点，然后删除那个最小节点。

例题7：二叉搜索树（洛谷P5076 普通二叉搜索树简化版）

题目描述您需要写一种数据结构，来维护一些数（绝对值10^9以内）的集合，最开始时集合是空的。其中需要提供以下操作，操作次数 q 不超过 10^4：

查询数 x 的排名（排名定义为集合中小于 x 的数的个数 +1）。注意 x 不一定在集合里。
查询排名为 x 的数。
求 x 的前驱（小于 x 的最大数），若不存在输出 -2147483647。
求 x 的后继（大于 x 的最小数），若不存在输出 2147483647。
插入一个数 x，保证插入前 x 不在集合中。

保证执行 1,3,4 操作时，集合中有至少一个元素。

输入格式第一行一个整数 q。接下来 q 行，每行两个整数 op, x。

输出格式对于操作 1,2,3,4，每行输出一个整数结果。

样例

text

输入： 7 5 1 5 3 5 5 1 3 2 2 3 3 4 3 输出： 2 3 1 5

解释：先插入1,3,5，然后查询3的排名（小于3的个数+1=2），查询排名为2的数是3，查询3的前驱是1，后继是5。

解题思路这是二叉搜索树的经典应用。我们可以直接手写一个二叉搜索树，支持插入、查找排名、查找第k小、前驱、后继。由于 q≤10^4，直接递归操作不会栈溢出，但要注意最坏情况可能退化成链，时间复杂度 O(q^2) 可能勉强能过（10^8量级有点危险），最好用平衡树，但作为教学，我们实现一个简单BST，并希望数据随机。或者可以用C++的STL set，但 set 不支持按排名查询，需要自己写。这里我们实现一个带节点子树大小信息的 BST，以便快速求排名和第k小。

我们可以在每个节点中额外维护一个size字段，表示以该节点为根的子树中的节点总数。这样，求排名时，通过比较左子树大小即可确定。

节点定义

cpp

struct Node { int val; Node *left, *right; int size; // 子树节点个数 Node(int v) : val(v), left(nullptr), right(nullptr), size(1) {} };

插入：递归插入，并更新 size。

查询排名：给定值 x，从根开始：

如果 x <= 当前节点值，则排名在左子树中递归查找（注意左子树所有节点都小于当前节点，所以当前节点的排名要加上左子树大小+1？不，排名定义为小于 x 的个数+1，所以如果 x 小于当前节点，那么当前节点及其右子树都大于 x，所以排名在左子树中。如果 x 等于当前节点，则小于 x 的个数就是左子树大小，排名 = 左子树大小+1。如果 x 大于当前节点，那么小于 x 的个数包括左子树所有节点 + 当前节点（因为当前节点小于 x）+ 右子树中小于 x 的部分，即递归右子树并加上左子树大小+1。

查询第k小：给定排名 k，从根开始：

左子树大小为 L，如果 k <= L，则第k小在左子树；
如果 k == L+1，则当前节点就是第k小；
否则，第k小在右子树，且排名为 k - (L+1)。

前驱：小于 x 的最大数。从根开始，如果 x <= 当前节点，则可能的前驱在左子树；如果 x > 当前节点，则当前节点是一个候选，然后去右子树找更大的候选。

后继：大于 x 的最小数，类似。

代码实现（省略指针操作细节，可自行补充）

由于篇幅，这里给出核心递归函数，完整代码略。

注意事项：由于要支持重复？题目保证插入前不在集合中，所以无需处理重复。

6.2 二叉搜索树的局限性

当插入序列有序时，BST会退化成链表，导致操作 O(n)。为解决此问题，人们发明了平衡二叉搜索树，如AVL树、红黑树、Treap、Splay等。在竞赛中，常用的是 STL 中的 set 和 map，或者手写 Treap 等。但对于初学者，理解普通BST是基础。

7. 表达式树

表达式树是一种特殊的二叉树，用于表示算术表达式。它的叶子节点是操作数（常量或变量），内部节点是运算符。通过遍历表达式树，可以得到不同的表达式形式。

例如，表达式(a+b)*c可以表示为：

text

* / \ + c / \ a b

前序遍历：* + a b c （前缀表达式，波兰式）
中序遍历：a + b * c （中缀表达式，但需要括号保证运算顺序，实际中序遍历输出时需加括号）
后序遍历：a b + c * （后缀表达式，逆波兰式）

例题8：表达式树

假设给定一个合法的后缀表达式（操作数为单个小写字母，运算符为+,-,*,/），请构建表达式树，并输出其前缀表达式和中缀表达式（带括号，保证运算顺序）。

输入样例：

text

ab+c*

输出样例：

text

前缀：*+abc 中缀：(a+b)*c

解题思路后缀表达式构建表达式树的方法：用一个栈，扫描后缀表达式，遇到操作数就创建节点压栈；遇到运算符就弹出两个节点作为右、左孩子（注意顺序），创建运算符节点压栈。最后栈顶即为根节点。

然后输出前缀（前序遍历），中序遍历需要加括号：当访问内部节点时，如果左子树是运算符且优先级低于当前节点，则需要加括号；同理右子树。为了简化，我们可以统一加括号，即中序遍历时输出 (左子树表达式运算符右子树表达式)。这样虽然括号可能多余，但保证了正确性。

代码略（较为简单，可自行实现）。

8. 二叉树的应用进阶

8.1 医院设置（树形DP）

例题9：医院设置（洛谷P1364）

题目描述设有一棵二叉树，如图（略）。圈中的数字表示结点中居民的人口。圈边上数字表示结点编号，现在要求在某个结点上建立一个医院，使所有居民所走的路程之和为最小，同时约定，相邻接点之间的距离为 1。如图中，若医院建在 1 处，则距离和 =4+12+2×20+2×40=136；若医院建在 3 处，则距离和 =4×2+13+20+40=81。

输入格式第一行一个整数 n，表示树的结点数。接下来的 n 行每行描述了一个结点的状况，包含三个整数 w,u,v，其中 w 为居民人口数，u 为左链接（为 0 表示无链接），v 为右链接（为 0 表示无链接）。

输出格式一个整数，表示最小距离和。

样例

text

输入： 5 13 2 3 4 0 0 12 4 5 20 0 0 40 0 0 输出： 81

解题思路这是一个经典的树形DP问题，类似于求树的重心，但这里是带权距离和最小。我们设医院建在节点 i 时的总距离和为 f[i]。直接枚举每个节点作为医院，然后 BFS 计算距离和，复杂度 O(n^2)，n≤100 可行，但我们可以更优雅地用两次 DFS 实现 O(n) 解法。

方法一：朴素枚举 + BFS（n≤100，完全可行）对于每个节点作为医院，用 BFS 求出所有节点到该节点的距离，乘以人口，求和，取最小。

方法二：树形DP（换根法）首先任选一个根（比如1），计算所有节点到根的距离和。设 size[u] 表示以 u 为根的子树的人口总数（包括 u 本身的人口）。则对于根，总距离和 = sum_{所有节点} 人口 * 深度（深度从根算起）。然后考虑将医院从父节点 u 转移到子节点 v，距离和的变化：对于 v 子树内的所有节点，距离减少1（因为更近了），对于 v 子树外的所有节点，距离增加1。所以 f[v] = f[u] - size[v] + (total - size[v]) = f[u] + total - 2*size[v]。其中 total 是所有节点人口总和。

因此，我们只需要一次DFS求出 size 和 f[root]，然后第二次DFS（换根）求出所有 f，取最小值。

代码实现（换根法）

cpp

#include <iostream> #include <vector> #include <algorithm> using namespace std;  const int N = 105; struct Node { int w, left, right; } tree[N]; int n, total; int size[N], f[N]; int ans = 1e9;  void dfs1(int u, int depth) { if (u == 0) return; size[u] = tree[u].w; f[1] += tree[u].w * depth; // 假设医院建在1，计算初始距离和 dfs1(tree[u].left, depth + 1); dfs1(tree[u].right, depth + 1); size[u] += size[tree[u].left] + size[tree[u].right]; }  void dfs2(int u) { if (u == 0) return; if (u != 1) { f[u] = f[tree[u]. ??? 实际上我们需要知道父节点是谁，但这里没有存储父指针，可以换根时传入父节点信息。 } // 正确做法：在 dfs2 中传入父节点，或者用全局数组记录父节点。 }  // 更清晰的做法：先建树并记录父节点，然后换根。 // 这里给出简化版：直接递归计算所有 f，需要知道父节点，我们可以在建树时记录父节点，或者在 dfs2 中传入父节点编号。 // 由于输入给出了左右孩子，我们可以用一个数组 parent[] 记录每个节点的父节点（根节点父为0）。 // 然后在 dfs2 中，对于每个子节点 v，有 f[v] = f[u] + total - 2*size[v]（其中 u 是 v 的父节点）。  int parent[N];  void dfs2(int u) { if (u == 0) return; if (parent[u] != 0) { int p = parent[u]; f[u] = f[p] + total - 2 * size[u]; } ans = min(ans, f[u]); dfs2(tree[u].left); dfs2(tree[u].right); }  int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> tree[i].w >> tree[i].left >> tree[i].right; if (tree[i].left) parent[tree[i].left] = i; if (tree[i].right) parent[tree[i].right] = i; total += tree[i].w; } // 确定根：找 parent 为0的节点，题目隐含根为1，因为输入顺序是从根开始？样例中根是1，但题目没说一定是1，不过通常根为1，我们以1为根。 dfs1(1, 0); ans = f[1]; dfs2(1); cout << ans << endl; return 0; }

注意：dfs1 中 depth 从0开始，表示根到自己的距离为0。

8.2 二叉树的深度、宽度与节点距离

题目（来自洛谷 P3884 二叉树问题）

题目描述如下图所示的一棵二叉树，求其深度、宽度及两个指定节点 x,y 之间的距离。其中宽度表示二叉树上同一层最多的结点个数，节点 u,v 之间的距离表示从 u 到 v 的最短有向路径上向根节点的边数的两倍加上向叶节点的边数。（实际上就是 u 到 LCA 的边数 + v 到 LCA 的边数，但这里定义有点怪，我们按常规 LCA 距离处理即可）

输入格式第一行 n，表示结点个数。接下来 n-1 行每行两个整数 u,v，表示树上存在一条连接 u,v 的边。最后一行两个整数 x,y，表示求 x,y 之间的距离。保证 u 是 v 的父结点。

输出格式输出三行：深度、宽度、x 和 y 之间的距离。

样例略。

解题思路

深度：直接 DFS 求最大深度。
宽度：BFS 记录每一层的节点数，取最大值。
距离：求 LCA（最近公共祖先），然后距离 = depth[x] + depth[y] - 2*depth[lca]。

由于题目保证 u 是 v 的父结点，所以我们可以方便地构建出树。用邻接表存储，然后从根节点 1 开始 DFS 记录深度和父节点，再用倍增或 Tarjan 求 LCA。这里 n≤100，简单 BFS 求深度然后向上找 LCA 即可。

代码略（较基础）。

8.3 二叉树的绘制（洛谷P1185）

题目描述需要用程序来绘制一棵二叉树，它由一棵满二叉树去掉若干结点而成。对于一棵满二叉树，我们需要按照以下要求绘制：

结点用小写字母 o 表示，对于一个父亲结点，用 / 连接左子树，用 \ 连接右子树。
定义 [i,j] 为位于第 i 行第 j 列的某个字符。若 [i,j] 为 / ，那么 [i-1,j+1] 与 [i+1,j-1] 要么为 o ，要么为 /。若 [i,j] 为 \ ，那么 [i-1,j-1] 与 [i+1,j+1] 要么为 o，要么为 \ 。同样，若 [i,j] 为第 1～m-1 层的某个结点 o ，那么 [i+1,j-1] 为 /，[i+1,j+1] 为 \。
对于第 m 层结点也就是叶子结点，若两个属于同一个父亲，那么它们之间由 3 个空格隔开；若两个结点相邻但不属于同一个父亲，那么它们之间由 1 个空格隔开。第 m 层左数第 1 个结点之前没有空格。
最后需要在一棵绘制好的满二叉树上删除 n 个结点（包括这个结点的左右子树，以及与父亲的连接），原有的字符用空格替换。

输入格式第 1 行包含 2 个正整数 m 和 n，为需要绘制的二叉树层数和需要删除的结点数。接下来 n 行，每行两个正整数，表示删除第 i 层的第 j 个结点。

输出格式按照题目要求绘制的二叉树。

样例见原题。

解题思路这是一道复杂的模拟题，需要计算每个节点在画布上的坐标。满二叉树的绘制有固定规律，我们可以先计算出满二叉树所有节点的坐标，然后标记哪些节点被删除，最后根据规则输出画布。

关键点：

满二叉树有 m 层，最后一层有 2^(m-1) 个叶子。
每个节点在画布上的行数可以确定：根节点在第 1 行？题目示例中根节点在第 1 行，但输出有空格？实际上样例输出中，根节点并不是在第 1 行最左边，而是居中。我们需要根据树的大小确定画布的宽度和高度。
父子之间的连线位置需要根据规则放置 '/' 和 ''。

一种常用方法：递归地给每个节点分配一个区间，然后确定其列坐标。例如，根节点在整个画布中间，其左右子树分别在左右半区。具体坐标可以计算：设画布宽度为 W，高度为 H。对于满二叉树，节点行号：根在第 1 行，叶子在第 m 行。每个节点在所在行的列号可以通过递归分配得到。连线字符的位置在两个节点之间。

由于 m≤10，我们可以暴力计算。具体实现较复杂，这里不再展开。

9. 总结与扩展

本文从二叉树的定义出发，详细介绍了其存储结构、遍历方法、经典应用以及多种例题。通过淘汰赛问题，我们看到了完全二叉树在数组中的妙用；通过深度问题，我们练习了递归；通过遍历序列重建二叉树，我们理解了三种遍历的内在联系；通过二叉搜索树，我们掌握了动态集合操作；通过医院设置，我们初步接触了树形DP；通过绘制二叉树，我们体会了模拟题的复杂性。

二叉树是学习更复杂树结构（如堆、并查集、平衡树、B树、哈夫曼树等）的基石。掌握了二叉树，你将能更好地理解递归、分治、动态规划等思想，并为后续学习打下坚实基础。

希望这篇博客能帮助你全面掌握二叉树。如果你有任何疑问或建议，欢迎在评论区留言。让我们一起在编程的路上不断进步！