1. 树

参考链接：

1.1 基本概念

? ? ? ?在计算机科学中，树（Tree）作为一种抽象的数据结构，用来模拟具有树状结构性质的数据集合，表示一对多的对应关系，考虑它的各种特性，来解决我们在编程中碰到的相关问题。它是由n（n≥0）个结点组成的一个具有层次关系的有限集合，之所以把它叫做”树”，是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。树的定义就是在讲解栈时提到的递归的方法，即在树的定义之中还会用到树的概念。

? ? ? ?与栈、队列、链表不同，树是一种非线性的数据结构。一棵树只能有一个根结点，拥有多个根结点的数据结构是树的集合，即森林。

? ? ? ?实际在现实生活中，树状结构是十分普遍的。例如在我们的计算机磁盘上存储的文件夹和文件，就能够构成一个文件树结构。其中，盘符下存储有文件和文件夹，文件夹下又有子文件和子文件夹，但是文件之下一定不会有其他子文件和子文件夹。如果将这些层次关系表示成一棵树，其结构如下：

通过上面这张图我们可以看出：

通过盘符或者文件夹，我们只能向下访问其中的子文件和子文件夹，但是我们不能够从文件夹1直接跳转到文件夹2中去，正如我们不会在D盘中直接访问到C盘是一样的道理；
只有盘符或者文件夹下面才能够下挂子文件和子文件夹，但是文件之下是不能够下挂其他任何结构的；
每一个盘符和文件夹之下都有多个分支，这些分支“开枝散叶”，形成了复杂的分支结构，而这种分支结构在向上看的时候，最终都会回归到盘符这个层面，所以上面这张图正如同一棵倒置的大树，其树根在上。我们将这种由结点和分支构成，并且结点之间只能够上线联系，不能够左右沟通的结构，称之为树结构。

? ? ? ?在上图中，我们称所有的盘符、文件夹和文件为树结构的结点；而连接结点与结点之间的通路，称之为路径。如果一个结点指向另一个结点（例如文件夹1和文件2的关系），那么我们称上面指出的结点为父结点或者双亲结点（文件夹1）；下面被指向的结点称为父结点的孩子结点（文件2），孩子结点简称子结点。

综上，引出数的基本定义如下：

当n=0时，称作空树；
当n>0时，称作非空树；
- 在任意一棵非空树中，每一个圆圈称作一个结点（结点中包含一个数据元素及若干个指向其子树的分支），每个结点有0个或者多个子结点，但有且仅有一个特定的结点称作根结点（Root），位于树的最上方，根结点没有父结点，其余的结点称作非根结点，每一个非根结点有且只有一个父结点。
- 当n>1时，除根结点外的其余结点可分为m（m>0)个互不相交的有限集T1、T2、...、Tm，其中，每一个集合本身又是一棵树，称其为根的子树（SubTree）。

- 树中不存在环；
- 一个结点的直接后继结点称为该结点的孩子结点（Child）或子结点（或每一棵子树的根），习惯性的，我们将一个父结点左边的子结点称为左孩子结点，右边的子结点称之为右孩子结点；
- 一个结点的直接前驱结点称为该结点的双亲结点（Parent，雌雄同体）或父结点（或每一棵子树的根的父亲）；
- 同一双亲结点的孩子结点之间互称为兄弟结点（Siblings）；
- 其双亲在同一层的结点互称为堂兄弟结点。
- 结点的祖先是从根到该结点所经分支上的所有结点。
- 一个结点含有子结点个数称为结点的度（Degree），树中所有结点度的最大值称作树的度。
  - 度为0（即没有子结点）的结点称为叶结点（Leaf） 或 终端结点 或 叶子结点；
  - 度不为0的结点称作分支结点或非终端结点，除根结点外，分支结点也称为内部结点或中间结点；
  - 在许多面试题中，都使用n0、n1、n2分别表示度为0、度为1、度为2的结点的数量，即有0个孩子结点、1个孩子结点、2个孩子结点的结点数量。
    - 在任意一棵二叉树中，这些结点的数量之间存在着如下关系：
      1. n2 = n0 - 1：即度为2的结点个数总比度为0的结点个数少1，也就是说，在任意二叉树中，同时具有左右孩子的结点，总比叶子结点的数量少1个；
      2. 根据上式可推导出如下关系：n = n0 + n1 + n2 = 2 * n0 + n1 - 1 = n1 + 2 * n2 + 1，且n1 = n - n0 - n2 = n - 2n0 + 1 = n - 2n2 - 1，其中，n表示结点总数。
      3. 因此只要我们知道一个二叉树中总的结点个数以及度为0或者度为2的结点数量，就能够推导出其他度的结点数量。
- 结点的层次（Level）：从根结点开始算起，根结点的层次为第一层，根的直接后继（孩子）层次为第二层，以此类推，即：若某结点在第n层，则其子树就在第n+1层。将树中的结点按照从上层到下层、同层从左到右的次序进行展开，可以得到一个线性序列（此处与下面的结论存在问题：树中结点的最大层次称为树的深度（Depth）或高度（Height））。
  
  上图中，D、E、F是堂兄弟，G、H、I、J也是堂兄弟。树的深度为4。
- 对于任意结点Ni，Ni的深度（Depth）为从根结点到Ni的唯一的路径的长，因此，,根结点的深度为0。Ni的高度（Height）是从Ni到一片树叶的最长路径的长，因此，所有叶子结点的高都是0。一棵树的高等于它的根的高，一棵树的深度等于它的最深的树叶的深度，该深度总是等于这棵树的高。
- 结点E的深度为1，高度为2；结点F的深度为1，高度为1；树高=树深=3
- 从递归的定义中可以发现，一棵树是由N个结点和N-1条边的集合，其中的一个结点叫做根。得出存在N-1条边的的结论依据：每条边都将某个结点连接到它的父亲，而除去根结点外每个结点都有一个父亲，即N个结点总共N-1条边。
- 从结点N1到Nk的路径（Path）定义为结点N1、N2、...、Nk的一个序列，使得对于1≤i≤k结点Ni是Ni+1的父亲，这条路径的长（Length）为该路径上边的条数，即k-1.从每一个结点到它自己有一条长为0的路径，注意，在一棵树中从根到每个结点恰好存在一条路径。
- 从根结点到目标结点所经历的所有结点称为目标结点的祖先结点，某一结点的子女以及这些子女的子女均为该结点的子孙结点。。如果存在从N1到N2的一条路径，那么称N1是N2的一位祖先（Ancestor），而N2是N1的一个后裔（Descendant）。如果N1≠N2，则称N1是N2的真祖先（Proper Ancestor），而N2是N1的真后裔（Proper Descendant）。

如果将树中结点的各子树看成是从左到右有次序的且不能互换的，则称该树为有序树，否则称为无序树。
森林（Forest）：是m（m>=0）棵互不相交的树的集合，将一颗非空树的根结点删去，树就变成一个森林；给森林增加一个统一的根结点，森林就变成一棵树。对树中的每个结点而言，其子树的集合即为森林。

将线性表与树的结构进行对比如下：

线性表：
- 线性结构
- 第一个数据元素：无前驱
- 最后一个数据元素：无后继
- 中间元素：一个前驱、一个后继

树结构：
- 非线性结构
- 根结点：无双亲，唯一
- 叶结点：无孩子，可以多个
- 中间结点：一个双亲多个孩子

1.2 树的存储结构及Java实现

? ? ? ?实现树的一种方法可以是在每一个结点除存储数据外还要存储一些链，使得该结点的每一个儿子都可以有一个链指向它。然而每个结点的儿子树并不确定，因此在数据结构中建立到各儿子结点的直接的链接是不可行的，因为这样会浪费太多的空间。

? ? ? ?顺序存储和链式存储都不能很好地反映出树的逻辑关系，故需采用顺序和链式相结合的方式。树的存储方式主要有以下三种：

双亲表示法
孩子表示法
孩子兄弟表示法

1.2.1 双亲表示法

具体介绍详见：程杰《大话数据结构（溢彩加强版）》P130-P133

? ? ? ?双亲表示法采用顺序表（也就是数组）存储普通树，其实现的核心思想是：顺序存储各个结点的同时，给各结点附加一个记录其父结点位置的变量。注意：根结点没有父结点，因此根结点记录父结点位置的变量通常设为 -1。其结构特点如图所示：

对于下图的树而言，存储状态如表所示：

对应Java代码实现：

?class TreeNode{
? ?  int data;
? ?  int parent;
? ?  TreeNode(){}
? ?  TreeNode(int val){
? ? ? ?  this.data = val;
? ?  }
?}
??
?public class Tree {
? ?  TreeNode[] treeNodes;
? ?  int n;
?}

1.2.2 孩子表示法

具体介绍详见：程杰《大话数据结构（溢彩加强版）》P133-P136

? ? ? ?孩子表示法采用顺序加链式的存储方式，首先会建立一个顺序表存储树中的各个结点，此外，孩子表示法还会在每个结点后配备一个链表，用于存储它的子女结点，无子女结点的结点对应的是空链表。存储状态示意图如下：

对应Java代码实现：

?class TreeNode{
? ?  int val;
? ?  TreeNode next;
? ?  TreeNode(){}
? ?  TreeNode(int val){
? ? ? ?  this.val = val;
? ?  }
?}

1.2.3 孩子兄弟表示法

具体介绍详见：程杰《大话数据结构（溢彩加强版）》P136-P137

? ? ? ? 孩子兄弟表示法采用的是链式存储的方式，从树的根结点开始，依次使用链表存储各个结点的孩子结点和兄弟结点，该链表中的结点分为三部分：孩子结点、数据域、兄弟结点。存储状态示意图如下：

对应Java代码实现：

?class TreeNode{
? ?  int val;
? ?  TreeNode child;
? ?  TreeNode brother;
? ?  TreeNode(){}
? ?  TreeNode(int val){
? ? ? ?  this.val = val;
? ?  }
?}