跳到主要内容

树与二叉树

树(Tree)是一种层次化的非线性数据结构,由节点与边组成,常用于表达具有父子、包含关系的场景,如文件系统、DOM、组织架构。二叉树是每个节点最多有两个子树的树结构,是绝大多数高级树(AVL、红黑树、堆、B 树)的基础。

树的基本术语​

  • 度(Degree):一个节点拥有的子节点数;树的度是所有节点度的最大值。
  • 深度(Depth):从根节点到该节点的路径长度(根深度为 0)。
  • 高度(Height):从该节点到最深叶子节点的路径长度;叶子高度为 0,整棵树的高度即根节点的高度。
  • 根 / 父 / 子 / 兄弟 / 叶子:根是唯一无父节点的;叶子是无子节点的;同父节点互为兄弟。

二叉树的性质​

设非空二叉树中度为 0、1、2 的节点数分别为 n0、n1、n2,叶子数为 n0:

  • n0 = n2 + 1(叶子数比度为 2 的节点数多 1)。
  • 第 i 层最多有 2^i 个节点(i 从 0 开始)。
  • 高度为 h 的二叉树最多有 2^(h+1) - 1 个节点(满二叉树)。
  • 满二叉树中,父节点下标为 i 时,左子节点为 2i+1、右子节点为 2i+2(数组存储基础)。

四种遍历方式​

以如下二叉树为例,根节点 1,左子 2,右子 3,2 又有左子 4、右子 5:

      1
     / \
    2   3
   / \
  4   5
  • 前序(Preorder):根 → 左 → 右 → 1 2 4 5 3
  • 中序(Inorder):左 → 根 → 右 → 4 2 5 1 3
  • 后序(Postorder):左 → 右 → 根 → 4 5 2 3 1
  • 层序(Level Order):按层从左到右 → 1 2 3 4 5

前/中/后序既可递归实现(代码简洁),也可用显式栈迭代实现(避免栈溢出);层序遍历则借助队列实现 BFS。

递归与迭代实现​

以中序遍历为例:

# 递归版
def inorder(root):
    if not root:
        return
    inorder(root.left)
    visit(root)
    inorder(root.right)

# 迭代版:用栈模拟调用
def inorder_iter(root):
    stack, node = [], root
    while stack or node:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        visit(node)
        node = node.right

迭代版通过手动维护"待访问节点栈",将递归调用展开为循环,栈深度最坏 O(n),空间与递归版相当,但避免了 Python 默认递归深度限制。

二叉搜索树(BST)​

二叉搜索树是满足以下性质的二叉树:对任意节点 x,其左子树所有节点值 < x.val,右子树所有节点值 > x.val,且左右子树也是 BST。

  • 查找/插入/删除:平均 O(log n),最坏退化为链状时 O(n)(此时需平衡树如 AVL、红黑树修正)。
  • 中序遍历 BST 得到有序序列,这是 BST 最重要的性质。
  • 删除节点分三种情况:叶子直接删;仅一个子节点用子节点替代;有两个子节点时,用右子树的最小节点(或左子树的最大节点)填补,再递归删除该后继。

BST 是理解更复杂自平衡树与数据库索引的基石。