树与二叉树详解：性质、存储、遍历与递归思想

Lichermione2026-08-212026-08-21

树用于表达一对多的层次关系，文件目录、组织架构、语法树和索引结构都离不开它。二叉树则把每个节点的孩子数限制为最多两个，却由此衍生出堆、二叉搜索树、AVL 树和红黑树等重要结构。本文从术语与性质入手，重点理解四种遍历及其代码实现。

1. 树的定义

树是由 $n;(n\ge0)$ 个节点组成的有限集合。非空树满足：

有且仅有一个根节点；
除根外，其余节点可分成若干互不相交的子树；
每棵子树本身仍是一棵树。

这一定义天然递归，因此树的许多算法也采用递归描述。

2. 基本术语

术语	含义
节点的度	该节点拥有的子树（孩子）数量
树的度	所有节点度数的最大值
叶节点	度为 0 的节点
分支节点	度不为 0 的节点
父节点、孩子节点	相邻层之间的直接上下级关系
兄弟节点	具有同一个父节点的节点
祖先、后代	从根到某节点的路径上产生的间接关系
深度	从根到该节点所经过的边数，本文规定根深度为 0
高度	从节点到最远叶节点的边数；空树高度可约定为 -1
森林	若干棵互不相交的树组成的集合

教材中也常规定根位于第 1 层，并用层数表示高度。不同约定会让结果相差 1，答题或设计接口时应先明确采用“节点数”还是“边数”。

3. 树的常见表示方法

3.1 双亲表示法

每个节点记录父节点下标。它适合快速向上查找，但枚举孩子需要扫描或额外索引。

3.2 孩子表示法

每个节点保存所有孩子的列表。孩子数不固定时，可以用动态数组或链表。

3.3 孩子—兄弟表示法

每个节点只维护两个指针：第一个孩子和下一个兄弟。

typedef struct TreeNode {
    int value;
    struct TreeNode *first_child;
    struct TreeNode *next_sibling;
} TreeNode;

任意多叉树都能转换成这种“左孩子—右兄弟”形式，从而用二叉链式结构表达。

4. 二叉树

二叉树是一个有限节点集合，它要么为空，要么由根节点、左子树和右子树组成。每个节点最多有两个孩子，且左右子树有顺序之分。

只有一个孩子时，“它是左孩子还是右孩子”仍是结构的一部分，不能随意互换。

typedef struct BinaryNode {
    int value;
    struct BinaryNode *left;
    struct BinaryNode *right;
} BinaryNode;

如果算法经常需要从孩子返回父节点，还可以增加 parent 指针，形成三叉链结构。

5. 特殊二叉树

5.1 满二叉树（完美二叉树）

若每一层节点数都达到最大值，则为满二叉树。根位于第 1 层、共有 $h$ 层时：

$$
n=2^h-1
$$

英文资料中常称为 perfect binary tree。另一个容易混淆的概念是 full/strict binary tree，它通常表示每个节点要么没有孩子，要么恰有两个孩子，并不要求所有叶子同层。

5.2 完全二叉树

除最后一层外，其余各层都满；最后一层的节点从左到右连续排列。满二叉树一定是完全二叉树，反之不成立。

完全二叉树适合存入数组。若根下标为 0，则节点 i 的位置关系为：

1
2
3

左孩子：2*i + 1
右孩子：2*i + 2
父节点：(i - 1) / 2（i > 0）

堆正是利用这种存储方式，无需显式保存指针。

6. 二叉树的重要性质

设根位于第 1 层：

第 $i$ 层最多有 $2^{i-1}$ 个节点；
高度为 $h$ 的二叉树最多有 $2^h-1$ 个节点；
任意非空二叉树中，若叶节点数为 $n_0$、度为 2 的节点数为 $n_2$，则 $n_0=n_2+1$；
有 $n$ 个节点的完全二叉树高度为 $\lfloor\log_2n\rfloor+1$。

第三条可由边数推导。设度为 1 的节点数为 $n_1$，总节点数为 $n_0+n_1+n_2$；除根外每个节点都有一条入边，所以边数既等于 $n-1$，也等于 $n_1+2n_2$。整理即可得到 $n_0=n_2+1$。

7. 深度优先遍历

对当前节点记作 N、左子树记作 L、右子树记作 R：

前序遍历：NLR，先访问根，再遍历左右子树；
中序遍历：LNR，先左子树，再访问根，最后右子树；
后序遍历：LRN，先左右子树，最后访问根。

7.1 递归模板

void preorder(const BinaryNode *root)
{
    if (root == NULL) {
        return;
    }
    visit(root);
    preorder(root->left);
    preorder(root->right);
}

中序和后序只需移动 visit(root) 的位置。每个节点被处理一次，时间复杂度为 $O(n)$；递归栈与树高成正比，为 $O(h)$。平衡树中 $h=O(\log n)$，极端退化时 $h=O(n)$。

7.2 迭代前序遍历

使用显式栈保存稍后访问的节点：

根入栈
while 栈非空：
    弹出并访问节点
    右孩子入栈
    左孩子入栈

右孩子先入栈，是因为栈后进先出，左孩子需要先被处理。

7.3 迭代中序遍历

不断把左链压栈；无法继续向左时弹出栈顶并访问，再转向其右子树。这个过程显式模拟了递归函数暂停与恢复的位置。

7.4 迭代后序遍历

后序必须确认左右子树都已处理后才能访问根。常见做法包括：

两个栈；
一个栈加 last_visited 指针；
先得到“根—右—左”，再反转为“左—右—根”。

8. 层序遍历

层序遍历从上到下、每层从左到右访问节点，本质是广度优先搜索：

根节点入队；
队头出队并访问；
非空左、右孩子依次入队；
重复直到队列为空。

时间复杂度为 $O(n)$。队列最大长度等于树的最大宽度，最坏额外空间为 $O(n)$。

9. 可运行的遍历与统计示例

#include <assert.h>
#include <stddef.h>
#include <stdio.h>

typedef struct BinaryNode {
    char value;
    struct BinaryNode *left;
    struct BinaryNode *right;
} BinaryNode;

static void preorder(const BinaryNode *root)
{
    if (root == NULL) {
        return;
    }
    putchar(root->value);
    preorder(root->left);
    preorder(root->right);
}

static void inorder(const BinaryNode *root)
{
    if (root == NULL) {
        return;
    }
    inorder(root->left);
    putchar(root->value);
    inorder(root->right);
}

static void postorder(const BinaryNode *root)
{
    if (root == NULL) {
        return;
    }
    postorder(root->left);
    postorder(root->right);
    putchar(root->value);
}

static size_t tree_size(const BinaryNode *root)
{
    return root == NULL ? 0 : 1 + tree_size(root->left) + tree_size(root->right);
}

static size_t leaf_count(const BinaryNode *root)
{
    if (root == NULL) {
        return 0;
    }
    if (root->left == NULL && root->right == NULL) {
        return 1;
    }
    return leaf_count(root->left) + leaf_count(root->right);
}

static size_t tree_height_nodes(const BinaryNode *root)
{
    if (root == NULL) {
        return 0;
    }
    size_t left = tree_height_nodes(root->left);
    size_t right = tree_height_nodes(root->right);
    return 1 + (left > right ? left : right);
}

int main(void)
{
    BinaryNode d = {'D', NULL, NULL};
    BinaryNode e = {'E', NULL, NULL};
    BinaryNode f = {'F', NULL, NULL};
    BinaryNode b = {'B', &d, &e};
    BinaryNode c = {'C', NULL, &f};
    BinaryNode a = {'A', &b, &c};

    preorder(&a);  putchar('\n'); /* ABDECF */
    inorder(&a);   putchar('\n'); /* DBEACF */
    postorder(&a); putchar('\n'); /* DEBFCA */
    assert(tree_size(&a) == 6);
    assert(leaf_count(&a) == 3);
    assert(tree_height_nodes(&a) == 3);
    return 0;
}

示例中的节点位于自动存储期，因此不需要 free；实际动态建树时，应使用后序顺序释放：先释放左右子树，再释放当前节点。

10. 根据遍历序列重建二叉树

仅凭一种遍历序列通常无法唯一确定普通二叉树。若节点值互不相同，则以下组合可以唯一重建：

前序 + 中序；
后序 + 中序。

前序的第一个元素或后序的最后一个元素确定根，再到中序序列中找到根的位置，即可划分左右子树并递归重建。

仅凭前序 + 后序通常不能唯一确定，因为单孩子节点究竟是左孩子还是右孩子存在歧义。若额外保证每个非叶节点都有两个孩子，才可能唯一确定。

朴素重建每层在线性扫描中序数组，最坏时间为 $O(n^2)$；使用哈希表预存“值到中序下标”的映射，可把期望时间降到 $O(n)$。

11. 常见递归题型

11.1 节点数

1 2	size(root) = 0 root 为空 size(root) = 1 + size(left) + size(right) 否则

11.2 最大深度

1 2	height(root) = 0 root 为空 height(root) = 1 + max(height(left), height(right)) 否则

11.3 判断平衡

如果先为每个节点重复计算子树高度，最坏会达到 $O(n^2)$。更好的方法是后序遍历：一次返回高度，并用特殊值表示“不平衡”，总时间 $O(n)$。

11.4 判断两棵树相同

当前节点值相同，且左子树相同、右子树相同；空指针的组合决定递归基线。时间为 $O(\min(n,m))$ 到 $O(n+m)$，具体取决于何时发现差异。

12. 常见误区

混淆树的高度是按边数还是节点数计算；
把“满二叉树”和“每个节点度为 0 或 2 的二叉树”混为一谈；
认为二叉树一定有序；只有二叉搜索树才有键值顺序约束；
在普通二叉树上使用数组导致大量空洞；
递归没有空节点基线，或忘记计算递归栈空间；
层序遍历误用栈，导致顺序变成深度优先；
动态建树后只释放根节点，造成子树泄漏。

树题看似变化很多，但绝大多数都可以归结为：当前节点要从左右子树得到什么信息，又要向父节点返回什么信息。先写清递归定义和空树行为，再决定使用前序、中序还是后序，代码通常会自然出现。