树-基本概念认知

树和图是非线性的逻辑结构。下图描述了树的相关概念。

二叉树

二叉树指的是每个节点的孩子节点最多有两个(可以有两个、一个或者没有孩子节点)。

在二叉树中还有两种特殊的二叉树，分别是满二叉树和完全二叉树。

满二叉树要求所有的非叶子节点必须有左右孩子节点。

完全二叉树只要确保节点从左往右从上往下节点的顺序和同样深度的满二叉树一样，同时只需要确保除了最后一个节点都是齐全的就可以。例如下图就是一个完全二叉树。

二叉树是一种逻辑结构，那么在实际存储时二叉树可以用链表或者数组进行存储。

二叉树链表

使用链表存储二叉树还是比较直观的，基本定义如下：

public class Node<T> {    T data;    Node<T> left;    Node<T> right;}

二叉树数组

二叉树使用数组存储可能没有链表来的直观，下面我们可以看一下数组是如何存储二叉树的节点的。

二叉树在数组中按照节点的顺序进行存储，如果二叉树的某个节点不存在，那么该节点对应的索引位置则不进行存储。这样设计的目的是为了方便定位二叉树的节点位置。

假设一个父节点的索引位置为i，那么他的左孩子节点索引2i+1，右孩子节点为2i+2，相反根据一个子节点也可以推出他的父节点的位置。

二叉树应用

二叉树主要应用在查找操作和维持相对顺序。

二叉查找树（二叉排序树）

二叉查找树需要满足以下条件：

• 如果左子树不为空，那么左子树上的所有值都要小于根节点
• 如果右子树不为空，那么右子树上的所有值都要大于根节点
• 左右子树也必须是二叉查找树

查找操作

比如查找一个节点值为4的节点，首先他会看根节点，发现4比根节点小，然后就去找根节点的左子树，然后就发现节点值为3的节点，于是就去找他的右子树，因此查找到了4节点，对于一个相对平衡(非常重要)的二叉查找树的平均时间复杂度是O(logn)。

插入操作

看一下二叉查找树的插入操作，在二叉查找树进行插入时必须要维护二叉查找树的规则，比如插入一个节点值为5的节点，由于5 < 6，因此和左子树比较，5 > 3，继续和3的右子树比较，5 > 4同时4又没有子节点，因此将5插入4的右子节点。看上去很不错，但是这样的插入会有一种弊端，可以看下图，依次插入9、8、7、6

上面二叉查找树查询时间复杂度退化为O(n)，如何解决这个问题就需要二叉树的自平衡了，二叉查找树的平衡方式有多种，比如红黑树、AVL树、树堆，后面会一一讲解这些特殊的树，尤其是红黑树，毕竟JDK1.8中的HashMap的数据结构采用了链表+红黑树。