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树]]