Python树的遍历 - 六级 | C++ & Algorithm 编程研习社

和家族树一起学遍历：用Python拜访树的每个节点

你一定见过家族族谱吧？从最老的祖先开始，一代一代往下分叉，每个人都有自己的孩子，孩子又有自己的孩子……在计算机里，这种结构就叫“树”（Tree）。树有一个“根”节点，下面分出“左子树”和“右子树”，就像一个人的孩子分成了老大和老二。我们需要把树里的每个节点都“拜访”一次，这个过程就叫树的遍历。遍历有什么用呢？比如你要统计家族里所有人的年龄、找出名字最长的人、或者把所有名字按顺序打印出来，都需要遍历。

三种最常用的遍历方式是：前序遍历、中序遍历、后序遍历。它们就像三条不同的“拜访路线”，从祖先一直走到孙子。

1. 树的节点长什么样？

首先，我们要用Python代码定义一棵树。每个节点有一个名字（比如“曾祖父”），还可能有一个左孩子和一个右孩子。如果某个孩子不存在，就用 None 表示。

class Node:
    def __init__(self, name):
        self.name = name       # 节点的名字，比如“曾祖父”
        self.left = None       # 左孩子（没有就是None）
        self.right = None      # 右孩子（没有就是None）

就像在纸上画一个圆圈，里面写名字，再从圆圈下面画出两个分支指向左、右孩子。

2. 三种遍历方式：怎么“拜访”才不重不漏？

下面我们用同一个家族例子来理解：曾祖父（根）有两个儿子：爷爷（左）和二爷爷（右）。爷爷有两个儿子：爸爸（左）和叔叔（右）。二爷爷也有两个儿子：堂伯（左）和堂叔（右）。注意这里的“左”和“右”只是为了区分，不是真的左手右手。

? 前序遍历：先看根，再看左，再看右

记忆口诀：根左右。

先拜访当前节点（比如曾祖父）。
然后去拜访左子树（所有左子孙）。
最后拜访右子树（所有右子孙）。

就像大家族聚餐，曾祖父先发言，然后按辈分从大到小、从左到右轮流发言。爷爷是左分支的老大，他讲完了才轮到右分支的二爷爷。

def preorder(node):
    """前序遍历：根 -> 左 -> 右"""
    if node:                       # 如果节点不为空
        print(node.name, end=' ')  # 拜访当前节点
        preorder(node.left)        # 递归遍历左子树
        preorder(node.right)       # 递归遍历右子树

对于我们的家族树，前序结果：

曾祖父 爷爷 爸爸 叔叔 二爷爷 堂伯 堂叔

? 中序遍历：先看左，再看根，再看右

记忆口诀：左根右。

先去拜访左子树中的所有节点。
然后拜访当前节点。
最后拜访右子树中的所有节点。

这就像班级按年龄从小到大排队：左子树代表年轻一代，根是上一代，右子树代表更老一代（这个比喻要注意：这里的“左”不一定真的年龄小，只是约定）。对于二叉树，中序遍历的结果会按照节点值的顺序从小到大排列（如果节点值有大小的话）。但在我们的家族树里，名字没有大小排序，它只是按照我们设定的结构来“拜访”。

def inorder(node):
    """中序遍历：左 -> 根 -> 右"""
    if node:
        inorder(node.left)         # 先遍历左子树
        print(node.name, end=' ')  # 拜访当前节点
        inorder(node.right)        # 再遍历右子树

对于家族树，中序结果：

爸爸 爷爷 叔叔 曾祖父 堂伯 二爷爷 堂叔

注意：爷爷的左孩子是爸爸，右孩子是叔叔，所以“爸爸爷爷叔叔”按左、根、右顺序输出。然后根（曾祖父），然后右子树（二爷爷）左孩子堂伯、右孩子堂叔。

? 后序遍历：先看左，再看右，最后看根

记忆口诀：左右根。

先去拜访左子树。
然后拜访右子树。
最后拜访当前节点。

就像吃完大餐后，小孩子先离席，大人最后收拾。左、右子树的所有子孙都“拜访”完了，才轮到根节点自己。

def postorder(node):
    """后序遍历：左 -> 右 -> 根"""
    if node:
        postorder(node.left)       # 先遍历左子树
        postorder(node.right)      # 再遍历右子树
        print(node.name, end=' ')  # 最后拜访当前节点

对于家族树，后序结果：

爸爸 叔叔 爷爷 堂伯 堂叔 二爷爷 曾祖父

注意：曾祖父是最后一个被拜访的，因为根最后才处理。

3. 递归是怎么工作的？——像“传话筒”一样

这三种遍历都用到了递归：函数自己调用自己。想象一下，你拿到一张名单“曾祖父”，你问他“你的左孩子是谁？”他说“是爷爷”。然后你又问爷爷“你的左孩子是谁？”……就这样一直问到没有孩子为止。然后一层一层返回结果。这就是递归的“递进”和“回归”。

递归写起来很简单，但新手容易犯两个错误：

忘记判断节点是否为None：如果直接 preorder(node.left) 而 node.left 是 None，那么 node 就会变成 None，接下来代码会报错（None 没有 name 属性）。所以必须在最开始用 if node: 检查。
顺序搞混：三种遍历只是 print 语句的位置不同：前序先打印，中序在中间打印，后序最后打印。可以多写几遍，或者用口诀“根左右、左根右、左右根”来记。

4. 完整可运行的代码（把家族树串起来）

下面将前面的所有代码拼接成一个完整的程序，加上主函数，你直接复制运行就能看到结果。

class Node:
    def __init__(self, name):
        self.name = name       # 节点的名字，比如“曾祖父”
        self.left = None       # 左孩子
        self.right = None      # 右孩子

# 前序遍历：根 -> 左 -> 右
def preorder(node):
    if node:                       # 节点不为空才执行
        print(node.name, end=' ')  # 拜访根
        preorder(node.left)        # 递归左
        preorder(node.right)       # 递归右

# 中序遍历：左 -> 根 -> 右
def inorder(node):
    if node:
        inorder(node.left)         # 遍历左
        print(node.name, end=' ')  # 拜访根
        inorder(node.right)        # 遍历右

# 后序遍历：左 -> 右 -> 根
def postorder(node):
    if node:
        postorder(node.left)       # 遍历左
        postorder(node.right)      # 遍历右
        print(node.name, end=' ')  # 拜访根

# 构建家族树
root = Node("曾祖父")
root.left = Node("爷爷")
root.right = Node("二爷爷")
root.left.left = Node("爸爸")
root.left.right = Node("叔叔")
root.right.left = Node("堂伯")
root.right.right = Node("堂叔")

# 测试三种遍历
print("前序（根-左-右）：", end='')
preorder(root)
print()   # 输出：曾祖父 爷爷 爸爸 叔叔 二爷爷 堂伯 堂叔

print("中序（左-根-右）：", end='')
inorder(root)
print()   # 输出：爸爸 爷爷 叔叔 曾祖父 堂伯 二爷爷 堂叔

print("后序（左-右-根）：", end='')
postorder(root)
print()   # 输出：爸爸 叔叔 爷爷 堂伯 堂叔 二爷爷 曾祖父

你可以把代码中的名字换成你自己的家族（比如“外公”、“舅舅”、“表弟”），或者换成你喜欢的动漫角色（比如“光头强”、“熊大”、“熊二”），看看遍历结果有什么变化。

5. 生活中的其他例子

前序就像老师按顺序点名：先点班长，再点第一组，再点第二组。班长就是根，第一组是左子树，第二组是右子树。
中序就像学校体检按身高排队：最矮的（左）先测，然后中等（根），最后最高的（右）。如果节点里存的是分数，中序遍历就能按分数从小到大输出。
后序就像整理书包：先把里面的书都拿出来（左、右），最后合上书包（根）。在计算机里，后序遍历常用于删除整棵树（先删孩子，再删自己）。

6. 去哪里继续探索？

掌握了这三种基本的遍历，你还可以尝试：

层序遍历：一层一层地拜访（先曾祖父，再爷爷和二爷爷，再爸爸、叔叔、堂伯、堂叔）。这需要用到一个叫“队列”的工具。
非递归遍历：用“栈”来代替递归，能避免递归层数太深导致程序崩溃。
二叉搜索树：如果节点值是有大小顺序的，中序遍历就能得到有序列表。很多快速查找程序都用到了这个特性。

继续学习“二叉树”、“递归”和“栈”，你就能写出更厉害的树算法啦！快动手试试吧。

例题精讲