线性表把元素排成一条线，树则用分支表达“一对多”的层次关系。课程目录、文件系统、组织结构和语法分析都可以抽象成树：每个对象只沿一条路径归属于上层对象，却可以继续管理多个下层对象。

本章按“由一般到特殊、由理论到应用”展开：先建立一般树的概念与存储，再聚焦有序的二叉树，掌握其性质、遍历、线索化与经典问题，并与树、森林完成双向转换。

本章学习目标

完成本章后，你应该能够：

• 准确解释树、二叉树的关键术语与结构不变量；
• 推导二叉树的数量与复杂度性质，并比较不同存储表示的取舍；
• 用手工与代码完成前序、中序、后序、层序遍历及其变体；
• 由遍历序列还原二叉树，理解线索化如何复用空链域；
• 完成树、森林与二叉树的互转，并求解树上的经典问题。

本章导览

以下小节从一般树过渡到二叉树，再落到经典问题：

• 4.1 树的基本概念与存储结构：一般树的定义、Tree ADT、三种存储表示与实现。
• 4.2 二叉树：二叉树的定义、特殊形态、性质与存储。
• 4.3 二叉树的遍历：四种遍历的递归与迭代、由序列构造二叉树。
• 4.4 线索二叉树：空链域复用、中序线索化与前驱/后继。
• 4.5 树、森林与二叉树：孩子兄弟表示法与遍历的等价对应。
• 4.6 二叉树的经典问题：统计、判断、变换、路径与树形 DP。
• 4.7 树结构代码题解析——从状态判定到换根模型：通过完全二叉树判定与网络最优选址两道经典例题，掌握从层序遍历状态机到无向树换根 DP 的解题思维跃迁。

代码训练路线

本章共 31 道代码题，每题 20 个测试点。按知识点完成以下训练，再进入综合应用：

知识点	题号	训练入口
一般树与孩子兄弟表示	04E01～04E02	叶子统计、树的高度
二叉树性质与基础计算	04E03～04E06	完全性检验、合并二叉树
遍历及重建	04E07～04E14	迭代中序、层平均值、叶子相似
中序线索树	04E15～04E16	中序线索化、后继与遍历
森林转换与一般树遍历	04E17～04E19	森林转二叉树、二叉树转森林、后根遍历
综合应用	04E20～04E31	最大宽度、坡度、树的同构