在计算机科学中，树（tree）是一种抽象数据类型（ADT）或是实现这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>0）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
1 . 每个节点都只有有限个子节点或无子节点；
2 . 没有父节点的节点称为根节点；
3 . 每一个非根节点有且只有一个父节点；
4 . 除了根节点外，每个子节点可以分为多个不相交的子树；
5 . 树里面没有环路。
树比线性结构复杂，细分类别也很多，一篇文章很难把树讲清楚，本文主要概述各种树的关系和定义，方便全局的了解树这个概念。
树的分类
无序树：也叫自由树，就是一个无回路的连通图（没有确定根，在自由树中选定一顶点做根，则成为一棵通常的树）。从根开始，为每个顶点（在树中通常称作结点）的孩子规定从左到右的次序，则它就成为一棵有序树。
有序树：树中任意节点的子节点之间有顺序关系，这种树称为有序树。
这些关系和相关术语如下；
1 . 节点的度：一个节点含有的子树的个数称为该节点的度；
2 . 树的度：一棵树中，最大的节点度称为树的度；
3 . 叶节点或终端节点：度为0的节点；
4 . 非终端节点或分支节点：度不为0的节点；
5 . 父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
6 . 子节点：一个节点含有的子树的根节点称为该节点的子节点；
7 . 兄弟节点：具有相同父节点的节点互称为兄弟节点；
8 . 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，依此类推；
9 . 深度：对于任意节点n,n的深度为从根到n的唯一路径长，根的深度为0；
10 . 高度：对于任意节点n,n的高度为从n到一片树叶的最长路径长，所有树叶的高度为0；
11 . 节点的祖先：从根到该节点所经分支上的所有节点；
12 . 节点的子孙：以某节点为根的子树中任一节点都称为该节点的子孙；
13 . 森林：由m（m>=0）棵互不相交的树的集合称为森林。
为了实现具体的算法或特定的数据结构，会对树做一些限制，有了这些限制以后，树就可以在特定场景发挥它的作用，主要类别和具体限制如图：
对图中重要的树类型说明如下：
二叉树
每个节点最多含有两个子树的树称为二叉树；
完全二叉树：每层结点都完全填满的二叉树，在最后一层上如果不是满的，则只缺少右边的若干结点。
满二叉树：也叫完美二叉树，所有的非叶子结点都有两个孩子，所有的叶子结点都在同一层的二叉树。
二叉查找树
二叉查找树简称BST（Binary Search Tree），也有人叫它二叉搜索树，排序二叉树，有很多相似的名字，很多人会把这些名字弄混，以为是多种树，其实这些都是一个类型。它在二叉树的基础上，还有以下特征：
1 . 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
2 . 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
3 . 任意节点的左、右子树也分别为二叉查找树；
这三条的三个限制就是：左比根小，右比根大，子树同样满足，这样数据就是有序的（中序遍历从小到大排列），查找一个数据可以根据当前节点和目标值的大小判断去左边查找还是右边查找，只需要O(lgn)的时间复杂度就能找到所需的元素，这也是它被冠以查找，搜索这些名词的原因，因为它查找数据快捷。
自平衡二叉查找树
自平衡二叉查找树（Self-Balancing Binary Search Tree）：也简称平衡二叉树，平衡查找树，甚至直接叫平衡树。如果把这些简称和上面的二叉查找树的各种叫法混在一起，肯定会分不清。所以记住，二叉查找树往下划分类别，带平衡的就是更细粒度的划分。
对二叉查找树来说查找是基本需求，但是查找树有一个缺点，就是输入的数据如果偏向一边，会形成一个类似于链式的结构，比如根元素就是最大的，然后左子树第二大，左子树的左子树第三…这样的树就成了线性了，查找的复杂度就会提升为O(n),加入平衡就是为了担保查找最差性能还能维持在O(lgn)级别。
为什么叫自平衡呢？站在数据结构设计的角度，这么称呼才合理的，因为普通的二叉查找树通过手动去调整，也可以让他平衡，所以数据结构的平衡就是在ADT层面就考虑好数据怎么自我保持平衡，这样的数据结构，才能拿出来就能用。
AVL树
AVL树种任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是O(lgn)。增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。
那么增加和删除是怎么旋转达到平衡的呢？这里有一个概念：平衡因子（Balance Factor）某个结点的左子树的高度减去右子树的高度得到的差值。
AVL树只要发现平衡因子大于1或小于-1，就会触发旋转让它回到{-1，0，1}这个范围。旋转分为左旋和右旋，以左旋为例，一个不平衡的树，根节点值是0，插入一个子节点值为1，它比根节点大，变成右子节点，再插入一个子节点值为2，比右子节点大，成为右子节点的右子节点。这个时候根节点的高度是2，它的左子树为空，高度是0，右子树有一个儿子，高度是2，平衡因子为0-2=-2，小于-1，所以需要进行调整，调整的方式就是右子节点变为根节点，根节点比右子节点小，变成了新根节点的左节点，新根节点原来就带有一个右子节点保持不变。这样树的平衡因子就变成0了，达到目标。形象的想象这一过程就是从中间提起右子节点，根节点就往左倾斜，所以叫左旋。
红黑树
红黑树是一种自平衡二叉查找树，在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。红黑树有以下5条约束：
1 . 节点是红色或黑色。
2 . 根是黑色。
3 . 所有叶子都是黑色。
4 . 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
5 . 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
这些约束确保了红黑树的关键特性，性质4导致了路径不能有两个毗连的红色节点，最短的可能路径都是黑色节点，最长的可能路径有交替的红色和黑色节点。因为根据性质5所有最长的路径都有相同数目的黑色节点，这就表明了没有路径能多于任何其他路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的。
红黑树上进行插入操作和删除操作会导致不再符合红黑树的性质。恢复红黑树的性质需要少量的颜色变更（实际是非常快速的）和不超过三次树旋转（对于插入操作是两次）。
因为红黑树操作相对复杂，需要大量的描述，本文只是概述，计划配合示例代码另起一篇文章单独讲解。
伸展树
伸展树是一种自平衡的二叉查找树，考虑到一种场景，刚被访问的内容下次可能仍会被访问，查找次数多的内容可能下一次会被访问，为了使整个查找时间更小，想到设计一个简单方法，在每次查找之后对树进行调整，把被查找的条目搬移到离树根近一些的地方。
伸展树的自我平衡使其拥有良好的性能，因为频繁访问的节点会被移动到更靠近根节点，进而获得更快的访问速度。
优点：可靠的性能——它的平均效率不输于其他平衡树；存储所需的内存少——伸展树无需记录额外的什么值来维护树的信息，相对于其他平衡树，内存占用要小。
缺点：它有可能会变成一条链。例如，在以非递减顺序访问全部n个之后就会出现这种情况。此时树的高度对应于最坏情况的时间效率，操作的实际时间效率可能很低；即使以“只读”方式（例如通过查找操作）访问伸展树，其结构也可能会发生变化。这使得伸展树在多线程环境下会变得很复杂。具体而言，如果允许多个线程同时执行查找操作，则需要额外的维护和操作。这也使得它们不适合在纯粹的函数式编程中普遍使用，尽管用于实现优先级队列的方式不多。
堆
堆（Heap）是计算机科学中的一种特别的树状数据结构。若是满足以下特性，即可称为堆：“给定堆中任意节点P和C，若P是C的父节点，那么P的值会小于等于（或大于等于）C的值”。若父节点的值恒小于等于子节点的值，此堆称为最小堆（min heap）；反之，若父节点的值恒大于等于子节点的值，此堆称为最大堆（max heap）。在堆中最顶端的那一个节点，称作根节点（root node）。
堆的实现通过构造二叉堆（binary heap），具有以下性质。
1 . 任意节点小于（或大于）它的所有子孙，最小元（或最大元）在堆的根上（堆序性）。
2 . 堆总是一棵完全树。即除了最底层，其他层的节点都被元素填满，且最底层尽可能地从左到右填入。
注意：堆和二叉查找树最大的区别是堆规定的是上下的大小，而二叉查找树规定的是左右的大小。
霍夫曼树
霍夫曼树是给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为霍夫曼树(Huffman Tree)。霍夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每一结点的路径长度之和，记为WPL=（W1L1 W2L2 W3L3 … WnLn），N个权值Wi（i=1,2,…n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1,2,…n）。
B树
B树（B-tree）是一种自平衡多叉查找树，能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作，都在对数时间内完成。一个节点可以拥有2个以上的子节点。与自平衡二叉查找树不同，B树适用于读写相对大的数据块的存储系统，例如磁盘。B树减少定位记录时所经历的中间过程，从而加快存取速度。B树这种数据结构可以用来描述外部存储。这种数据结构常被应用在数据库和文件系统的实现上。
在B树中，内部非叶节点可以拥有可变数量的子节点（数量范围预先定义好）。当数据被插入或从一个节点中移除，它的子节点数量发生变化。为了维持在预先设定的数量范围内，内部节点可能会被合并或者分离。因为子节点数量有一定的允许范围，所以B树不需要像其他自平衡查找树那样频繁地重新保持平衡，但是由于节点没有被完全填充，可能浪费了一些空间。子节点数量的上界和下界依特定的实现而设置。例如，在一个2-3 B树（通常简称2-3树），每一个内部节点只能有2或3个子节点。
一个m阶的B树具有如下几个特征：
1.根结点至少有两个子女。
2.每个中间节点都包含k-1个元素和k个孩子，其中 m/2 <= k <= m
3.每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m
4.所有的叶子结点都位于同一层。
5.每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。
2-3-4树
2-3-4树是b树的一种，而红黑树是二叉树，看上去可能完全不同，但是，在某种意义上它们又是完全相同的，一个可以通过应用一些简单的规则变成另一个，而且使他们保持平衡的操作也是一样，数学上称他们为同构。
2-3-4 树在多数编程语言中实现起来相对困难，因为在树上的操作涉及大量的特殊情况。红黑树实现起来更简单一些，所以可以用它来替代。应用如下三条规则可以将2-3-4树转化为红黑树：
1 . 把2-3-4树中的每个2-节点转化为红-黑树的黑色节点。
2 . 把每个3-节点转化为一个子节点和一个父节点，子节点有两个自己的子节点：W和X或X和Y。父节点有另一个子节点：Y或W。哪个节点变成子节点或父节点都无所谓。子节点涂成红色，父节点涂成黑色。
3 . 把每个4-节点转化为一个父节点和两个子节点。第一个子节点有它自己的子节点W和X；第二个子节点拥有子节点Y和Z。和前面一样，子节点涂成红色，父节点涂成黑色。
B 树
B 树是一种树数据结构，通常用于数据库和操作系统的文件系统中。B 树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。B 树的特征：
1.有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
2.所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
3.所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。
字典树
字典树又称前缀树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。
举个例子，对于单词存储，根节点为t，两个子节点分别为a和o，a有两个子节点g和k，k有一个子节点e，这样的树输入根节点t的时候就可以检索三个单词tag，take，to，再输一个a还能检索到两个单词tag，take。完整的信息是从一个根到叶节点的路径决定的，从根节点往下检索可以联想出所有相关信息。
小结
树结构的概述就到这里，可以通过上面的内容看清树这个体系的脉络，后期会对几种最重要的树分别单独写文章和示例代码讲解。
