---
title: 树与堆
tags:
  - module
  - data-structure-and-algorithm
  - tree
  - heap
  - joplin
type: module
source_type: reconstructed
created: 2026-04-22
updated: 2026-04-22
---

# 树与堆

> [!abstract]
> 这一模块处理层次结构。重点不是把各种树名词割裂开背，而是理解它们都在解决“如何维护有层次的关系并支持高效操作”。

## 模块结论

- [[二叉树]] 是最基础的树形组织方式，遍历、节点数、高度等问题都从这里展开。
- [[二叉排序树]] 在二叉树上增加有序性，用来加速查找、插入和删除。
- [[AVL树]] 进一步在二叉排序树上增加平衡约束，避免退化。
- [[堆]] 是特殊的完全二叉树，更适合快速找最值，而不是做通用查找。

## 一、二叉树基础

- 每个结点最多两个孩子。
- 常见操作包括前序、中序、后序遍历，以及结点数、叶子数和高度统计。
- 顺序存储适合完全二叉树，链式存储适合一般二叉树。

### 遍历为什么重要

- 前序常用于描述“根先处理”。
- 中序在二叉排序树里会直接得到有序序列。
- 后序适合“先处理子问题，再处理根”的场景。

## 二、二叉排序树

- 左子树所有关键字小于根，右子树所有关键字大于根。
- 查找、插入、删除都围绕这条性质展开。
- 删除最值得复习，因为要区分 0 个孩子、1 个孩子、2 个孩子三类情况。

### 删除核心逻辑

- 叶子结点：直接删。
- 单孩子结点：用孩子顶替。
- 双孩子结点：常用后继或前驱替换后再删。

## 三、AVL 树

- 它是自平衡的二叉排序树。
- 任一结点左右子树高度差绝对值不超过 1。
- 一旦插入导致失衡，就需要旋转恢复平衡。

### 四种典型失衡

- LL
- RR
- LR
- RL

### 复习重点

- 别只背旋转名字，要能判断失衡发生在哪一侧、由哪种插入路径导致。

## 四、堆

- 堆是完全二叉树。
- 最大堆满足根不小于孩子，最小堆满足根不大于孩子。
- 典型操作是插入、删除堆顶、建堆。

### 堆和二叉排序树的区别

- 堆只保证局部父子有序，不保证整棵树中序有序。
- 堆适合反复取最值。
- 二叉排序树适合更一般的动态查找。

## 五、易错点

- 二叉树的顺序存储数组下标关系要和从 0 还是从 1 开始分开看。
- 二叉排序树最坏情况下会退化成链表。
- AVL 树旋转后不仅结构变了，高度也要更新。
- 堆不是完全排序结构，不能直接当成“任意查找都快”的树。

## 六、复习提问

- 二叉树三种深度优先遍历的访问次序分别是什么？
- 二叉排序树删除结点为什么要分三类情况？
- AVL 树为什么比普通二叉排序树更稳定？
- 堆为什么适合优先队列，却不适合一般查找？

## 来源

- [[raw/Joplin/计算机专业基础/数据结构与算法/(C)840数据结构与算法/2.二叉树的实现和应用.md]]
- [[raw/Joplin/计算机专业基础/数据结构与算法/(C)840数据结构与算法/3.堆--以最大堆为例.md]]
- [[raw/Joplin/计算机专业基础/数据结构与算法/(C)840数据结构与算法/5.二叉排序树.md]]
- [[raw/Joplin/计算机专业基础/数据结构与算法/(C)840数据结构与算法/6.平衡二叉树(AVL树).md]]
- [[raw/Joplin/计算机专业基础/数据结构与算法/(C++)数据结构与算法/12.二叉排序树.md]]

## 相关页面

- [[数据结构与算法]]
- [[二叉树]]
- [[堆]]
- [[二叉排序树]]
- [[AVL树]]