二叉树

一、二叉树的基本概念

二叉树（Binary Tree）是一种树形数据结构，它的每个节点最多只能有两个子节点，分别称为左子节点和右子节点。可以把它类比成 “每个家长最多只能有两个孩子” 的家族树。

关键术语：

  • 根节点：树的最顶层节点，没有父节点。
  • 叶子节点：没有任何子节点的节点。
  • 节点的度：节点拥有的子节点数量（二叉树中最多为 2）。
  • 树的深度 / 高度：从根节点到最远叶子节点的路径上的节点数。
  • 满二叉树：所有非叶子节点都有两个子节点，且所有叶子节点在同一层。
  • 完全二叉树：除最后一层外，每一层节点数都达到最大值，最后一层的叶子节点靠左排列。

二、二叉树的经典计算方法与公式（全是递归，学会这个公式就可以）

1. 二叉树的基本定义（Python 实现）

先定义二叉树节点的类，这是所有计算的基础：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class TreeNode:
    """二叉树节点类"""
    def __init__(self, val=0, left=None, right=None):
        self.val = val    # 节点值
        self.left = left  # 左子节点
        self.right = right# 右子节点

# 示例：构建一个简单的二叉树
#       1
#      / \
#     2   3
#    / \
#   4   5
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

2. 经典计算方法与公式

（0）计算二叉树的单侧高度（深度）

  • 公式 / 逻辑：二叉树单侧的高度 = 无子节点则停止更新。
  • Python 代码：
1
2
3
4
5
6
7
8
def get_right_height(node):
    height = 0
    while node:
        height += 1
        node = node.right
    return height

left_h = get_left_height(root)
（1）计算二叉树的高度（深度）
  • 公式 / 逻辑：二叉树的高度 = max (左子树高度，右子树高度) + 1（递归思想，叶子节点高度为 1）。
  • Python 代码：
1
2
3
4
5
6
7
8
9
10
11
def tree_height(root: TreeNode) -> int:
    """计算二叉树的高度（递归法）"""
    if root is None:  # 空树高度为0
        return 0
    # 递归计算左右子树高度，取最大值+1
    left_height = tree_height(root.left)
    right_height = tree_height(root.right)
    return max(left_height, right_height) + 1

# 测试：上述示例树的高度为3
print("树的高度：", tree_height(root))  # 输出：3
（2）计算二叉树的节点总数
  • 公式 / 逻辑：总节点数 = 左子树节点数 + 右子树节点数 + 1（当前节点）。
1
2
3
4
5
6
7
8
9
def count_nodes(root: TreeNode) -> int:
    """计算二叉树的总节点数"""
    if root is None:
        return 0
    # 递归累加左右子树节点数 + 当前节点
    return count_nodes(root.left) + count_nodes(root.right) + 1

# 测试：上述示例树的节点数为5
print("总节点数：", count_nodes(root))  # 输出：5
（3）计算二叉树的叶子节点数

  • 公式 / 逻辑：

    叶子节点 = 若当前节点是叶子（无左右子节点）则为 1；否则 = 左子树叶子数 + 右子树叶子数。

  • Python 代码：

1
2
3
4
5
6
7
8
9
10
11
12
def count_leaf_nodes(root: TreeNode) -> int:
    """计算二叉树的叶子节点数"""
    if root is None:
        return 0
    # 叶子节点判定：无左、右子节点
    if root.left is None and root.right is None:
        return 1
    # 递归累加左右子树的叶子节点数
    return count_leaf_nodes(root.left) + count_leaf_nodes(root.right)

# 测试：上述示例树的叶子节点是4、5、3，共3个
print("叶子节点数：", count_leaf_nodes(root))  # 输出：3
（4）完全二叉树的节点数（优化公式）

对于完全二叉树，无需递归遍历所有节点，可利用特性优化计算：

  • 公式：

    设完全二叉树的高度为 h：

    • 若右子树的高度 = h-1 → 左子树是满二叉树，节点数 = 2^(h-1) + 右子树节点数；

    • 若右子树的高度 = h-2 → 右子树是满二叉树，节点数 = 2^(h-2) + 左子树节点数。

      （满二叉树高度为 k 时，节点数 = 2^k -1）

  • Python 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
def count_complete_tree_nodes(root: TreeNode) -> int:
    """优化版：计算完全二叉树的节点数（无需遍历所有节点）"""
    if root is None:
        return 0
    
    # 计算左子树的高度（沿左边界到底）
    def get_left_height(node):
        height = 0
        while node:
            height += 1
            node = node.left
        return height
    
    # 计算右子树的高度（沿右边界到底）
    def get_right_height(node):
        height = 0
        while node:
            height += 1
            node = node.right
        return height
    
    left_h = get_left_height(root)
    right_h = get_right_height(root)
    
    # 若左右高度相等，是满二叉树，直接用公式 2^h -1
    if left_h == right_h:
        return (1 << left_h) - 1  # 等价于 2^left_h -1
    # 否则递归计算左右子树
    return 1 + count_complete_tree_nodes(root.left) + count_complete_tree_nodes(root.right)

# 测试：构建一个完全二叉树（示例）
#       1
#      / \
#     2   3
#    / \  /
#   4  5 6
complete_root = TreeNode(1)
complete_root.left = TreeNode(2)
complete_root.right = TreeNode(3)
complete_root.left.left = TreeNode(4)
complete_root.left.right = TreeNode(5)
complete_root.right.left = TreeNode(6)
print("完全二叉树节点数：", count_complete_tree_nodes(complete_root))  # 输出：6

二叉树有三种常见的遍历方式：

1. 先序遍历

原则：根左右（先访问根，再访问左子树，最后访问右子树）

  • 通俗解释：遇到一个节点，立刻记下它的值，然后再去处理左边的分支，左边处理完了，再去处理右边。
  • 访问顺序：
    1. 访问根节点。
    2. 先序遍历左子树。
    3. 先序遍历右子树。
  • 举例：
    假如有一个树：
    1
    2
    3
    4
    5
        A
       / \
      B   C
     / \   \
    D   E   F
    先序遍历的结果是：A -> B -> D -> E -> C -> F
    （过程：A -> 进左树（B -> 进左树（D） -> 进右树（E）） -> 回到A的右树（C -> 进右树（F）））

2. 中序遍历

原则：左根右（先访问左子树，再访问根，最后访问右子树）

  • 通俗解释：先把左边的所有子节点处理完了，才回头记下当前节点的值，然后再去处理右边。
  • 访问顺序：
    1. 中序遍历左子树。
    2. 访问根节点。
    3. 中序遍历右子树。
  • 举例：
    同样的树：
    1
    2
    3
    4
    5
        A
       / \
      B   C
     / \   \
    D   E   F
    中序遍历的结果是：D -> B -> E -> A -> C -> F
    （过程：进A的左树（进B的左树（D） -> B -> 进B的右树（E）） -> A -> 进A的右树（C -> 进C的右树（F）））
    （注意：因为C没有左子树，所以直接访问C，然后进它的右树F）

3. 后序遍历

原则：左右根（先访问左子树，再访问右子树，最后访问根）

  • 通俗解释：确保这个节点的左孩子和右孩子都被记录完了，最后才记录这个节点本身。
  • 访问顺序：
    1. 后序遍历左子树。
    2. 后序遍历右子树。
    3. 访问根节点。
  • 举例：
    同样的树：
    1
    2
    3
    4
    5
        A
       / \
      B   C
     / \   \
    D   E   F
    后序遍历的结果是：D -> E -> B -> F -> C -> A
    （过程：处理A的左树（处理B的左树（D） -> 处理B的右树（E） -> B） -> 处理A的右树（处理C的右树（F） -> C） -> A）

如何快速记忆？

为了帮助你记忆，我们可以把根看作核心，把左看作“左边全部”，把右看作“右边全部”。

  1. 先序：根最先出现（根左右）。
  2. 中序：根在中间出现（左根右）。
  3. 后序：根最后出现（左右根）。

它们有什么用？

这三种遍历方式在不同的应用场景下有不同的用途：

  • 先序遍历：用于复制一棵树（因为你先拷贝了根，才知道把左右子树挂在哪里），或者用于输出表达式的前缀表示。
  • 中序遍历：在二叉搜索树（BST）中，中序遍历的结果是一个递增的有序序列。这是它最重要的特性。
  • 后序遍历：用于删除树（你得先把孩子删了，才能删父亲，否则孩子找不到了），或者用于计算树的高度、自底向上的计算（比如计算文件夹占用的磁盘空间）。