数据结构基础：树的概念与结构详解
在学习二叉树之前，我们需要先理解什么是树。树是一种非线性的数据结构，与前面学过的线性表不同，它由 n(n>=0) 个有限节点组成一个具有层次关系的集合。
一、树的相关概念
提到树，我们很容易联想到生活中的植物。虽然形态相似，但数据结构中的树是倒挂的——根朝上，叶子朝下。
1. 树的概念与结构
树形结构具有以下核心特征：
- 根节点：有一个特殊的节点称为根节点，它没有前驱节点。
- 子树划分：除了根节点之外，剩下的其他节点被分成 M(M>0) 个互不相交的集合 T1, T2, ..., Tm。每个集合 Ti 本身又是一颗结构与树类似的子树。
- 递归定义：每棵子树的根节点有且只有一个前驱（父节点），可以有 0 个或多个后驱（子节点）。
注意：在树形结构中，子树不能有交集。如果相交了，那就变成了图，不再是树。
此外，除根节点外，其他节点有且仅有一个父节点；一颗 N 节点的树必然有 N-1 条边。
2. 树的相关术语
结合下图来理解这些术语：
- 父节点/双亲节点：若一个节点含有子节点，则该节点为子节点的父节点。例如 A 是 B 的父节点。
- 子节点/孩子节点：一个结点含有的子树的根节点称为该节点的子结点。例如 B 是 A 的子结点。
- 结点的度：一个结点有几个孩子，其度就是多少。如 A 的度是 6，F 的度是 2。
- 树的度：一棵树中最大结点的度称为树的度。上图树的度为 6。
- 叶子结点/终端结点：度为 0 的结点称为叶结点，如 B、C、H、I 等。
- 分支结点/非终端结点：度不为 0 的结点，如 D、E、F、G 等。
- 兄弟结点：具有相同父结点的结点互相称为兄弟结点。如 B、C 是兄弟结点。
- 结点的层次：从根开始定义，根为第 1 层，根的子结点是第 2 层，以此类推。
- 树的高度或者深度：树中结点的最大层次。上图树的高度为 4。
- 结点的祖先：从根到该结点所经分支上的所有结点。如 A 是所有节点的祖先。
- 路径：一条从树任意结点出发，沿父结点 - 子结点连接，达到任意结点的序列。例如 A 到 Q 的路径为 A-E-J-Q。
- 子孙：以某个结点为根的子树中任一结点都称为该节点的子孙。
- 森林：由 m(m>0) 棵互补相交的树的集合称为森林。
3. 树的表示方法
树结构相对线性表比较复杂，既要存储值域，也要保存结点和结点之间的关系。实际中树有很多种表示方式，如双亲表示法、孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。
在这些方法中，我们通常选择孩子兄弟表示法。这种方法将多叉树转换为二叉树的形式，便于理解和实现。
