算法与数据结构(四)-树的定义和类型
前言
在目前计算机科学中，树（英语：tree）是一种抽象数据类型（ADT）或是实现这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它的形象因为像一颗大树,所以被称为树。树是历来程序面试的考点，它在Java 、C、Python等等均有实现的类型。
树的定义
树是 n （n >= 0） 个节点的有限集。 n = 0 时 我们称之为空树, 空树是树的特例。
在任意一棵非空树中：
- 有且仅有一个特定的节点称为根（Root）的节点
- 当 n > 1 时，其余节点可分为 m （m > 0）个
互不相交的有限集T1、T2、……..Tm，其中每一个集合本身又是一棵树，并且称为根的子树。
有且仅有一个特定的节点称为根节点，也就是上图中的橙色节点。
当节点数目大于 1 时，除根节点以外的节点，可分为 m 个互不相交的有限集 T1,T2……..Tm。
例如上图中，我们将根节点以外的节点，分为了 T1 （2，3，4，5，6，7），T2（8，9）两个有限集。
那么 T1 （绿色节点）和 T2（蓝色节点）就是根节点（橙色节点）的子树。
树定义:除根节点以外的节点，所有的子树节点不能相交。
上图中(A) , (B) 符合树的定义，（C）, (D) 不符合，这是因为 (C) , (D) 它们都有相交的子树。
节点类型\节点间的关系
孩子节点/子节点:一个节点含有的子树的根节点称为该节点的子节点.
例如:1的子节点为2,8
节点的度:一个节点含有的子节点的个数称之为该节点的度.
例如:1节点的度为2,2节点的度为2,4节点的度为3.
树的度:一棵树中,最大的节点的度称之为树的度.
例如:该树的度为3,因为节点4的度最大为3.
叶节点/终端节点:度为0的节点.
例如:5,6,7,3,9节点都被称为叶节点或者终端节点
内部节点/非终端节点:除根节点外,度不为0的节点.
例如;2,4,8节点
双亲节点/父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点.
例如:4的父节点为2,8为9的父节点.
兄弟节点:具有相同父节点的节点互称为兄弟节点.
例如:3父节点为2,4父节点也为2.所以 3节点的兄弟节点为2 反之亦然.
节点的层次:见下图,从根开始定义,第一层,第二层…
堂兄弟节点:双亲在同一层的节点互为堂兄弟节点.
例如:4和9,3和9
节点的祖先:从根到该节点所经过分支上的所有节点.
例如:节点5的祖先为4,2,1节点
节点的子孙:以某节点为根的子树中任一节点都称为该节点的子孙.
例如:节点2的子孙为3,4,5,6,7
树的高度/深度:树中节点的最大层次.
例如:上图树的高度为4
节点的深度:根节点到这个节点所经历的边的个数,也就是节点的层次-1
例如:节点4的深度为2
节点的高度:节点到叶子节点的最大边数.
例如:节点2到叶子节点3的边数为1,到其他叶子节点(节点5,6,7)的边数为2,所以节点2的高度为2.
森林: m(m>=0) 颗互不相交的树的集合
注意:节点的高度和深度可能容易记混
所以 在求深度时，从上往下测量，求高度时，从下往上测量，节点的高度和深度也是如此。
树的种类
二叉树
二叉树前提是一棵树，也就是需要满足我们树的定义的同时，还需要满足要求:
- 每个节点
最多有两个子节点，分别是左子节点和右子节点。(二叉树并不是必须要求每个节点都有两个子节点,也可以仅有一个左子节点，或者仅有一个右子节点。)
二叉树的特点
每个节点最多有两棵子树，也就是说二叉树中不存在度大于 2 的节点，节点的度可以为 0，1，2。
左子树和右子树是有顺序的,有左右之分。
假如只有一棵子树 ，也要区分它是左子树还是右子树
完全二叉树
叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。
可以这样理解，除了最后一层，其他层的节点个数都是满的，而且最后一层的叶子节点必须靠左。
所以上图中(A）（B）为完全二叉树，（C）（D）不是完全二叉树.
满二叉树
指在一棵二叉树中，所有分支节点都存在左子树和右子树，并且所有的叶子都在同一层,这种树我们称之为完全二叉树.
所以满二叉树也为完全二叉树的一种。
所以上图中只有(B)是满二叉树.
斜二叉树
斜二叉树也就是斜的二叉树.
所有的节点只有左子树的称为左斜树,所有节点只有右子树的二叉树称为右斜树.
红黑数
红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。
它的每个节点存储一个表示“颜色”(“红色”或“黑色”)的额外位，用于确保树在插入和删除期间保持平衡。
红黑树在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能，它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。
红黑树是每个节点都带有颜色属性的二叉查找树，颜色为红色或黑色。
除了二叉查找树强制一般要求以外，对于任何有效的红黑树我们有如下的额外要求：
- 节点是红色或黑色。
- 根一定是黑色。
- 所有叶子节点都是黑色（NIL节点也是叶子节点）。
- 每个红色节点必须有两个黑色的子节点。（所以从每个叶子到根的所有路径上不能有两个连续的红色节点。）
- 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
这些要求确保了红黑数的关键特性：从根到叶子的最长的路径不多于最短的路径的两倍长。
在很多其它树数据结构的表示中，一个节点有可能只有一个子节点，由于红黑数是一定平衡的存在，所以红黑树对于这种情况，允许使用”nil叶子”或”空（null）叶子”，它不包含数据而只充当树在此结束的指示（占位）。
B数
一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多于两个子树。
首先，B树不要和二叉树混淆，B树是一种自平衡树数据结构。B树适用于读写相对大的数据块的存储系统，例如磁盘。B树减少定位记录时所经历的中间过程，从而加快存取速度。B树这种数据结构可以用来描述外部存储。这种数据结构常被应用在数据库和文件系统的实现上。
B树是一种平衡的多分树，通常我们说m阶的B树，它必须满足如下条件：
- 每个节点最多只有m个子节点。
- 每个非叶子节点（除了根）具有至少⌈ m/2⌉子节点。
- 如果根不是叶节点，则根至少有两个子节点。
- 具有k个子节点的非叶节点包含k -1个键。
- 所有叶子都出现在同一水平，没有任何信息（高度一致）。
其中B树中一个节点的子节点数目的最大值，用m表示，假如最大值为10，则为10阶，如图:
所有节点中，节点【13,16,19】拥有的子节点数目最多，四个子节点（灰色节点），所以可以定义上面的图片为4阶B树，现在懂什么是阶了吧