基础知识就像是一座大楼的地基，它决定了我们技术的高度
在面试中，关于树的问题是很多的，例如简单点的会问你关于树的前中后序的遍历顺序是怎样的？难点会让你手写关于树的算法题，又或是在Java后端面试中也会涉及到一些树的知识，例如在HashMap中产生哈希冲突生成的链表到一定条件下为什么要转成红黑树？，为什么要用红黑树而不用B+树呢？在Mysql中索引的存储为什么用B+树而不用其他树等等。其实这些东西我们在日常开发过程中都会用到，其实每个程序员都不甘心每天工作只是CRUD，那么这些数据结构其实就是内功，我们学会了它在日常工作分析问题，选用什么集合，排序怎么排，这些问题中我们会多一些选择。
什么是树
树（英语：tree）是一种抽象数据类型（ADT）或是实现这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>0）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
再完备的定义也没有图直观，我们先来看一下图（这里借用数据结构与算法作者王争老师的图，下面看到类似风格的图都是如此）。
image
我们可以看到这里的树和我们现实生活的树是十分相像的，其中每个元素我们称之为节点，而用直线相连的关系我们称之为父子关系。那么什么才能称之为树呢？
- 每个节点都只有有限个子节点或无子节点
- 没有父节点的节点称为根节点
- 每一个非根节点有且只有一个父节点
- 除了根节点外，每个子节点可以分为多个不相交的子树
- 树里面没有环路
树的分类有很多，但是我们常用的还是二叉树(每个节点最多含有两个子树的树称为二叉树)，下图中所示其实就是二叉树。
image
二叉树中也会有分类，其中上图中②是满二叉树(除了叶子节点以外，每个节点都有左右两个子节点)，上图③是完全二叉树(其它各层的节点数目均已达最大值，最后的所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树)，这里关键点是从左到右排列。那么为什么会有完全二叉树呢？这里涉及到了树的两种存储方式，一种直观的感受就是直接链表存储。Node节点设置左右子节点两个元素。代码如下。
class TreeNode <T>{
public T data;
public TreeNode leftNode;
public TreeNode rightNode;
TreeNode(T data){
this.data = data;
}
}
另一种方式就是基于数组顺序存储，我们把树从根节点开始放入数组下标为1的索引处，接下来一次从左到右放入。
image
| 序号 | 左节点位置 | 右节点位置 |
|---|---|---|
| 1 | 2 | 3 |
| 2 | 4 | 5 |
| 3 | 6 | 7 |
| …… | …… | …… |
| n | 2n | 2n-1 |
这里如果是将根节点放在索引为0的地方开始的话，那么左节点就是2n+1，右节点就是2n+2
依据上面的表格，我们应该能够得到对于每个节点n来说，它的左节点位置就是2n，它的右节点位置就是2n+1。这样我们就能够将完全二叉树存储在数组的结构中去了。如果是非完全二叉树也用数组存储的话，那么数组的中间会产生许多的空洞，造成内存的浪费。
用数组存储数据的优点在于无需向链表那样存储左右子节点的指针，节省空间。
二叉树的遍历
上面我们简单了解了树的定义，接下来我们学习一下二叉树的遍历(前序遍历、中序遍历、后序遍历)，这也是面试中经常被问到的点。
- 前序遍历是指，对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树
- 中序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树
- 后序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身
image
我们用代码表示一下更加直观。
/**
* @Description: 前序遍历
* @Param: [treeNode]
* @return: void
* @Author: hu_pf
* @Date: 2019/11/26
*/
private static void frontOrder(TreeNode<String> treeNode){
if (treeNode == null){
return;
}
System.out.printf(treeNode.data);
frontOrder(treeNode.leftNode);
frontOrder(treeNode.rightNode);
}
/**
* @Description: 中序遍历
* @Param: [treeNode]
* @return: void
* @Author: hu_pf
* @Date: 2019/11/26
*/
private static void middleOrder(TreeNode<String> treeNode){
if (treeNode == null){
return;
}
middleOrder(treeNode.leftNode);
System.out.printf(treeNode.data);
middleOrder(treeNode.rightNode);
}
/**
* @Description: 后序遍历
* @Param: [treeNode]
* @return: void
* @Author: hu_pf
* @Date: 2019/11/26
*/
private static void afterOrder(TreeNode<String> treeNode){
if (treeNode == null){
return;
}
afterOrder(treeNode.leftNode);
afterOrder(treeNode.rightNode);
System.out.printf(treeNode.data);
}
二叉查找树
二叉查找树中，每个节点的值都大于左子树节点的值，小于右子树节点的值
二叉查找树就是动态的支持数据的增删改查，而且还是天然有序的，我们只要通过中序遍历那么的到的数据就是有序的数据了。
二叉查找树的插入
我们只需要从根节点开始，依次比较要插入的数据和节点的关系即可。如果插入的数据比当前节点大，并且其右节点没有数据则放到其右节点上去，如果其右节点有数据，那么久再次遍历其右子树。如果插入数据比当前数据小的话过程类似。
image
用代码表示如下。
private void insertTree(int data){
if (this.rootNode == null){
rootNode = new TreeNode(data);
return;
}
TreeNode<Integer> p = rootNode;
while (p!=null){
Integer pData = p.data;
if (data>=pData){
if (p.rightNode == null){
p.rightNode = new TreeNode(data);
break;
}
p = p.rightNode;
}else {
if (p.leftNode == null){
p.leftNode = new TreeNode(data);
break;
}
p = p.leftNode;
}
}
}
二叉查找树的查找
二叉树的查找的话就比较简单了，拿要找的数据和根节点相比较，如果查找的数据比它小则在左子树进行查找，如果查找的数据比它大则在右子树进行查找。
private TreeNode findTreeNode(int data){
if (this.rootNode == null){
return null;
}
TreeNode<Integer> p = rootNode;
while (p != null){
if (p.data == data) return p;
if (data >= p.data) p = p.rightNode;
else p = p.leftNode;
}
return null;
}
二叉查找树的删除
二叉查找树的删除操作比较复杂，需要考虑三种情况。
- 删除的节点无子节点：直接删除即可
- 删除的节点只有一个节点：父节点的引用换成其子节点即可
- 删除的节点有两个节点：那么我们需要想了，左子节点数据<父节点数据<右子节点数据，此时我们如果删除了父节点的话，那么就需要从左节点或者右节点找到一个节点移动过来占据此位置，并且移动完以后还要保持同样的大小关系，那么移动哪个呢？移动左子节点最大的节点，或者右子节点最小的节点。这里大家需要细细品味一下。为什么要这样移动。
要找到右子节点最小的节点，只要找到右子节点哪个没有左节点就代表那个节点是最小的，相反的如果要找到左子节点最大的节点，只要找到左子节点哪个没有右节点就代表那个节点是最大的。
image
接下来我们看一下删除的代码
private void deleteTreeNode(int data){
if (this.rootNode == null ) return;
TreeNode<Integer> treeNode = rootNode;
TreeNode<Integer> treeNodeParent = null;
while (treeNode != null){
if (treeNode.data == data) break;
treeNodeParent = treeNode;
if (data >= treeNode.data) treeNode = treeNode.rightNode;
else treeNode = treeNode.leftNode;
}
// 没有找到节点
if (treeNode == null) return;
TreeNode<Integer> childNode = null;
// 1. 删除节点没有子节点
if (treeNode.leftNode == null && treeNode.rightNode == null){
childNode = null;
if (treeNodeParent.leftNode == treeNode) treeNodeParent.leftNode = childNode;
else treeNodeParent.rightNode = childNode;
return;
}
// 2. 删除节点只有一个节点
if ((treeNode.leftNode !=null && treeNode.rightNode==null)||(treeNode.leftNode ==null && treeNode.rightNode!=null)){
// 如果此节点是左节点
if (treeNode.leftNode !=null) childNode = treeNode.leftNode;
// 如果此节点是右节点
else childNode = treeNode.rightNode;
if (treeNodeParent.leftNode == treeNode) treeNodeParent.leftNode = childNode;
else treeNodeParent.rightNode = childNode;
return;
}
// 3. 删除的节点有两个子节点都有,这里我们演示的是找到右子节点最小的节点
if (treeNode.leftNode !=null && treeNode.rightNode!=null){
TreeNode<Integer> minNode = treeNode.rightNode;
TreeNode<Integer> minNodeParent = treeNode;
while (minNode.leftNode!=null){
minNodeParent = minNode;
minNode = minNode.leftNode;
}
treeNode.data = minNode.data;
if (minNodeParent.rightNode != minNode) minNodeParent.leftNode = minNode.rightNode;
else minNodeParent.rightNode = minNode.rightNode;
}
}
删除的代码比较复杂，这里还有一个简单的做法，就是将其标记为删除。这样也就无需移动数据，在插入数据的时候判断是否删除即可。但是会比较占用内存。
平衡二叉树——红黑树
平衡二叉树（Balanced Binary Tree）具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
上面我们讲了什么是查找二叉树，那么查找二叉树在一些极端情况下有可能变成一个链表，所以再进行查找的话效率就会变低，而平衡二叉树就是为了解决这个问题出现的，即让整棵树看起来比较均匀，左右子节点的数量大致相同。这样就不会再极端情况下变成链表了。那么通常情况下我们常用的平衡二叉树就是红黑树。
image
这里我不讲解红黑树实现的代码，因为实在是太麻烦了，大概说一下他在Java后端的应用场景。Java的HashMap的结构其实是数组加链表的结构，如果一个槽的链表过多的话也会影响性，所以当链表长度为8的时候就会自动转换为红黑树，以增加查询性能。接下来我会结合我自身面试的情况给大家说一下红黑树在面试中经常被问到的点。
-
HashMap什么时候后会将链表转换为红黑树？链表长度为8的情况 - 在什么情况下红黑树会转换为链表?红黑树的节点为6的时候
- 为什么链表要转换为红黑树？答出链表查询性能不好即可
- 为什么不用其他的树？关键点，平衡树，答出红黑树的优点即可
- 为什么不用
B+树？关键点，磁盘，内存。红黑树多用在内部排序，即全放在内存中的。B+树多用于外存上时，B+树也被称之为一个磁盘友好的数据结构
正常情况在面试中面试官是不会让你手写红黑树之类的，我在面试中大概碰到的就上面几个，只要答出红黑树的优点以及应用场景差不多就够了。
关于树的排序
是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。
在面试中其实也会经常碰到一些排序的算法，例如堆排序或者堆排序的一些应用例如前求TopN的数据。其实堆的结构也是树。堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
image
其中第 1 个和第 2 个是大顶堆，第 3 个是小顶堆，第 4 个不是堆。既然堆本质上是一个完全二叉树，那么我们完全可以用数组来存堆的数据。那么当前节点是n的话，其左子节点就是2n，其右子节点就是2n+1。
class Heap{
// 存放堆中的数据，用数组来装
private int [] a;
// 堆中能存放的最大数
private int n;
// 堆中已经存放的数量
private int count;
public Heap(int capacity){
a = new int [capacity + 1];
this.n = capacity;
count = 0;
}
}
如何在堆中插入数据
接下来我们如何动态的将数据插入到堆中呢？
image
例如我们上图中的在堆中插入元素22，那么此时应该怎么做来保持他仍是一个堆呢？此时我们上图中演示的大顶堆，那么就要保证大顶堆的概念要求，每个节点的值都大于等于其左右子节点的值。那么我们将其放入到数组最后一个位置，然后和它的父节点（n/2就是他的父节点）进行比较，如果大于它的父节点，就和父节点调换位置，继续和其父节点比较，直到它小于其父节点就停止。代码实现如下。
public void insert(int data){
if (count >= n) return;
count++;
// 把数据放到数组中
a[count] = data;
int index = count;
// 开始进行比较，先判断跳出条件
// 1. 首先能想到的是插入的数据满足了大（小）顶堆的数据要求
// 2. 加上极值条件，及是一颗空树情况
while (index/2>0 && a[index]>a[index/2]){
swap(a,index,index/2);
index = index/2;
}
}
private void swap(int [] a, int i , int j){
int swap = a[i];
a[i] = a[j];
a[j] = swap;
}
如何删除堆顶元素
我们直到大小顶堆的根节点值是最大的或者最小的。那么如果删除了堆顶元素，接下来就要从左右子节点选个最大或者最小的放入到根节点，然后以此类推。那么我们按照我们刚才分析的如果进行移动的话，可能会产生数组的空洞。
image
我们可以将根节点移除以后，然后再将数组最后的值给移到根节点，然后再进行依次比较换位置，这样就不会产生数组空洞了。
image
代码如下
public void removeMax(){
if (count == 0) return;
// 将最后的元素移动到堆顶
a[1] = a[count];
count--;
heapify(a,count,1);
}
private void heapify(int [] a,int n,int i){
// 定义什么时候结束，当前节点与其左右子节点进行比对，如果当前节点是最大的则跳出循环（代表当前节点已经是最大的）
while (true){
int maxIndex = i;
// 找到三个节点中最大节点的索引值
if (2*i<= n && a[i]<a[2*i]) maxIndex = 2*i; // 判断当前节点,是否小于左节点
if (2*i+1<= n && a[maxIndex]<a[2*i+1]) maxIndex = 2*i+1;// 判断最大节点是否小于右节点
// 如果当前节点已经是最大节点就停止交换并停止循环
if (maxIndex == i )break;
// 找到中最大值的位置，并交换位置
swap(a,i,maxIndex);
i = maxIndex;
}
}
堆排序
我们对于传进来一个无序的数组如何利用堆来进行排序呢。那么既然是利用堆来排序，那么我们第一步肯定是先将此数组变成一个堆结构。
建堆
如何将一个无序的数组变成一个堆结构呢？第一种我们很容易就能想到的就是依次调用我们上面的插入的方法，但是这样所用的内存会加倍，即我们会新建一个内存进行存储这个堆。那么如果我们想无需新增内存直接再原有的数组将其变成堆，该如何做呢？
image
这里数组是不是堆，那么如何将其变成堆呢？这里我们采用从下往上建堆的方法，什么意思呢？其实就是递归的思想，我们先将下面的建好堆，然后依次往上传递。我们先堆化标号为4的树，然后再堆化标号为3的，然后堆化标号为2的，然后堆化标号为1的。依次进行。到最后我们就得到了一个堆。下图中画圆圈代表了其堆化的树的范围。代码如下
image
public void buildHeap(int[] a,int n){
for (int i =n/2;i>=1;i--){
heapify(a,n,i);
}
}
private void heapify(int [] a,int n,int i){
// 定义什么时候结束，当前节点与其左右子节点进行比对，如果当前节点是最大的则跳出循环（代表当前节点已经是最大的）
while (true){
int maxIndex = i;
// 找到三个节点中最大节点的索引值
if (2*i<= n && a[i]<a[2*i]) maxIndex = 2*i; // 判断当前节点,是否小于左节点
if (2*i+1<= n && a[maxIndex]<a[2*i+1]) maxIndex = 2*i+1;// 判断最大节点是否小于右节点
// 如果当前节点已经是最大节点就停止交换并停止循环
if (maxIndex == i )break;
// 找到中最大值的位置，并交换位置
swap(a,i,maxIndex);
i = maxIndex;
}
}
排序
排序的话就简单了，因为堆的根节点是最大或者最小的元素，所以第一种我们依然能够想到的是直接将其根节点的值拿出来后放到另一个数组，然后删掉堆顶元素，然后再拿掉堆顶元素，然后再删除依次类推。这样有一个缺点还是占用内存，因为我们又重新定义了一个数组，那么有没有办法不占用内存，直接在原有的数组中进行排序呢？
第二种办法就是不需要借助另一个数组，怎么做呢？这个过程优点类似于删除堆顶元素，不同的是删除堆顶元素我们直接堆顶元素丢弃了，而排序的话我们需要将堆顶元素和最后一个元素进行互换，互换完以后然后再将其堆化，然后再将堆顶元素与最后一个元素的前一个元素互换，然后再堆化，以此类推。
image
如何求前TopN的数据
相信微博大家都用，那么其中的前十热搜是如何实时的显现呢？其实求前TopN的数据用到的基本上都是堆，我们可以建立一个大小为N的小顶堆，如果是静态数据的话，那么就依次从数组中取出元素与小顶堆的堆顶元素进行对比，如果比堆顶元素大，那么就丢弃堆顶元素，然后将数组中元素放入到堆顶，然后堆化。依次进行，最后得到的就是TopN大的数据了。如果是动态数据的话和静态数据也一样，也是进行不断的进行比对。最后如果想要TopN大的数据直接将此堆返回即可。
接下来我用动图演示一下是怎么求得的TopN数据。
数组为: 1 2 3 9 6 5 4 3 2 10 15
求得Top5
image
本文代码地址
有感兴趣的可以关注一下我新建的公众号，搜索[程序猿的百宝袋]。或者直接扫下面的码也行。
image
网友评论