五、树与二叉树

本章导览

共 4 个小节：树和森林、二叉树、哈夫曼树、并查集

五、树与二叉树 · 章节总览

本章重点

树是一对多层次结构；一般树用双亲 / 孩子 / 孩子兄弟表示
二叉树为核心：满 / 完全 / BST / AVL，遍历是基础
应用：哈夫曼树（编码压缩）、并查集

树和森林

关键点

树 = n 个结点的有限集；结点数 = 总度数 + 1
区分层次（深度，上往下）与高度（下往上）
存储：双亲 / 孩子 / 孩子兄弟（可转二叉树）

树的基本性质

关键点

常见考点 1：结点数 = 总度数 + 1 常见考点 2：度为 m 的树、m 叉树的区别常见考点 3：度为 m 的树第 i 层至多有 $m^{i-1}$ 个结点（i 1），m 叉树第 i 层至多有 $m^{i-1}$ 个结点（i 1）。常见考点 4：高度为 h 的 m 叉树至多有 $\frac{m^h-1}{m-1}$ 个结点。