总结

术语对照表

中文术语	英文术语	说明
树	Tree	n 个结点的有限集
二叉树	Binary Tree	每个结点至多两个孩子的有序树
叶子结点	Leaf	度为 0 的结点
深度	Depth	结点的最大层次数
满二叉树	Full Binary Tree	每层结点数达最大值
完全二叉树	Complete Binary Tree	最后一层结点集中左侧
前序遍历	Preorder	根左右
中序遍历	Inorder	左根右
后序遍历	Postorder	左右根
层序遍历	Level-order	按层次遍历
线索二叉树	Threaded Binary Tree	用空指针存前驱后继
哈夫曼树	Huffman Tree	带权路径长度最小的二叉树

核心要点

二叉树性质： $n_0 = n_2 + 1$ ；第 i 层至多 $2^{i-1}$ 个结点
前序+中序或后序+中序可唯一确定二叉树；前序+后序不能
三种遍历递归代码只改变 visit 的位置，时间复杂度均为 $O(n)$
层序遍历借助队列实现
哈夫曼编码是最优前缀编码，用于数据压缩

上一章节应用二叉搜索树、平衡二叉树、哈夫曼树与哈夫曼编码。

下一章节图掌握图的基本概念、存储结构、遍历方法及其基本应用。