树与二叉树

树是一种重要的非线性数据结构，目录结构、组织架构、表达式求值、数据压缩等都能用树来建模。二叉树是树的特殊形式，也是算法考查的绝对重点：遍历、线索化、哈夫曼编码都是高频考点。本章从树的基本概念出发，逐步深入二叉树的特征、存储、遍历，最后介绍树与森林的转换及典型应用。

本章要解决的问题

如何把”一对多”的层次关系高效地存储与遍历？二叉树作为”每个结点至多两个孩子”的有序树，如何用顺序/链式存储、如何用前中后序与层序四种方式遍历、如何由遍历序列还原二叉树，都是核心问题。此外，线索二叉树如何利用空指针提速、树与森林如何互相转换、哈夫曼树如何构造最优编码，也需要一一理清。

学习目标

• 理解树的基本概念、术语与性质
• 掌握二叉树的定义、性质与特殊二叉树
• 掌握二叉树的顺序与链式存储结构
• 掌握前序、中序、后序、层序遍历及由遍历序列构造二叉树
• 理解线索二叉树与树、森林的存储转换
• 掌握二叉搜索树、平衡二叉树、哈夫曼树的应用

章节导航

建议阅读顺序

基础路线：基本概念 → 存储结构 → 遍历，先掌握二叉树的定义、存储与四种遍历。

进阶路线：线索二叉树与树森林 → 应用 → 总结，理解树结构的高级特性与实际价值。