一、'树'是什么
树（Tree）是一种非线性、分层级的数据结构，它模拟了自然界中树的分支结构。核心特点是：一个节点可以有多个后继（子节点），但只能有一个前驱（父节点）。树结构是递归定义的。
二、'树'的理解
我们可以把树想象成宗族关系。
- 根节点：A 是整棵树的'根'，相当于家族的老祖宗。
- 父节点：对根节点以外的任意节点，都有父节点。
- 子节点：节点不一定都有子节点。
- 没有子节点的，称为叶节点或终端节点。
- 有子节点的，称之为非叶子节点或分支节点。
- 兄弟节点：同一个父节点的孩子我们称之为兄弟节点。
- 路径传递性：在树形结构中，'大小'或'远近'这种关系仅在同一路径上具有明确的传递性。
三、树的基础概念
1. 度
- 节点的度：该节点拥有的子节点数量。
- 树的度：树中所有节点的最大度值。
2. 层次与深度
- 层次：根节点为第 1 层，其子节点为第 2 层，以此类推。
- 节点的深度：从根节点到该节点的路径长度（边数）。
3. 高度
- 节点的高度：从该节点到最深叶子节点的最长路径长度。
- 树的高度：根节点的高度。
4. 路径
- 路径：从一个节点到另一个节点的节点序列。
- 路径长度：路径上的边数。
5. 子树
- 子树：树中任意节点及其所有后代构成的子结构。
四、树节点的表示
理解树简单，但想实现树就有难度。
- 在定义树节点结构体的时候，需要有数据域和指针域。
- 让人困惑的点在于节点的指针域设计：由于每个节点可能拥有数量不确定的子节点，无法预先分配固定大小的指针空间。
- 常用方法是左孩子右兄弟表示法：
- 左指针：指向该节点的第一个子节点（即'长子'）。
- 右指针：指向该节点在兄弟节点中的下一个兄弟。
- 通过这种方式，节点的所有子节点被组织成一个以第一个子节点为起点的单链表。
五、树与线性结构的核心区别
| 对比维度 | 树结构 | 线性结构 |
|---|---|---|
| 数据关系 | 一对多层次关系 | 一对一顺序关系 |
| 访问方式 | 从根开始导航 | 可直接索引访问 |
| 典型时间复杂度 | 查找：O(log n) | 查找：O(n) |
