树是一种非线性的数据结构，它是由 n（n≥0）个有限节点组成一个具有层次关系的集合。当 n = 0 时，称为空树。在非空树中，有且仅有一个根节点（root），其余节点可分为 m（m≥0）个互不相交的有限集，每个集合本身又是一棵树，称为根的子树（sub - tree）。
树的常用术语(结合示意图理解):
根节点
父节点
子节点
叶子节点 (没有子节点的节点)
节点的权(节点值)
路径(从root节点找到该节点的路线)
层
子树
树的高度(最大层数)
二叉树（Binary Tree）
二叉树是一种特殊的树，每个节点最多有两个子树，通常称为左子树和右子树，并且左子树和右子树是有顺序的，不能随意交换。
- 满二叉树（Full Binary Tree）：除了最后一层无任何子节点外，每一层上的所有节点都有两个子节点。例如，一个深度为 3 的满二叉树，第 1 层有 1 个节点，第 2 层有 2 个节点，第 3 层有 4 个节点。
- 完全二叉树（Complete Binary Tree）：设二叉树的深度为 h，除第 h 层外，其它各层 (1～h - 1) 的节点数都达到最大个数，第 h 层所有的节点都连续集中在最左边。就好像一个三角形阵列，除了最后一行可能不满，上面的行都是满的，并且最后一行的节点是从左到右依次排列的。
顺序存储二叉树
二叉树的结点，可以用数组的方式来存放，但是在插入和查询时需要用二叉树的方式去操作。顺序存储二叉树有几个特点：二叉树的节点按照层次顺序存储在一个数组中，根节点存储在数组的第一个位置（索引为 0 或 1，通常为 1），如果节点的索引为 i，那么它的左子节点索引为 2i，右子节点索引为 2i + 1。这种存储方式适用于完全二叉树，对于非完全二叉树会浪费大量的存储空间。例如，一个完全二叉树有 7 个节点，存储在数组中，根节点在索引 1，它的左子节点在索引 2，右子节点在索引 3，以此类推。
顺序存储二叉树在堆的结构中曾经有过使用，堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆,反之则为小顶堆。 注意 : 没有要求结点的左孩子的值和右孩子的值的大小关系。最大堆与最小堆都可以使用这种结构去创建，然后在通过上滤或者下滤操作为堆中元素找到合适的位置。
链式存储二叉树
通过节点类来存储二叉树，每个节点包含数据域、左子节点引用和右子节点引用。
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
this.left = null;
this.right = null;
}
二叉树的遍历：
前序遍历: 先输出父节点，再遍历左子树和右子树。例如，对于二叉树节点值为 1（根），左子树节点值为 2，右子树节点值为 3 的二叉树，前序遍历结果为 1,2,3。
中序遍历: 先遍历左子树，再输出父节点，再遍历右子树。例如，对于上述二叉树，中序遍历结果为 2,1,3。
后序遍历: 先遍历左子树，再遍历右子树，最后输出父节点。例如，对于上述二叉树，后序遍历结果为 2,3,1。
小结: 看中间节点的顺序，从而确定是前序，中序还是后序。
层序遍历（Level - order Traversal）：从根节点开始，按照层次顺序依次访问每一层的节点。通常借助队列来实现，先将根节点入队，然后循环取出队首节点，访问该节点，并将其左右子节点入队。例如，对于一个简单的二叉树，根节点为 1，左子树节点为 2，右子树节点为 3，层序遍历结果为 1,2,3。
二叉搜索树（Binary Search Tree，BST）
二叉搜索树是一种特殊的二叉树，是具有下列性质：若它的左子树不空，则左子树所有节点的值均小于它的根节点的值；若它的右子树不空，则右子树所有节点的值均大于它的根节点的值；它的左、右子树也分别为二叉搜索树。即：左子树<父节点<右子树
二叉搜索树好处：当使用数组查找某一个值时，如果数组未排序则呢额需要遍历数组，时间复杂度最高位log(n),数组排序可是有二分查找，但是插入的话需要修改插入点后面的数据向后移动，速度不理想。而使用链表的话插入速度快，但是查找还是很慢。而二叉树查找与插入的速度都很快，同时优化了链表与数组的缺陷，查找与插入速度在最优情况下是log2(n)。
//实现二叉搜索树的插入操作
class BinarySearchTree {
TreeNode root;
// 插入方法
public void insert(int value) {
root = insertRec(root, value);
}
private TreeNode insertRec(TreeNode node, int value) {
if (node == null) {
return new TreeNode(value);
}
if (value < node.val) {
node.left = insertRec(node.left, value);
} else if (value > node.val) {
node.right = insertRec(node.right, value);
}
return node;
}
}
//实现二叉搜索树的查询操作
class BinarySearchTree {
//... 前面的插入相关代码省略
// 查询方法，判断值是否存在于树中
public boolean search(int value) {
return searchRec(root, value);
}
private boolean searchRec(TreeNode node, int value) {
if (node == null) {
return false;
}
if (value == node.val) {
return true;
} else if (value < node.val) {
return searchRec(node.left, value);
} else {
return searchRec(node.right, value);
}
}
}
二叉排序树的删除情况比较复杂，有下面三种情况需要考虑:
一、删除叶子节点：直接删除，根据当前节点位置将父节点的对应节点设置为null。
二、删除有一颗子树的节点：
1）删除的为左节点：父节点的左节点设置为子树
2）删除的为右节点：父节点的右节点设置为子树
三、删除有俩颗子树的节点：
找到当前节点下右子树中最小的节点，临时设置一个temp保存当前的节点，删除最小的节点，然后将要删除的节点设置成temp
平衡二叉树-红黑树
二叉排序树可有一个问题，便是当插入的数组是有序数列时（升序或者倒序），二叉树可能会形成一个单链表形式。此时查询速度明显降低，没有了二叉树的查找优势，反而因为还需要对比俩个子树，查询速度比单链表还慢。此时就需要一种新的解决方式-平衡二叉树。
衡二叉树有以下特点：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。我们单独讲解一下红黑树的构造。
红黑树除了符合二叉查找树的基本特性外，还具有下列的附加特性：
- 节点是红色或黑色。
- 根节点是黑色。
- 每个叶子节点都是黑色的空节点（NIL节点）。
- 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
上面一系列的规则，保证了红黑树的自平衡。红黑树从根到叶子的最长路径不会超过最短路径的2倍。但是当插入或删除节点的时候，红黑树的规则有可能被打破，这个时候需要进行调整来维持红黑树的规则。想要了解如何调整红黑树需要先知道红黑树的基本操作变色与旋转。
变色：新节点的默认颜色是红色，因为新节点如果是黑色的话，那么就不符合从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点，从而需要大幅度的去调整红黑树，所以新节点默认为红色。但是当新节点的父节点也为红色的情况下，就需要调整红黑树，其中就用到了变色操作。变色操作具体使用方式如下：将新节点的父节点与叔叔节点设置为黑色，然后将祖父节点设为红色，再将祖父节点当做新节点继续向上操作，直到根节点变色后，如果跟根节点不为黑色则需要旋转操作。
旋转：
旋转分为左旋与右旋，操作方式类似只不过操作对象相反，这里只讲解一下左旋：
例如新增节点γ如果与父节点Y都是红色的话不符合红黑树结构此时需要针对X旋转操作
1.现将X的右节点这职位Y的左节点β，这一步我叫它新建子树也就是创建需要旋转的子树的新节点
2.将X的父节点设置成Y的父节点，这一步是更新节点，也就是旋转的中心点的更新
2.将Y的左节点设置成X，最后一步完成旋转，将新建的子树旋转的中心点左侧
右旋与左旋操作步骤一致只不过操作方向相反。就不做具体介绍了。
代码如下
package com.example.demo.RedBlankTree;
/**
* 红黑树
*
* 左旋和右旋实现
* @author hh
*/
public class RBTree {
RBNode root;
/**
* 对x进行左旋
* 从上往下看变化
* p p
* / /
* x 对x左旋 y
* / \ -------> /\
* lx y x ry
* /\ / \
* ly ry lx ly
*
* @param x
*/
private void leftRoute(RBNode x) {
RBNode y = x.right;
RBNode ly = y.left;
//将y的左节点指向x的右节点
x.right = ly;
//如果y的左节点ly不为空 把ly的父节点 指向x
if (ly != null) {
ly.parent = x;
}
//将原来x的父节点 指向为y的父节点（更新父节点）
y.parent = x.parent;
if (x.parent == null) {
this.root = y;
} else {
//如果x为左节点
if (x == x.parent.left) {
x.parent.left = y;
} else {
//如果x为右节点
x.parent.right = y;
}
}
//更新xy与下面子节点的关系
y.left = x;
x.parent = y;
}
/**
* 右旋
* 同上
*
* @param x
*/
private void rightRoute(RBNode x) {
RBNode y = x.left;
x.left = y.right;
if (y.right != null) {
y.right.parent = x;
}
if (y == null) {
this.root = y;
} else {
if (x == x.parent.left) {
//如果为左节点
x.parent.left = y;
} else {
//x为右节点
x.parent.right = y;
}
}
y.left = x;
x.parent = y;
}
/**
* 红黑树节点
*
* @param <T>
*/
final class RBNode<T extends Comparable<T>> {
/**
* 颜色
*/
boolean color;
/**
* 节点值
*/
T key;
/**
* 左节点
*/
RBNode<T> left;
/**
* 右节点
*/
RBNode<T> right;
/**
* 父节点
*/
RBNode<T> parent;
public T getKey() {
return key;
}
}
}
了解了变色与旋转后，再来看红黑树的添加，当添加了一个新的红节点以后，此时会出现四种情况：
1.新增红节点，父节点为黑节点，此时没有违反红黑树任何性质，可以直接插入
2.新增红节点，父节点为红节点，此时不能有连在一起的红节点这条规则显然是不满足了，所以就需要调整红黑树结构,这时主要看父节点的兄弟节点的颜色与新增节点的位置。
1）兄弟节点存在且为红色
此时只需要进行变色操作，然后继续向上调整即可满足红黑树条件。
2）兄弟节点不存在或者存在为黑色，且新增节点位置与父节点在同一方向
此时需要新增节点的位置（左节点、右节点）来决定是左旋还是右旋，旋转中心则为父节点
旋转一次后再将祖父节点与父节点颜色对调即可满足红黑树结构。
当新增节点与父节点方向不一致时，需要先以新增节点为中心点进行一次旋转，将树转换为上一种情况，然后在进行二次旋转即可完成调整。
最优二叉树-霍夫曼树
是定n个权值作为n个叶子结点，构造一棵二叉树，该树的带权路径长度(wpl)达到最小则被称为最优二叉树霍夫曼树也叫哈夫曼树。其中从根节点到叶子节点走过的通路称为路径，中间经过了几个节点数量则为路径长度。若给也子节点设置一个带有某种意义的数值权，那么临界点的带权路径长度为路径长度×权，树的带权路径长度WPL=各个节点带权路径长度的和。例如，对于叶子结点权值分别为2、3、4、5的二叉树，若其对应的路径长度分别为2、2、2、2，则该树的WPL=2×2+3×2+4×2+5×2=28。
构成赫夫曼树的步骤：
1)从小到大进行排序, 将每一个数据，每个数据都是一个节点 ， 每个节点可以看成是一颗最简单的二叉树
2)取出根节点权值最小的两颗二叉树
3)组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和
4)再将这颗新的二叉树，以根节点的权值大小 再次排序， 不断重复 1-2-3-4 的步骤，直到数列中，所有的数据都被处理，就得到一颗赫夫曼树。
赫夫曼树实际用例：无损压缩之-赫夫曼编码
