第 28 课 - 二叉树基础

所属模块： 树结构
难度： Beginner
标签： binary-tree, node, traversal
上一课： 三分搜索
下一课： 树的遍历

1. 学习目标

完成本课学习后，你将能够：

理解二叉树的基本定义、术语和特性。
解释节点、根节点、叶子节点、子树、深度等核心概念。
使用代码定义并构建一个简单的二叉树结构。
识别二叉树与其他数据结构（如链表）的联系与区别。

2. 核心概念

2.1 什么是二叉树？

想象一下你的家谱。你有一个曾祖父（树的“根”），他可能有父亲和叔伯（他的“孩子”）。你的父亲又有你和你的兄弟姐妹（他的“孩子”）。这种分层级、有分支的关系，就是“树”结构。

二叉树是树结构中最简单、最重要的一种。它的核心规则是：每个节点最多只能有两个分支（称为“左孩子”和“右孩子”）。

节点 (Node): 树中的每个元素。每个节点存储一个数据元素，并可能有指向其他节点的指针（引用）。
根节点 (Root): 树最顶端的节点，没有父节点。
叶子节点 (Leaf): 没有任何子节点的节点，是树的“末端”。
子树 (Subtree): 一个节点和它所有的后代节点构成的一棵树。左孩子及其所有后代构成“左子树”，右孩子及其所有后代构成“右子树”。
深度/高度 (Depth/Height): 从根节点到某个节点所经过的边的数量。树的高度是根节点到最远叶子节点的边数。

2.2 二叉树的节点

一个二叉树的节点至少包含三个部分：

数据域 (Data): 存储的数据。
左指针 (Left): 指向其左子节点的引用。
右指针 (Right): 指向其右子节点的引用。

可以用 Python 的类来定义一个节点：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val      # 数据域
        self.left = left    # 左指针
        self.right = right  # 右指针

3. 代码示例

下面的代码展示了如何创建节点，并将它们连接起来，构成一棵简单的二叉树。

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

# 1. 创建各个节点
root = TreeNode(1)          # 创建根节点，值为1
node2 = TreeNode(2)         # 创建节点2
node3 = TreeNode(3)         # 创建节点3
node4 = TreeNode(4)         # 创建节点4
node5 = TreeNode(5)         # 创建节点5

# 2. 连接节点，构建树的结构
root.left = node2           # 根的左孩子是节点2
root.right = node3          # 根的右孩子是节点3
node2.left = node4          # 节点2的左孩子是节点4
node2.right = node5         # 节点2的右孩子是节点5

# 3. 一个辅助函数，用于打印树的结构（非二叉树遍历，仅为演示）
def print_tree_structure(node, level=0, prefix="Root: "):
    if node is not None:
        print(" " * (level * 4) + prefix + str(node.val))
        if node.left is not None or node.right is not None:
            print_tree_structure(node.left, level + 1, "L--- ")
            print_tree_structure(node.right, level + 1, "R--- ")

# 打印我们刚刚构建的树
print("我们构建的二叉树结构:")
print_tree_structure(root)
print()

# 4. 计算树的深度（递归方法）
def max_depth(node):
    if node is None:
        return 0  # 空树的深度为0
    else:
        left_depth = max_depth(node.left)
        right_depth = max_depth(node.right)
        return max(left_depth, right_depth) + 1

depth = max_depth(root)
print(f"这棵二叉树的深度是: {depth}")

预期输出:

我们构建的二叉树结构:
Root: 1
    L--- 2
        L--- 4
        R--- 5
    R--- 3

这棵二叉树的深度是: 3

4. 实践练习

练习 1：手动构建树（简单）

给定数据值 [A, B, C, D, E]，请在纸上画出满足以下条件的二叉树，并写出代码构建它：

A 是根节点。
B 是 A 的左孩子。
C 是 A 的右孩子。
D 是 B 的左孩子。
E 是 C 的右孩子。

预期输出（打印结构应类似）：

A
L--- B
    L--- D
R--- C
    R--- E

练习 2：统计节点数（中等）

编写一个递归函数 count_nodes(root)，计算并返回一棵二叉树中的总节点数。提示：树的总节点数 = 1 (根节点) + 左子树节点数 + 右子树节点数。当遇到 None 时返回 0。

预期结果：对上面示例代码中构建的树调用 count_nodes(root)，应返回 5。

练习 3：查找最大值（挑战）

编写一个递归函数 find_max(root)，找到并返回二叉树中所有节点值的最大值。假设所有节点的值都是整数。提示：最大值可能是当前节点的值，也可能是左子树或右子树中的最大值。同样需要处理 None 的基本情况。

5. 常见错误

忘记处理空树 (None)：这是递归函数中的首要错误。必须有一个基本情况来终止递归，通常 if node is None: 就是这个基本情况。

# 错误写法，会导致无限递归或错误
def bad_func(node):
    return 1 + bad_func(node.left) + bad_func(node.right)

# 正确写法
def good_func(node):
    if node is None: # 这是基本情况
        return 0
    return 1 + good_func(node.left) + good_func(node.right)

混淆“度”与“孩子”：二叉树节点的“度”指的是其子节点的个数（0, 1, 或 2）。但“左孩子”和“右孩子”的位置是固定的。一个节点只有左孩子（度为1）和另一个只有右孩子（度为1）是结构不同的二叉树。
认为树必须是“满”的：初学者常误以为二叉树必须像金字塔一样完美对称。实际上，只要每个节点最多有两个孩子，它就是二叉树。像示例中，节点3只有右孩子(None 的左孩子)也是完全合法的。

6. 小结

本节课我们学习了二叉树的基础：

定义：二叉树是一种每个节点最多有两个子节点的树形数据结构。
核心组件：节点由数据域、左指针和右指针构成。
关键术语：根节点（起点）、叶子节点（终点）、子树（分支）、深度/高度（层次）。
代码实现：用类 (class) 来定义节点，并通过指针赋值来构建节点间的父子关系。
基本操作：通过递归，我们可以轻松地对树进行各种计算，如求深度和统计节点数。

理解二叉树是学习更复杂树结构（如二叉搜索树、堆）和图算法的基础。在下一课《树的遍历》中，我们将学习如何系统地访问树中的每一个节点，这是解决许多树相关问题的第一步。

练习编辑器

rust