跳至内容
概览
软件开发
Python开发
数据结构与算法
树与二叉树

树与二叉树

树是最重要的非线性数据结构之一：文件系统的目录结构、HTML/XML 的 DOM 树、数据库索引（B 树/B+树）、组织架构图，本质上都是树。本篇梳理树和二叉树的核心概念与性质，并用 Python 实现一棵二叉树及其四种遍历方式。

树的基本概念

树是 n（n ≥ 0）个元素的集合：n = 0 时称为空树；否则有且仅有一个没有前驱的特殊元素，称为根（Root），其余元素被划分为若干个互不相交的集合，每个集合本身又是一棵树，称为原树的子树（Subtree）——这是一个递归定义，也是后面用递归实现遍历算法的理论基础。

常用术语：

术语含义
结点（Vertex）树中的数据元素
结点的度（Degree）结点拥有的子树数目
叶子结点度为 0 的结点，也叫终端结点
分支结点度不为 0 的结点，也叫非终端结点
树的度树中各结点度的最大值
双亲 / 孩子子树的根是原结点的孩子，原结点是子树根的双亲
兄弟拥有相同双亲的结点
层次（Level）根结点为第 1 层，根的孩子为第 2 层，以此类推
树的深度 / 高度树中结点层次的最大值
森林m（m ≥ 0）棵互不相交的树的集合；对某个结点而言，它所有子树的集合就是一个森林

树的特点：唯一的根、子树互不相交、除根外每个结点有且仅有一个双亲、叶子结点没有孩子。

二叉树

二叉树是每个结点最多有两棵子树的有序树——即使某个结点只有一棵子树，也必须区分它是左子树还是右子树，不能像普通树那样随意排列。

基本形态与特殊二叉树

二叉树有五种基本形态：空二叉树、只有根结点、根只有左子树、根只有右子树、根同时有左右子树。此外还有几种命名的特殊形态：

  • 斜树：所有结点都只有左子树（左斜树）或都只有右子树（右斜树），退化成了链表。
  • 满二叉树：所有分支结点都同时存在左右子树，且所有叶子结点都在最下面一层。深度为 k 的满二叉树共有 2^k - 1 个结点。
  • 完全二叉树：深度为 k 时，第 1 到 k-1 层的结点数都达到最大值，第 k 层的结点全部集中在最左边。满二叉树一定是完全二叉树，反之不一定成立。

二叉树的性质

  • 性质 1：二叉树第 i 层最多有 2^(i-1) 个结点（i ≥ 1）。
  • 性质 2：深度为 k 的二叉树最多有 2^k - 1 个结点（k ≥ 1）。
  • 性质 3：对任意二叉树，若叶子结点数为 n0、度为 2 的结点数为 n2，则 n0 = n2 + 1。
  • 性质 4：有 n 个结点的完全二叉树，深度为 ⌊log₂ n⌋ + 1（对应 Python 里的 math.floor(math.log2(n)) + 1）。
  • 性质 5：完全二叉树按层序从 1 开始编号后，结点 i 的双亲是 i // 2，左孩子是 2i，右孩子是 2i + 1——这正是用数组（而非链表）实现堆等完全二叉树结构的理论基础。

二叉树的遍历

遍历是按某种规则对树中所有结点访问且只访问一次，把树的层次结构转换成线性序列。设根结点为 D、左子树为 L、右子树为 R：

  • 层序遍历（广度优先）：从第一层开始，逐层自左向右访问。
  • 前序遍历 DLR（先根遍历）：根 → 左子树 → 右子树，每棵子树内部同样先根后左右，递归进行。
  • 中序遍历 LDR（中根遍历）：左子树 → 根 → 右子树。
  • 后序遍历 LRD（后根遍历）：左子树 → 右子树 → 根。

前序、中序、后序都是深度优先遍历，天然适合用递归实现；层序遍历是广度优先遍历，通常借助队列迭代实现。

用 Python 实现二叉树

以下面这棵二叉树为例：

        A
       / \
      B   C
     / \  / \
    D  E F   G
from collections import deque
from dataclasses import dataclass


@dataclass
class TreeNode:
    value: str
    left: "TreeNode | None" = None
    right: "TreeNode | None" = None


# 搭建示例二叉树
root = TreeNode("A",
    left=TreeNode("B", left=TreeNode("D"), right=TreeNode("E")),
    right=TreeNode("C", left=TreeNode("F"), right=TreeNode("G")),
)

前序 / 中序 / 后序：递归实现 

def preorder(node: TreeNode | None) -> list[str]:
    """前序遍历 DLR：根 -> 左 -> 右。"""
    if node is None:
        return []
    return [node.value] + preorder(node.left) + preorder(node.right)


def inorder(node: TreeNode | None) -> list[str]:
    """中序遍历 LDR：左 -> 根 -> 右。"""
    if node is None:
        return []
    return inorder(node.left) + [node.value] + inorder(node.right)


def postorder(node: TreeNode | None) -> list[str]:
    """后序遍历 LRD：左 -> 右 -> 根。"""
    if node is None:
        return []
    return postorder(node.left) + postorder(node.right) + [node.value]


print("前序:", preorder(root))   # ['A', 'B', 'D', 'E', 'C', 'F', 'G']
print("中序:", inorder(root))    # ['D', 'B', 'E', 'A', 'F', 'C', 'G']
print("后序:", postorder(root))  # ['D', 'E', 'B', 'F', 'G', 'C', 'A']

层序遍历：借助队列迭代实现

层序遍历没有天然的递归结构，用 collections.deque 实现先进先出的队列更直观：

def level_order(root: TreeNode | None) -> list[str]:
    """层序遍历：借助队列做广度优先遍历。"""
    if root is None:
        return []
    result = []
    queue = deque([root])
    while queue:
        node = queue.popleft()
        result.append(node.value)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return result


print("层序:", level_order(root))   # ['A', 'B', 'C', 'D', 'E', 'F', 'G']
前序、中序、后序遍历的递归写法本质上就是递归函数一节里讲的"边界条件 + 缩小问题规模"：边界条件是 node is None（空树直接返回空列表），每次递归调用都作用于更小的子树，最终收敛到叶子结点。
最后更新于
排序算法