二叉树及其遍历

二叉树及其遍历

二叉树的定义与基本性质；二叉树的表示与存储；二叉树的遍历：前序、中序、后序。

概念

二叉树是每个结点最多有两个子树，且分左右子树的树形结构。空树也是二叉树。存储可用链式（左右指针）或顺序（数组下标 $i$ 的左孩子在 $2i$、右孩子在 $2i+1$，仅对完全二叉树省空间）。遍历是按固定规则访问每个结点一次：前序根—左—右，中序左—根—右，后序左—右—根。已知任意两种遍历（通常含中序）常可唯一确定二叉树结构，再求第三种。与 cspj.ds.tree 的区别：二叉树有严格的「至多两个孩子」与左右之分；与 cspj.ds.special-tree 的区别：本叶讲一般二叉树及其遍历，完全二叉树、哈夫曼树、BST 的专用性质归特殊树。

CSP-J 常考

• cspj-r1-2019 第 14 题：给后序与中序序列，求前序遍历结果（字母结点经典题）。
• cspj-r1-2023 第 11 题：给前序与中序，选正确的后序序列。
• cspj-r1-2024 第 12 题：同上形态，七个结点 [A…G] 的三种遍历互推。

struct Node { char val; Node *l, *r; };

void preOrder(Node* t) {       // 前序
    if (!t) return;
    cout << t->val;
    preOrder(t->l);
    preOrder(t->r);
}

void inOrder(Node* t) {        // 中序
    if (!t) return;
    inOrder(t->l);
    cout << t->val;
    inOrder(t->r);
}

易错点

• 还原树时：前序第一个（或后序最后一个）是根；在中序里根把序列分成左子树、右子树区间，递归时区间边界 off-by-one 最常见。
• 只有前序+后序不能唯一确定二叉树（缺中序时左右子树单链时会歧义）——初赛若给三种里两种，通常含中序。
• 顺序存储的下标公式 $2i$ / $2i+1$ 只对按完全二叉树规则填数组时恒成立；一般二叉树会留空位，不要生搬。
• 遍历序列长度必须等于结点数，推根时数结点个数帮助核对区间长度。