4-5 二叉树

二叉树

本版块主要学习的是二叉树，树也是一种数据结构，但是它使用起来更加的复杂。

树

我们前面已经学习过链表了，我们知道链表是单个结点之间相连，也就是一种一对一的关系，而树则是一个结点连接多个结点，也就是一对多的关系。

一个结点可以有N个子结点，就像上图一样，看起来就像是一棵树。而位于最顶端的结点（没有父结点）我们称为根结点，而结点拥有的子节点数量称为度，每向下一级称为一个层次，树中出现的最大层次称为树的深度(高度)。

二叉树

二叉树是一种特殊的树，每个结点最多有两颗子树，所以二叉树中不存在度大于2的结点，位于两边的子结点称为左右子树（注意，左右子树是明确区分的，是左就是左，是右就是右）

数学性质：

• 在二叉树的第i层上最多有2^(i-1) 个节点。
• 二叉树中如果深度为k，那么最多有2^k-1个节点。

设计一个二叉树结点类：

public class TreeNode<E> {
    public E e;   //当前结点数据
    public TreeNode<E> left;   //左子树
    public TreeNode<E> right;   //右子树
}

二叉树的遍历

顺序表的遍历其实就是依次有序去访问表中每一个元素，而像二叉树这样的复杂结构，我们有四种遍历方式，他们是：前序遍历、中序遍历、后序遍历以及层序遍历，本版块我们主要讨论前三种遍历方式：

• 前序遍历：从二叉树的根结点出发，到达结点时就直接输出结点数据，按照先向左在向右的方向访问。ABCDEF
• 中序遍历：从二叉树的根结点出发，优先输出左子树的节点的数据，再输出当前节点本身，最后才是右子树。CBDAEF
• 后序遍历：从二叉树的根结点出发，优先遍历其左子树，再遍历右子树，最后在输出当前节点本身。CDBFEA

//假设hash表长度为16，hash算法为：

数组中每一个元素都是一个头结点，用于保存数据，那我们怎么确定数据应该放在哪一个位置呢？通过hash算法，我们能够瞬间得到元素应该放置的位置。
//假设hash表长度为16，hash算法为：
private int hash(int hashcode){
return hashcode % 16;
}
设想这样一个问题，如果计算出来的hash值和之前已经存在的元素相同了呢？这种情况我们称为hash碰撞，这也是为什么要将每一个表元素设置为一个链表的头结点的原因，一旦发现重复，我们可以往后继续添加节点。
当然，以上的hash表结构只是一种设计方案，在面对大额数据时，是不够用的，在JDK1.8中，集合类使用的是数组+二叉树的形式解决的（这里的二叉树是经过加强的二叉树，不是前面讲得简单二叉树，我们下一节就会开始讲）

二叉排序树

我们前面学习的二叉树效率是不够的，我们需要的是一种效率更高的二叉树，因此，基于二叉树的改进，提出了二叉查找树，可以看到结构像下面这样：

不难发现，每个节点的左子树，一定小于当前节点的值，每个节点的右子树，一定大于当前节点的值，这样的二叉树称为二叉排序树。利用二分搜索的思想，我们就可以快速查找某个节点！

平衡二叉树

在了解了二叉查找树之后，我们发现，如果根节点为10，现在加入到结点的值从9开始，依次减小到1，那么这个表就会很奇怪，就像下面这样：

显然，当所有的结点都排列到一边，这种情况下，查找效率会直接退化为最原始的二叉树！因此我们需要维持二叉树的平衡，才能维持原有的查找效率。
现在我们对二叉排序树加以约束，要求每个结点的左右两个子树的高度差的绝对值不超过1，这样的二叉树称为平衡二叉树，同时要求每个结点的左右子树都是平衡二叉树，这样，就不会因为一边的疯狂增加导致失衡。我们来看看以下几种情况：

左左失衡

右右失衡

左右失衡

右左失衡
通过以上四种情况的处理，最终得到维护平衡二叉树的算法。

红黑树

红黑树也是二叉排序树的一种改进，同平衡二叉树一样，红黑树也是一种维护平衡的二叉排序树，但是没有平衡二叉树那样严格（平衡二叉树每次插入新结点时，可能会出现大量的旋转，而红黑树保证不超过三次），红黑树降低了对于旋转的要求，因此效率有一定的提升同时实现起来也更加简单。但是红黑树的效率却高于平衡二叉树，红黑树也是JDK1.8中使用的数据结构！

红黑树的特性:（1）每个节点或者是黑色，或者是红色。（2）根节点是黑色。（3）每个叶子节点的两边也需要表示（虽然没有，但是null也需要表示出来）是黑色。（4）如果一个节点是红色的，则它的子节点必须是黑色的。（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
我们来看看一个节点，是如何插入到红黑树中的：
基本的 插入规则和平衡二叉树一样，但是在插入后：

1. 将新插入的节点标记为红色
2. 如果 X 是根结点(root)，则标记为黑色
3. 如果 X 的 parent 不是黑色，同时 X 也不是 root:

• 3.1 如果 X 的 uncle (叔叔) 是红色
  • 3.1.1 将 parent 和 uncle 标记为黑色
  • 3.1.2 将 grand parent (祖父) 标记为红色
  • 3.1.3 让 X 节点的颜色与 X 祖父的颜色相同，然后重复步骤 2、3
• 3.2 如果 X 的 uncle (叔叔) 是黑色，我们要分四种情况处理
  • 3.2.1 左左 (P 是 G 的左孩子，并且 X 是 P 的左孩子)
  • 3.2.2 左右 (P 是 G 的左孩子，并且 X 是 P 的右孩子)
  • 3.2.3 右右 (P 是 G 的右孩子，并且 X 是 P 的右孩子)
  • 3.2.4 右左 (P 是 G 的右孩子，并且 X 是 P 的左孩子)
  • 其实这种情况下处理就和我们的平衡二叉树一样了