511 二叉树遍历序列的性质

二叉树遍历序列的性质

基本定义

• 前序遍历（Preorder）：根节点 → 左子树 → 右子树
• 中序遍历（Inorder）：左子树 → 根节点 → 右子树
• 后序遍历（Postorder）：左子树 → 右子树 → 根节点

单个序列的重要性质

前序遍历性质

• 序列的第一个节点必定是根节点
• 任意节点在序列中出现在其所有子孙节点之前
• 若某节点是其父节点的左子节点，它在序列中紧跟在其父节点之后

中序遍历性质

• 对于二叉搜索树 (BST)，中序遍历得到的是递增序列
• 任意节点的左子树中所有节点在该节点前面，右子树中所有节点在该节点后面
• 单独一个中序遍历序列不能唯一确定一棵二叉树

后序遍历性质

• 序列的最后一个节点必定是根节点
• 任意节点在序列中出现在其所有子孙节点之后
• 适合用于释放/删除树，因为总是先处理子节点再处理父节点

序列组合的性质

前序 + 中序组合

305 栈的应用

二叉树的前序遍历和中序遍历对应入栈和出栈次序，也就是说，已知前序序列，那么可能的二叉树棵数就等于其出栈顺序个数 卡特兰数（Catalan number）

• 可以唯一确定一棵二叉树
• 前序确定根节点，中序可分割左右子树
• 树的重构算法基础：递归地识别子树的根节点和范围

后序 + 中序组合

• 可以唯一确定一棵二叉树
• 后序的最后一个元素是根节点，中序可分割左右子树

前序 + 后序组合

• 对于一般二叉树，不能唯一确定树结构
• 对于满二叉树（每个非叶节点都有两个子节点），可以唯一确定

其他特性

• 三种遍历的序列长度都等于树中节点总数
• 叶子节点在三种遍历序列中的相对顺序相同
• 前序遍历的第一个节点和后序遍历的最后一个节点相同（都是根节点）
• 知道一棵树的形状，任意两种遍历序列可推导出第三种

二叉树遍历序列编号的性质

前序遍历

在前序遍历（根 - 左 - 右）中，假设某节点编号为 $k$，那么：

1. 根节点性质：整棵树的根节点编号始终为 1
2. 左右子树编号区间：

• 左子树的所有节点编号形成连续区间：$[k+1,k+L]$（其中 $L$ 是左子树节点数）
• 右子树的所有节点编号形成连续区间：$[k+L+1,k+L+R]$（其中 $R$ 是右子树节点数）

3. 直接子节点性质：

• 左子节点的编号：$k+1$（紧跟在父节点之后）
• 右子节点的编号：$k+L+1$（左子树之后的第一个）

中序遍历

在中序遍历（左 - 根 - 右）中，假设某节点编号为 $k$，那么：

1. 根节点性质：整棵树的根节点编号为 $L+1$（其中 $L$ 是左子树节点数）
2. 左右子树编号区间：

• 左子树的所有节点编号形成连续区间：$[k-L,k-1]$
• 右子树的所有节点编号形成连续区间：$[k+1,k+R]$

3. 直接子节点性质：

• 左子节点所在子树的最大编号为 $k-1$
• 右子节点所在子树的最小编号为 $k+1$

4. 特殊性质：在二叉搜索树中，节点的中序编号恰好对应其值的大小顺序

后序遍历

在后序遍历（左 - 右 - 根）中，假设某节点编号为 $k$，那么：

1. 根节点性质：整棵树的根节点编号等于节点总数 $n$
2. 左右子树编号区间：

• 左子树的所有节点编号形成连续区间：$[k-L-R,k-R-1]$
• 右子树的所有节点编号形成连续区间：$[k-R,k-1]$

3. 直接子节点性质：

• 右子节点的编号为 $k-1$（紧邻父节点）
• 左子节点所在子树的最大编号为 $k-R-1$

4. 特殊性质：任何节点的编号都大于其所有子孙节点的编号

通用性质

1. 子树连续性：在任何遍历序列中，一棵子树的所有节点编号总是连续的
2. 节点数关系：对任意节点，设其左子树节点数为 $L$，右子树节点数为 $R$，则以该节点为根的子树总节点数为 $L+R+1$
3. 递归性质：以上性质对树中的每个子树都成立

二叉树序列相同的情况辨析

1. 两序列相同的情况

前序序列 = 中序序列：右斜树

A
 \
  B
   \
    C
     \
      D

解释：当所有节点都没有左子树时，前序遍历 (根 - 左 - 右) 和中序遍历 (左 - 根 - 右) 会产生相同序列，因为 ” 左 ” 为空，使得两个遍历序列都变为 ” 根 - 右 “。

中序序列 = 后序序列：左斜树

      A
     /
    B
   /
  C
 /
D

解释：当所有节点都没有右子树时，中序遍历 (左 - 根 - 右) 和后序遍历 (左 - 右 - 根) 会产生相同序列，因为 ” 右 ” 为空，使得两个遍历序列都变为 ” 左 - 根 “。

前序序列 = 后序序列：单节点树

A

解释：只有当树只有一个节点时，前序和后序才会相同，因为此时没有左右子树，三种遍历都只有根节点。

2. 两序列相反的情况

前序序列与中序序列相反：左斜树

      A
     /
    B
   /
  C
 /
D

解释：在左斜树中，前序是从根向下 (A→B→C→D)，而中序是从叶向上 (D→C→B→A)，它们正好相反。

中序序列与后序序列相反：右斜树

A
 \
  B
   \
    C
     \
      D

解释：在右斜树中，中序是从上到下 (A→B→C→D)，而后序是从下到上 (D→C→B→A)，它们正好相反。

前序序列与后序序列相反：每个非叶子节点最多只有一个子节点

既可以是左斜树:

      A
     /
    B
   /
  C
 /
D

也可以是右斜树:

A
 \
  B
   \
    C
     \
      D

解释：

• 左斜树：前序 (A→B→C→D) 与后序 (D→C→B→A) 相反
• 右斜树：前序 (A→B→C→D) 与后序 (D→C→B→A) 相反

有转折的情况：

当二叉树既不是严格的左斜树也不是严格的右斜树，但仍满足前序与后序序列相反的条件时，树的形态可能为：

      A
    /
  B
   \
    C
      \
       D

分析：

• 前序遍历：A → B → C → D
• 后序遍历：D → C → B → A
• 序列仍然完全相反

一般规律： 前序序列与后序序列相反的充要条件是：二叉树中每个非叶子节点最多只有一个子节点。

具体包括：

1. 左斜树：每个节点最多只有左子节点
2. 右斜树：每个节点最多只有右子节点
3. 混合单支树：每个节点最多只有一个子节点（可以是左子节点或右子节点）

数学证明： 设二叉树有 $n$ 个节点，前序序列为 $P=p_1,p_2,...,p_n$，后序序列为 $Q=q_1,q_2,...,q_n$。

若 $P$ 与 $Q$ 相反，则 $p_i=q_{n+1-i}$ 对所有 $i$ 成立。

由于前序遍历根节点最先访问，后序遍历根节点最后访问，所以 $p_1=q_n$（根节点）。

对于任意非叶子节点，若其既有左子树又有右子树，则在前序遍历中，该节点后紧跟左子树的根节点；在后序遍历中，该节点前紧邻右子树的根节点。这会破坏序列相反的性质。

因此，每个非叶子节点最多只能有一个子节点。