6 树结构 · 教材 · 算法与数据结构教材

树是一种表达层级关系的数据结构。文件目录、组织架构、家谱、表达式和搜索索引，都可以用树来表示。

树与数组、链表的最大区别是：一个节点可以连接多个子节点，数据不再排成一条直线。

原书中的树结构使用指针和递归来说明。本文用 Python 对象引用来实现同样的关系，并把每个算法写成可以直接运行的示例。

理解树的关键，不是先记住各种术语，而是学会把“一个节点和它的子树”看成一个可以递归处理的整体。

1. 树的基本概念

下面是一棵树：

常见术语如下：

根（root）：最上面的节点，本例中是 A；
父节点（parent）：直接连接到子节点上方的节点，例如 B 是 E 的父节点；
子节点（child）：直接连接在某个节点下面的节点；
兄弟节点（sibling）：拥有同一个父节点的节点，例如 B、C、D；
叶节点（leaf）：没有子节点的节点，例如 C、D、E、F；
边（edge）：连接两个节点的关系；
子树（subtree）：从某个节点及其后代节点构成的树；
深度（depth）：从根到节点经过的边数；
高度（height）：从节点向下到最远叶节点的最长路径长度。

根的深度通常为 0。空树没有节点；只有一个根节点的树高度为 0。

2. 有序树和无序树

如果同一个父节点的子节点有明确的左右或先后顺序，就是有序树：

    A                 A
   / \               / \
  B   C             C   B

在有序树中，这两棵树不同，因为 B 和 C 的位置不同。

如果只关心“谁是谁的子节点”，不关心兄弟节点的顺序，则它们可以被视为同一棵无序树。

程序实现前必须先明确：顺序是否具有意义。表达式树、二叉搜索树和文件列表通常都需要保留顺序。

3. 二叉树和 Python 节点类

二叉树是一种特殊的树：每个节点最多有两个子节点，通常称为左子节点和右子节点。

在 Python 中，可以这样定义二叉树节点：

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

构造一棵小树：

root = TreeNode(
    "A",
    left=TreeNode("B", TreeNode("D"), TreeNode("E")),
    right=TreeNode("C"),
)

如果某个子节点不存在，对应属性就是 None。

二叉树不是“每个节点必须有两个子节点”的树；“最多两个”意味着 0 个、1 个或 2 个都可以。

4. 树的递归性质

树非常适合用递归描述：

一棵空树是一棵树；
一个节点以及它的若干棵子树可以组成一棵新的树。

对二叉树来说，可以具体理解为：

None 代表空树；
一个节点加上一棵左子树和一棵右子树，组成一棵二叉树。

所以很多树算法都遵循同一个模式：

处理当前节点；
递归处理左子树；
递归处理右子树。

递归的终止条件通常是：

def visit(node):
    if node is None:
        return

5. 三种深度优先遍历

考虑下面这棵树：

5.1 先序遍历

顺序是：

访问当前节点；
遍历左子树；
遍历右子树。

结果为：

A → B → C → D

def preorder(root):
    result = []

    def visit(node):
        if node is None:
            return

        result.append(node.value)
        visit(node.left)
        visit(node.right)

    visit(root)
    return result


root = TreeNode("A", TreeNode("B", TreeNode("C")), TreeNode("D"))
print(preorder(root))  # ['A', 'B', 'C', 'D']

先序遍历常用于：

复制一棵树；
输出树的结构；
生成前缀表达式。

5.2 中序遍历

顺序是：

遍历左子树；
访问当前节点；
遍历右子树。

结果为：

C → B → A → D

def inorder(root):
    result = []

    def visit(node):
        if node is None:
            return

        visit(node.left)
        result.append(node.value)
        visit(node.right)

    visit(root)
    return result


print(inorder(root))  # ['C', 'B', 'A', 'D']

中序遍历对二叉搜索树尤其重要：如果二叉搜索树满足左小右大的规则，中序遍历会按升序输出所有元素。

5.3 后序遍历

顺序是：

遍历左子树；
遍历右子树；
访问当前节点。

结果为：

C → B → D → A

def postorder(root):
    result = []

    def visit(node):
        if node is None:
            return

        visit(node.left)
        visit(node.right)
        result.append(node.value)

    visit(root)
    return result


print(postorder(root))  # ['C', 'B', 'D', 'A']

后序遍历常用于：

删除整棵树；
计算目录大小；
计算表达式的值；
生成后缀表达式。

6. 层序遍历

深度优先遍历会沿着一条路径尽可能向下。层序遍历则按层访问：

第 0 层：A
第 1 层：B D
第 2 层：C

层序遍历通常使用队列。Python 中可以使用 collections.deque：

from collections import deque


def level_order(root):
    if root is None:
        return []

    result = []
    queue = deque([root])

    while queue:
        node = queue.popleft()
        result.append(node.value)

        if node.left is not None:
            queue.append(node.left)
        if node.right is not None:
            queue.append(node.right)

    return result


print(level_order(root))  # ['A', 'B', 'D', 'C']

遍历整棵树时，每个节点只入队和出队有限次数，因此时间复杂度是 O(n)。

队列的空间复杂度取决于某一层最多有多少个节点；深度优先递归的额外空间通常取决于树高 h。

7. 表达式树

表达式树用叶节点表示操作数，用内部节点表示运算符。

表达式：

(a + b) × (c - d)

可以表示为：

          ×
        /   \
       +     -
      / \   / \
     a   b c   d

用 Python 构造这棵树：

expression = TreeNode(
    "*",
    left=TreeNode("+", TreeNode("a"), TreeNode("b")),
    right=TreeNode("-", TreeNode("c"), TreeNode("d")),
)

不同遍历对应不同的表达式写法：

遍历	结果	表达式形式
先序	* + a b - c d	前缀表达式
中序	a + b * c - d	中缀表达式，需要括号表达优先级
后序	a b + c d - *	后缀表达式

如果希望输出带括号的中缀表达式，可以递归构造字符串：

def infix_expression(node):
    if node.left is None and node.right is None:
        return str(node.value)

    left = infix_expression(node.left)
    right = infix_expression(node.right)
    return f"({left} {node.value} {right})"


print(infix_expression(expression))
# ((a + b) * (c - d))

后序遍历很适合求值，因为一个运算符的两个操作数会先被处理。

8. 普通树的 Python 表示方法

普通树中的一个节点可能有任意多个子节点，不能简单地只放 left 和 right 两个属性。

8.1 使用子节点列表

Python 可以直接为每个节点保存一个 children 列表：

class GeneralNode:
    def __init__(self, value):
        self.value = value
        self.children = []

    def add_child(self, child):
        self.children.append(child)


root = GeneralNode("A")
root.add_child(GeneralNode("B"))
root.add_child(GeneralNode("C"))
root.add_child(GeneralNode("D"))

这种写法直观。children 本身是一个动态数组，按下标访问子节点很方便。

可以用递归遍历普通树：

def general_preorder(node):
    if node is None:
        return []

    result = [node.value]
    for child in node.children:
        result.extend(general_preorder(child))
    return result

8.2 左孩子—右兄弟表示法

还可以把普通树转换为二叉结构：

first_child 指向第一个子节点；
next_sibling 指向下一个兄弟节点。

class ForestNode:
    def __init__(self, value):
        self.value = value
        self.first_child = None
        self.next_sibling = None

例如，A 有 B、C、D 三个子节点时，可以表示成：

普通树：                 左孩子—右兄弟：
    A                         A
  / | \                       ↓
 B  C  D                     B → C → D

这种表示法只需要两个链接属性，可以统一表示任意分支数的树；代价是访问“某个节点的第 k 个孩子”时，需要沿着兄弟链接逐个查找。

9. 二叉搜索树

二叉搜索树是在二叉树上增加了顺序规则：

对任意节点 x：

左子树中的元素小于 x；
右子树中的元素大于 x。

搜索过程：

def bst_search(root, key):
    current = root

    while current is not None:
        if key == current.value:
            return current

        if key < current.value:
            current = current.left
        else:
            current = current.right

    return None

插入过程可以递归实现：

def bst_insert(root, value):
    if root is None:
        return TreeNode(value)

    if value < root.value:
        root.left = bst_insert(root.left, value)
    elif value > root.value:
        root.right = bst_insert(root.right, value)
    # 相同值在这里忽略

    return root


root = None
for value in [8, 3, 12, 1, 5, 10, 15]:
    root = bst_insert(root, value)

print(inorder(root))  # [1, 3, 5, 8, 10, 12, 15]
print(bst_search(root, 10).value)  # 10

搜索、插入和删除的复杂度与树高 h 有关：

O(h)

如果树比较平衡，h 接近 log n，操作接近 O(log n)；如果元素按有序顺序插入，树可能退化成链表，h = n，操作退化为 O(n)。

这也是平衡树重要的原因：它通过调整结构，避免树退化。

10. 树遍历的复杂度

无论采用先序、中序、后序还是层序遍历，遍历整棵包含 n 个节点的树时，都需要访问每个节点：

时间复杂度：O(n)

递归遍历的额外空间取决于树高：

空间复杂度：O(h)

平衡树的递归深度约为 O(log n)；退化成链表的树可能需要 O(n) 的递归栈空间。

Python 默认的递归深度有限。对特别深的树，递归实现可能触发 RecursionError，此时可以改用显式栈或队列。

11. 在 Python 中删除整棵树

在 C 语言中，释放树节点时通常使用后序遍历：先处理左右子树，再释放当前节点。

Python 通常不需要逐个释放节点。如果没有其他引用，直接让根节点失去引用即可：

root = None

如果希望明确演示“先断开子树，再处理当前节点”的后序过程，可以写成：

def detach_tree(root):
    if root is None:
        return

    left = root.left
    right = root.right

    detach_tree(left)
    detach_tree(right)

    root.left = None
    root.right = None


demo_tree = TreeNode("A", TreeNode("B"), TreeNode("C"))
detach_tree(demo_tree)
demo_tree = None

这个函数不是 Python 中释放内存的必需步骤，而是帮助理解后序处理顺序。真正的回收由 Python 的内存管理机制负责。

12. 树适合什么时候？

树适合表示：

文件系统和目录层级；
组织结构和家谱；
HTML、XML 等嵌套文档；
编译器的语法树；
数学表达式；
搜索索引；
决策过程和游戏状态。

如果数据本质上只有前后顺序，数组或链表通常更直接；如果数据具有层级关系，树通常更自然。

13. 常见错误

把二叉树和二叉搜索树混为一谈

二叉树只要求每个节点最多两个子节点；二叉搜索树还要求左小右大的顺序关系。

忘记空树和空子树

几乎所有递归树函数都需要先处理：

def visit(node):
    if node is None:
        return

混淆遍历顺序

“访问当前节点”放在递归调用之前是先序，放在中间是中序，放在之后是后序。

错估二叉搜索树的复杂度

二叉搜索树并不自动平衡。分析搜索、插入和删除时，应写成 O(h)，只有在能保证树高为 O(log n) 时，才能进一步写成 O(log n)。

递归深度过大

退化树可能导致递归调用层数达到 n。对规模很大的数据，需要考虑平衡树、显式栈或迭代实现。

层序遍历误用 list.pop(0)

list.pop(0) 会移动剩余元素，导致出队变成 O(n)。层序遍历应使用 deque.popleft()。

14. 小结

树用于表示层级关系；
根、父节点、子节点、叶节点、深度和高度是理解树的基础术语；
二叉树的每个节点最多有两个子节点；
先序、中序、后序和层序是常见遍历方式；
遍历整棵树通常是 O(n)，递归额外空间通常是 O(h)；
表达式树可以通过不同遍历生成前缀、中缀和后缀表达式；
普通树可以用子节点列表或左孩子—右兄弟表示法实现；
二叉搜索树的操作复杂度取决于树高 h；
平衡树能把树高控制在接近 O(log n)，避免退化为链表；
Python 负责对象的内存回收，但算法仍然要正确维护节点之间的引用。