数据结构初阶：树的相关概念
在深入二叉树之前，我们需要先建立对'树'这一非线性数据结构的整体认知。树形结构与线性表不同，它通过层次关系组织数据，广泛应用于文件系统、组织架构等场景。
一、树的概念与结构
讲到树，我们很容易联想到生活中的植物树。但今天我们要讲的树，灵感正来源于此，只是方向相反。
生活中的树根在地下，分支朝上生长；而数据结构中的树是倒挂的，根节点朝上，叶子节点朝下。
树是由 n(n>=0) 个有限节点组成的具有层次关系的集合。其核心特征如下：
- 根节点：唯一的特殊节点，没有前驱节点。
- 子树：除了根节点外，其余节点被划分为 m(m>0) 个互不相交的集合 T1, T2, ..., Tm。每个集合本身又是一棵结构类似的子树。
- 递归性：每棵子树的根节点有且仅有一个前驱（父节点），但可以有多个后驱（子节点）。
- 无环性：子树之间不能有交集，否则将构成图而非树。
此外，对于一棵包含 N 个节点的树，其边的数量必然为 N-1。除根节点外，其他每个节点都有且仅有一个父节点。
二、树的相关术语
理解树的结构需要掌握以下关键术语（参考下图逻辑结构）：
- 父节点/双亲节点：若一个节点含有子节点，则该节点为其子节点的父节点。
- 子节点/孩子节点：一个结点含有的子树的根节点成为该节点的子结点。
- 结点的度：一个结点拥有的子树数量。例如，A 的度为 6。
- 树的度：一棵树中所有结点的度的最大值。
- 叶子结点/终端结点：度为 0 的结点。
- 分支结点/非终端结点：度不为 0 的结点。
- 兄弟结点：具有相同父结点的结点互相称为兄弟结点。
- 结点的层次：从根开始定义，根为第 1 层，其子结点为第 2 层，以此类推。
- 树的高度或者深度：树中结点的最大层次。
- 结点的祖先：从根到该结点所经分支上的所有结点。
- 路径：一条从树任意结点出发，沿父结点 - 子结点连接，达到任意结点的序列。
- 子孙：以某个结点为根的子树中任一结点都称为该节点的子孙。
- 森林：由 m(m>0) 棵互不相交的树的集合称为森林。
三、树的表示方法
树结构比线性表复杂，存储时既要保存值域，也要保存结点间的关系。常见的表示方法包括双亲表示法、孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。
