总结
树与二叉树是数据结构里概念密度最高的一章:性质、遍历、线索化、哈夫曼树,每一项都可能单独出题。术语对照表把满二叉树、完全二叉树、四种遍历、线索二叉树的说法对齐到英文,核心要点给出必须记牢的 与每层结点数上界,其余概念建议配合本章的遍历演示一起复习。
| 中文术语 | 英文术语 | 说明 |
|---|---|---|
| 树 | Tree | n 个结点的有限集 |
| 二叉树 | Binary Tree | 每个结点至多两个孩子的有序树 |
| 叶子结点 | Leaf | 度为 0 的结点 |
| 深度 | Depth | 结点的最大层次数 |
| 满二叉树 | Full Binary Tree | 每层结点数达最大值 |
| 完全二叉树 | Complete Binary Tree | 最后一层结点集中左侧 |
| 前序遍历 | Preorder | 根左右 |
| 中序遍历 | Inorder | 左根右 |
| 后序遍历 | Postorder | 左右根 |
| 层序遍历 | Level-order | 按层次遍历 |
| 线索二叉树 | Threaded Binary Tree | 用空指针存前驱后继 |
| 哈夫曼树 | Huffman Tree | 带权路径长度最小的二叉树 |
- 二叉树性质:;第 i 层至多 个结点
- 前序+中序 或 后序+中序 可唯一确定二叉树;前序+后序不能
- 三种遍历递归代码只改变 visit 的位置,时间复杂度均为
- 层序遍历借助队列实现
- 哈夫曼编码是最优前缀编码,用于数据压缩
