数据结构初阶：树的相关概念
在深入二叉树之前，我们需要先夯实树的基础。线性表处理的是顺序关系，而树结构则引入了层次和分支，这是非线性数据结构的典型代表。
一、树的概念与结构
提到树，大家容易联想到植物。计算机中的树确实借鉴了这种形态，但方向是相反的——根在上，叶在下。
定义：树是由 n(n>=0) 个有限节点组成的具有层次关系的集合。当 n=0 时称为空树。
树的核心特性包括：
- 根节点：没有前驱节点的节点，整棵树的入口。
- 子树：除根节点外，其余节点被分成 m(m>0) 个互不相交的集合，每个集合本身又是一棵树。
- 递归性：每棵子树的根节点有且只有一个前驱（父节点），可以有多个后驱（子节点）。
注意：子树之间不能有交集，否则就变成了图结构。
此外还有两个重要性质：
- 除了根节点，其他节点有且仅有一个父节点。
- 一棵 N 节点的树必然有 N-1 条边。
二、树的相关术语
理解术语是掌握树结构的关键。我们结合下图来梳理这些概念：
| 术语 | 说明 |
|---|---|
| 父节点/双亲节点 | 若一个节点含有子节点，则该节点为父节点（如 A 是 B 的父节点）。 |
| 子节点/孩子节点 | 一个结点含有的子树的根节点称为该节点的子结点（如 B 是 A 的子节点）。 |
| 结点的度 | 一个结点拥有的子树数量（如 A 的度为 6）。 |
| 树的度 | 树中所有结点的度的最大值。 |
| 叶子结点 | 度为 0 的结点，即终端结点。 |
| 分支结点 | 度不为 0 的结点，即非终端结点。 |
| 兄弟结点 | 具有相同父结点的结点互相称为兄弟。 |
| 结点的层次 | 从根开始定义，根为第 1 层，其子结点为第 2 层，以此类推。 |
| 树的高度/深度 | 树中结点的最大层次。 |
| 路径 | 从任意结点出发沿父子连接到达另一结点的序列。 |
| 祖先/子孙 | 从根到某结点路径上的所有结点为其祖先；以某结点为根的子树中任一点为其子孙。 |
| 森林 | 由 m(m>0) 棵互不相交的树的集合。 |
三、树的表示方法
树的结构比线性表复杂，存储时需要同时保存值域和结点间的关系。常见的表示法有双亲表示法、孩子表示法、孩子双亲表示法等。在实际应用中，孩子兄弟表示法最为常用，它巧妙地将多叉树转化为二叉树结构，便于理解和实现。
结构体定义
struct TreeNode {
struct TreeNode* child; // 指向第一个孩子结点
struct TreeNode* brother; // 指向下一个兄弟结点
int data; // 结点中的数据域
};
原理解析
这个结构体只有两个指针，却足以表达复杂的树形关系。child 指向最左边的孩子，brother 指向右边的兄弟。通过这两个指针的链接，原本的多叉树就被'拉直'成了二叉树的形式。
对应到具体的内存映射，这棵树的结构化表现如下：
四、树形结构的应用
树在生活中无处不在，最直观的例子就是操作系统的文件管理器。文件夹嵌套文件夹，文件挂在文件夹下，本质上就是一层一层向下的树形管理结构。
掌握了这些基础概念和术语，接下来我们就可以顺利进入二叉树的学习了。