CC++ & Algorithm

二叉树的遍历

困难0
语言版本：C++
概述：遍历就是按顺序访问二叉树的所有节点，常见的有前序、中序、后序和层序四种方法。

二叉树的遍历：像整理书包一样按顺序访问每个节点

想象你去图书馆找一本书，如果书架上的书没有顺序，你得一本一本翻找，效率很低。二叉树的遍历，就是给树里的每个节点规定一个“参观顺序”，让你能不重复、不遗漏地访问所有节点。常见的有四种方法：前序、中序、后序（深度优先）和层序（广度优先）。它们就像四种不同的“旅行路线”，走完整棵树。

1. 为什么要有遍历？

因为树不是线性的，我们不能像数组或链表那样只用一个for循环。遍历解决两个问题：

  • 按特定顺序处理节点：比如打印家族族谱（从祖先到后代）、计算文件夹总大小（先统计子文件夹）。
  • 查找某个值：遍历时对比每个节点的数据。

生活中的例子：你去朋友家，他家有客厅、卧室、书房等房间，每个房间还有柜子。你要检查每个柜子是否锁好。前、中、后、层序就是四种不同的检查路线。

2. 深度优先遍历：一条路走到黑，再回头

深度优先会用递归，一直往下走，直到没路再返回。就像进一个迷宫，每次只选一条岔路，走到尽头再退回上一个岔路口。三种方法区别在于访问根节点的时机。

  • 前序（根左右）：先看爸爸，再看左儿子，最后看右儿子。
    例子：老师上课点名，先喊班长，再喊班长左边的同学，最后喊右边的。
    应用：复制一棵树（先复制根，再复制左子树和右子树）。

  • 中序（左根右）：先看左儿子，再看爸爸，最后看右儿子。
    例子：按学号从小到大排队，先报左边小组，再报中间，最后右边。
    应用：二叉搜索树的中序遍历结果是有序的（从小到大）。

  • 后序（左右根）：先看左儿子，再看右儿子，最后看爸爸。
    例子：你整理书包，先把所有科目的书按顺序放进书包，最后拉上拉链（根）。
    应用：删除树（先删子节点，再删根节点）。

三种方法用递归写非常简单，代码和原有内容一致（保留并稍作调整，增加注释）：

# 定义二叉树节点
class TreeNode:
    def __init__(self, val):          # val: 节点值
        self.val = val
        self.left = None              # left: 左子节点
        self.right = None             # right: 右子节点

def preorder(node):                   # 前序遍历 (根左右)
    if node is None:                  # 如果节点为空，直接返回
        return
    print(node.val, end=' ')          # 访问根节点
    preorder(node.left)               # 递归左子树
    preorder(node.right)              # 递归右子树

def inorder(node):                    # 中序遍历 (左根右)
    if node is None:
        return
    inorder(node.left)                # 递归左子树
    print(node.val, end=' ')          # 访问根节点
    inorder(node.right)               # 递归右子树

def postorder(node):                  # 后序遍历 (左右根)
    if node is None:
        return
    postorder(node.left)              # 递归左子树
    postorder(node.right)             # 递归右子树
    print(node.val, end=' ')          # 访问根节点

3. 广度优先遍历（层序）：从上到下，一层层扫荡

层序遍历更像“扫地机器人”式扫描：先访问第一层（根），再第二层从左到右，逐层往下。它需要借助队列（先进先出）来实现——像排队买奶茶，先到先服务。

例子：广播体操排舞，老师先喊第一排（根），再喊第二排从左到右，依次类推。

from collections import deque

def level_order(root):              # 层序遍历
    if not root:                    # 树为空直接返回
        return
    queue = deque([root])           # queue: 存放待访问节点的队列
    while queue:                    # 只要队列不为空
        node = queue.popleft()      # 取出队首节点
        print(node.val, end=' ')    # 访问该节点
        if node.left:               # 左子节点存在则入队
            queue.append(node.left)
        if node.right:              # 右子节点存在则入队
            queue.append(node.right)

4. 常见错误（新手容易踩的坑）

  1. 忘记递归终止条件：递归函数里一定要判断 node is None，否则会无限递归导致程序崩溃。
    ❌ 错误：def preorder(node): print(node.val); ...
    ✅ 正确：先判断 if node is None: return

  2. 混淆左右子树顺序：中序和后序容易把左右搞反。记住：中序（左根右）是先访问左子树再根；后序（左右根）最后才是根。

  3. 层序遍历忘记用队列：有人试图用递归实现层序，很难控制顺序。正确做法是用队列手动模拟。

  4. 访问空节点的属性：如果 node 是 None，却写了 node.left 会报错。一定要先判断 if node 再访问。

5. 完整可运行示例

下面创建一棵树，并输出四种遍历结果（沿用你给的树结构，节点值用字母表示更直观）：

      A
     / \
    B   C
   / \
  D   E

完整代码：

from collections import deque

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

# ---------- 前中后序 ----------
def preorder(node):
    if node is None:
        return
    print(node.val, end=' ')
    preorder(node.left)
    preorder(node.right)

def inorder(node):
    if node is None:
        return
    inorder(node.left)
    print(node.val, end=' ')
    inorder(node.right)

def postorder(node):
    if node is None:
        return
    postorder(node.left)
    postorder(node.right)
    print(node.val, end=' ')

# ---------- 层序 ----------
def level_order(root):
    if not root:
        return
    queue = deque([root])
    while queue:
        node = queue.popleft()
        print(node.val, end=' ')
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

# ---------- 构建树 ----------
root = TreeNode("A")
root.left = TreeNode("B")
root.right = TreeNode("C")
root.left.left = TreeNode("D")
root.left.right = TreeNode("E")

# ---------- 输出 ----------
print("前序:", end=' '); preorder(root)      # A B D E C
print("\n中序:", end=' '); inorder(root)      # D B E A C
print("\n后序:", end=' '); postorder(root)    # D E B C A
print("\n层序:", end=' '); level_order(root)  # A B C D E

运行结果：

前序: A B D E C 
中序: D B E A C 
后序: D E B C A 
层序: A B C D E

你可以对照树的结构，体会每种顺序的“路线”。

6. 相关指引

  • 树的构建：如何用代码把值变成树？参考“二叉树的基本定义和创建”。
  • 递归：遍历的核心思想，如果你对递归不熟，可以先看“函数的递归调用”。
  • 队列：层序遍历中用的 deque 是 Python 内置的双端队列，了解它的 popleft() 和 append() 方法。
  • 二叉搜索树：中序遍历的特殊应用——输出有序序列。

试一试：把树改成数字节点，比如根10、左5、右15，观察中序遍历的输出是不是从小到大？这就用到了二叉搜索树的性质。

例题精讲

1单选题

一棵二叉树的前序遍历序列为ABDCEF，中序遍历序列为DBAECF，则其后序遍历序列是？

ADBEFCA
BDBEACF
CABDCEF
DEDBFCA
2判断题

已知一棵二叉树的前序遍历序列和后序遍历序列，可以唯一确定这棵二叉树。

3单选题

以下哪种遍历方式需要借助队列来实现？

A前序遍历
B中序遍历
C后序遍历
D层序遍历
4判断题

后序遍历二叉树时，访问根节点的操作发生在遍历完其右子树之后。

5填空题
请完成以下中序遍历二叉树的递归函数（二叉树节点定义已给出）：
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def inorder(root):
    if root is None:
        return
    inorder(root.left)
    print(___)
    inorder(root.right)