树与二叉树

树是一种重要的非线性数据结构,目录结构、组织架构、表达式求值、数据压缩等都能用树来建模。二叉树是树的特殊形式,也是算法考查的绝对重点:遍历、线索化、哈夫曼编码都是高频考点。本章从树的基本概念出发,逐步深入二叉树的特征、存储、遍历,最后介绍树与森林的转换及典型应用。读完本节,你将能够理解树的基本概念、术语与性质、掌握二叉树的定义、性质与特殊二叉树、掌握二叉树的顺序与链式存储结构、掌握前序、中序、后序、层序遍历及由遍历序列构造二叉树、理解线索二叉树与树、森林的存储转换、掌握二叉搜索树、平衡二叉树、哈夫曼树的应用。

本章要解决的问题

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

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

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

章节

发现内容有问题?

告诉我们哪里需要改进。