数据结构 - 初阶：树的基本概念与结构
在掌握了线性表之后，我们进入非线性结构的学习。今天我们将深入探讨树（Tree）这一核心数据结构，它是后续学习二叉树、堆及图论的基础。
一、树的相关概念
提到树，大家容易联想到植物。计算机中的树确实借鉴了这种形态，但方向是倒置的：根在上，叶在下。
1. 树的概念与结构
树是一种非线性的数据结构，由 n(n>=0) 个有限节点组成一个具有层次关系的集合。之所以称为树，是因为它看起来像一颗倒挂的树，根节点朝上，叶子节点朝下。
- 根节点：没有前驱节点的节点。
- 子树：除了根节点外，其余节点被分成 m(m>0) 个互不相交的集合 T1, T2...Tm，每个集合本身又是一棵结构与树类似的子树。
- 递归定义：每棵子树的根节点有且只有一个前驱，可以有 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。
