一直以来，我都很少使用也避免使用到树和图,总觉得它们神秘而又复杂，但是树在一些运算和查找中也不可避免的要使用到，那么今天我们就鼓起勇气来学习下树，争取在被问到和使用时不再那么怂。
1. 什么是二叉树？
二叉树也是一棵树（这不是废话么，虽说是废话，但这是事实），但它的每个节点最多只有2个儿子（这个才是重点）。
1.1 如何实现
在了解了二叉树的概念后，我们如何定义一颗树的节点？so easy.
// 节点
public class BinaryNode {
// 存放的信息
Object data;
// 左儿子
BinaryNode left;
// 右儿子
BinaryNode right;
}
1.2 三种遍历算法
构造完树之后，不可避免的就是读取（或者叫做遍历，不然存储成这样干哈啊）。
遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。
由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。
对于树的遍历，按照访问根节点的次序不同，主要有以下三种遍历算法：
- 先序遍历
- 后序遍历
- 中序遍历
除了上面三种遍历，我们还会带大家学习下深度优先遍历和广度优先遍历。
我们首先给出一个假设：
L:左子树
D:根
R:右子树
1.2.1 先序遍历（DLR）
先序遍历：根节点->左子树->右子树
算法的简单实现如下：
public static void DLR(BinaryNode node) {
// 访问根节点
System.out.print(node.data + " ");
// 遍历左子树
if (node.left != null) {
DLR(node.left);
}
// 遍历右子树
if (node.right != null) {
DLR(node.right);
}
}
1.2.2 后序遍历（LRD）
后序遍历：左子树->右子树->根节点
public static void LRD(BinaryNode node) {
// 遍历左子树
if (node.left != null) {
LRD(node.left);
}
// 遍历右子树
if (node.right != null) {
LRD(node.right);
}
// 访问根节点
System.out.print(node.data + " ");
}
1.2.3 中序遍历（LDR）
中序遍历：左子树->根节点->右子树
public static void LDR(BinaryNode node) {
// 遍历左子树
if (node.left != null) {
LDR(node.left);
}
// 访问根节点
System.out.print(node.data + "");
// 遍历右子树
if (node.right != null) {
LDR(node.right);
}
}
1.2.4 深度优先遍历
英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。
深度优先遍历需要使用到栈这种数据结构，栈具有先进后出的特点。
如上图，我们来分析下深度优先遍历的过程。
- 首先根节点A入栈，stack（A）。
- 将A节点弹出，因为A存在 B C两个子节点，根据定义和栈特点，首先将C(右儿子)压入栈中，然后将B（左儿子）压入栈中，stack(C B)
- 弹出栈顶元素B节点弹出，将节点 E 和 D压入栈中，stack（C E D）。
- 弹出栈顶元素D，由于节点D只存在一个子节点H，因此H直接入栈，stack(C E H).
- 弹出栈顶元素H，元素H不存在子元素，stack(C E).
- 弹出栈顶元素E，元素E不存在子元素，stack(C).
- 弹出栈顶元素C，子节点G F分别入栈，stack(G F).
- F出栈，stack(G)。
- G出栈,stack()。
- 遍历结束。
深度优先遍历的结果为： A B D H E C F G.
通过上面的分析，是不是觉得深度优先遍历其实也没那么难啊，下面我们来动手实现这段代码（过程理解清楚了，代码实现起来很简单）。
private void depthFirst(AVLTreeNode<T> node) {
if (node == null) {
return;
}
Stack<AVLTreeNode> stack = new Stack<>();
// 根节点入栈，然后进行后续操作
stack.push(node);
while (!stack.isEmpty()) {
AVLTreeNode root = stack.pop();
// 弹出栈顶元素，进行访问。
System.out.println(root.key + " ");
// 首先将右节点入栈
if (root.right != null) {
stack.push(node.right);
}
// 然后左节点入栈
if (root.left != null) {
stack.push(node.left);
}
}
}
1.2.5 广度优先遍历
英文缩写为BFS即Breadth FirstSearch。其过程检验来说是对每一层节点依次访问，访问完一层进入下一层，而且每个节点只能访问一次。对于上面的例子来说，广度优先遍历的 结果是：A,B,C,D,E,F,G,H(假设每层节点从左到右访问)。
广度优先遍历需要使用到队列这种数据结构，队列具有先进先出的特点。
如上图所示，我们来分析广度优先遍历的过程。
- 首先将A节点插入队列中，queue（A）;
- 将A节点弹出，同时将A的子节点B，C插入队列中，此时B在队列首，C在队列尾部，queue（B，C）；
- 将B节点弹出，同时将B的子节点D，E插入队列中，此时C在队列首，E在队列尾部，queue（C，D，E）;
- 将C节点弹出，同时将C的子节点F，G插入队列中，此时D在队列首，G在队列尾部，queue（D，E，F，G）；
- 将D节点弹出，同时将D节点的子节点H插入队列中，此时E在队列首，H在队列尾部，queue（E，F，G，H）；
- E F G H分别弹出（这四个节点均不存在子节点）。
广度优先遍历结果为：A B C D E F G H
动手来实现广度优先遍历，代码如下：
public void breadthFirst() {
breadthFirst(root);
}
private void breadthFirst(AVLTreeNode<T> node) {
if (node == null) {
return;
}
Queue<AVLTreeNode> queue = new ArrayDeque<>();
// 根节点入栈
queue.add(node);
while (!queue.isEmpty()) {
AVLTreeNode root = queue.poll();
System.out.print(node.key + " ");
if (root.left != null) {
queue.add(node.left);
}
if (root.right != null) {
queue.add(node.right);
}
}
}
1.3 示例
光说不练假把式，本章节我们来举个简单的例子来实战下。
1.3.1 构造一棵树
以上图表达式二叉树为例，我们来看下1.2章节三个遍历算法的输出结果：
先序遍历：+ + a * b c * + * d e f g
中序遍历：a + b * c + d * e + f * g
后序遍历：a b c * + d e * f + g * +
1.3.2 根据表达式构造树
现在假如我们拿到了一个后缀表达式的输入：a b c * + d e * f + g * + ，那么如何根据它来构造树呢？
我们前面已经分析了后序遍历算法（LRD），其实这就是一个逆序的过程。
我们一次一个符号读入表达式，如果符号为操作数，那么我们就新建一个节点并入栈；如果符号为操作符，我们就从栈中弹出两个操作数T1和T2（T1先弹出）并形成一棵新的树，该树的根就是操作符，它的左右子树分别为T2和T1，然后将该树压入栈中。
现在输入为：a b + c d e + * *
很明显前两个为操作数，因此创建两个节点并将它们压入栈中。
接着'+'被读取，因此两棵树被弹出，一颗新的树形成，并被压入栈中。
然后，c、d、e分别被读入，在每个节点被创建后，被压入栈中。
然后'+'被读入，因此我们弹出两个节点形成一棵新的树并压入栈中。
继续读取，‘*’被读入，我们弹出两颗树形成一棵新的树并压入栈中。
最后，读入最后一个符号，两颗树合并，最后的树留在栈中。
下面，我们将上面的分析过程转换为代码：
public static BinaryNode buildTreeFromLRD(String content) {
Stack<BinaryNode> stack = new Stack();
char[] chars = content.toCharArray();
for (int index = 0; index < chars.length; index++) {
char data = chars[index];
if (data >= 'a' && data <= 'z') {
BinaryNode numNode = new BinaryNode();
numNode.data = String.valueOf(data);
stack.push(numNode);
} else {
BinaryNode root = new BinaryNode();
root.data = String.valueOf(data);
root.right = stack.pop();
root.left = stack.pop();
stack.push(root);
}
}
return stack.pop();
}
1.3.3 求表达式的值
求表达式的值是我们学习中或者面试中一个不可避免的知识点,本章节就结合二叉树的遍历，教你如何轻松实现表达式求值。
我们的输入一般为中缀表达式（我们二叉树中序遍历的结果），由于表达式可能存在（），因此可能会出现优先级的问题。而如果将其转换为后缀表达式，则无需考虑运算符优先级的问题。
因此本章节讲解两个部分的内容：
- 将包含（）的中缀表达式转换为后缀表达式
- 求解后缀表达的值
1.3.3.1 中缀->后缀
中缀表达式转换为后缀表达式时，主要使用栈这种结构，并根据一定的规则进行处理。
中缀表达式示例：a + b * c + ( d * e + f ) * g
期望的后缀表达式：a b c * + d e * f + g * +
我们使用op栈来存储操作符，使用re栈来存储操作数。
中缀表达式转换为后缀表达式最为重要的就遇到一个操作数或者运算符的时候应该怎么处理， 也就是优先级的确认。
遇到操作数的时候直接推进re栈。
遇到运算符的时候，需要比较该运算符与op栈头元素的运算符的优先级，如果该运算符优先级高于栈顶运算符（不包括等于）则将该运算符推进op， 否则弹出op栈的头元素直到头元素运算符的优先级低于该运算符，最后将该运算符推进op中。
当然有特殊情况，也就是遇到左括号“（”的时候直接推进op， 当其他运算符与左括号比较优先级的时候可认为左括号的优先级最低。遇到右括号的时候，不断弹出栈的头元素直到遇到左括号，左括号弹出后不入re栈（后缀表达式不需要括号）。
接下来我们详细讨论每种情况：
“+”：优先级是最低的，几乎所有运算符都要弹出（包括加号自身），除了左括号。
“-”：与加号优先级相同，同上。
“*”：优先级稍高，只有遇到乘号，除号，以及幂号的时候才需要弹出。
“/”：与乘号优先级相同，同上。
“^”:优先级最高，只有遇到它自身的时候才需要弹出。
首先符号a被读入，它被存入re栈；然后‘+’被读入并被放入op栈中；接下来b读入并流向re栈。
op栈：+
re栈：a b‘ * ’被读入，因为op栈栈顶元素[+]优先级比[ * ]低，因此re栈无输出，且*入op栈。
op栈：+ *
re栈：a b c‘+’被读入。因为[+]优先级低于op栈栈顶元素[ * ],因此将[ * ]号从op栈弹出并输出到re栈；现在op栈剩下了[+],由于读入的[+]不比op栈中的[+]优先级低而是具备相同的优先级，因此弹出op栈中的[+]并输出到re栈，并将读取到的[+]输入到op栈。
op栈：+
re栈：a b c * +‘（’被读入。直接输入到op栈中。
op栈：+ (
re栈：a b c * +d被读入。直接将d输出到re栈中。
op栈：+ (
re栈：a b c * + d‘*’被读入。由于除非在处理闭括号否则开括号不会从栈中弹出，因此[ * ]直接输出到op栈。
op栈：+ ( *
re栈：a b c * + d‘+’被读入。比较优先级'+'<' * ',‘ * ’从op栈弹出输出至re栈，‘+’栈输出至op栈。
op栈：+ ( +
re栈：a b c * + d *f被读入。直接将f输出到re栈中。
op栈：+ ( +
re栈：a b c * + d * f‘）’被读入。遇到了），因此将op栈中元素弹出，直到最近的（弹出。
op栈：+
re栈：a b c * + d * f +' * '被读入。' * '>'+',*号直接入op栈。
op栈：+ *
re栈：a b c * + d * f +g被读入。直接将g输出到re栈。
op栈：+ *
re栈：a b c * + d * f + g表达式已经读取完毕，将op栈中的元素出栈，并输出到re栈中。
op栈：
re栈：a b c * + d * f + g * +
过程已经清楚了，那么下面让我们动手来实现这个转换过程。（只处理了简单的加减乘除和（）的情况）
/**
* 将中缀表达式转换为后缀表达式
*
* @param midStat 中缀表达式
* @return 转换后的后缀表达式
*/
public static String convertMid2Suffix(String midStat) {
Stack<Character> op = new Stack<>();
Stack<Character> re = new Stack<>();
char[] chars = midStat.toCharArray();
for (int index = 0; index < chars.length; index++) {
char data = chars[index];
if (data >= 'a' && data <= 'z' || data >= '0' && data <= '9') {
// 操作数直接进入re栈
re.push(data);
} else {
// 栈为空时，直接入栈
if (op.size() == 0) {
op.push(data);
continue;
}
// 处理运算符优先级
while (op.size() > 0) {
// peek方法只读取，不出栈
Character exist = op.peek();
// 处理特殊情况,读入的为左括号时，直接入op栈
if (data == '(') {
op.push(data);
break;
}
// 读入为右括号时，op出栈输出到re栈，直到最近的左括号弹出为止
if (data == ')') {
if (exist == '(') {
op.pop();
break;
}
re.push(exist);
op.pop();
continue;
}
if (exist == '(') {
op.push(data);
break;
}
int compareResult = compareOp(data, exist);
// 当前读入的运算符大于op栈栈顶的运算符，直接输入到op栈
if (compareResult > 0) {
op.push(data);
break;
}
// 读入运算符与op栈栈顶运算符优先级相同
if (compareResult == 0) {
// op栈栈顶运算符弹出，并输出至re栈中
re.push(exist);
op.pop();
if (op.size() == 0) {
op.push(data);
break;
}
}
if (compareResult < 0) {
// op栈栈顶运算符弹出，并输出至re栈中
re.push(exist);
op.pop();
if (op.size() == 0) {
op.push(data);
break;
}
}
}
}
}
while(op.size()>0){
re.push(op.pop());
}
StringBuilder result = new StringBuilder();
while (re.size() > 0) {
result.append(re.pop());
}
return result.reverse().toString();
}
public static int compareOp(Character left, Character right) {
String pmOp = "-+";
String mdOp = "*/";
if (left == right) {
return 0;
}
if (pmOp.indexOf(left) >= 0 && pmOp.indexOf(right) >= 0) {
return 0;
}
if (mdOp.indexOf(left) >= 0 && mdOp.indexOf(right) >= 0) {
return 0;
}
if (pmOp.indexOf(left) >= 0 && mdOp.indexOf(right) >= 0) {
return -1;
}
if (mdOp.indexOf(left) >= 0 && pmOp.indexOf(right) >= 0) {
return 1;
}
return 0;
}
1.3.3.2 后缀表达式求值
在上个章节，我们详细分析了如何将我们日常见的算术表达式转换为后缀表达式，接下来我们来分析下如何求解后缀表达式的值。
后缀表达式：6 5 2 3 + 8 * + 3 + *
中缀表达式为：6 * ((5+(2+3) * 8)+3)
照例我们来分析下求解的过程：
6523 入栈
re栈：6 5 2 3+读入。此时2 3出栈，进行+运算，并将结果入栈。
re栈：6 5 58读入。
re栈：6 5 5 8*读入。此时5 8出栈，进行 * 运算后将结果入栈。
re栈：6 5 40+读入。此时5 40出栈，进行+运算后入栈。
re栈：6 453读入。
re栈：6 45 3+读入。此时45 3出栈，进行+运算后入栈。
re栈：6 48'*' 入栈。此时6 48 出栈，进行 * 运算后结果入栈。
re栈：288288出栈，运算结束。
让我们动手来实现这段代码吧。
public static Integer computeSuffixStat(String statement) {
Stack<Integer> re = new Stack<>();
char[] chars = statement.toCharArray();
for (int index = 0; index < chars.length; index++) {
char charData = chars[index];
if (charData >= '0' && charData <= '9') {
Integer data = Integer.parseInt(String.valueOf(charData));
re.push(data);
}
if (charData == '+') {
Integer result = re.pop() + re.pop();
re.push(result);
}
if (charData == '-') {
Integer aft = re.pop();
Integer pre = re.pop();
Integer result = pre - aft;
re.push(result);
}
if (charData == '*') {
Integer result = re.pop() * re.pop();
re.push(result);
}
if (charData == '/') {
Integer aft = re.pop();
Integer pre = re.pop();
Integer result = pre / aft;
re.push(result);
}
}
System.out.println(re.pop());
return re.pop();
}
2.2 完全二叉树
定义：若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
完全二叉树有如下特点：
- 只允许最后一层有空缺结点且空缺在右边，即叶子结点只能在层次最大的两层上出现。
- 对任一结点，如果其右子树的深度为j，则其左子树的深度必为j或j+1。 即度为1的点只有1个或0个。
2.2.1 分析
出于简便起见,完全二叉树通常采用数组而不是链表存储,其存储结构如下:
var tree:array[1..n]of longint;{n:integer;n>=1}
对于tree[i]，有如下特点：
（1）若i为奇数且i>1，那么tree的左兄弟为tree[i-1]；
（2）若i为偶数且i<n，那么tree的右兄弟为tree[i+1]；
（3）若i>1，tree的父亲节点为tree[i div 2]；
（4）若2i<=n，那么tree的左孩子为tree[2i]；若2i+1<=n，那么tree的右孩子为tree[2i+1]；
（5）若i>n div 2,那么tree[i]为叶子结点（对应于（3））；
（6）若i<(n-1) div 2.那么tree[i]必有两个孩子（对应于（4））。
（7）满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。
完全二叉树第i层至多有2（i-1）个节点，共i层的完全二叉树最多有2i-1个节点。
2.2.2 满二叉树
除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树。
国内教程定义：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。
满二叉树是一种特俗的完全二叉树。
2.3 ADT-二叉查找树
二叉树的一个重要的应用就是它们在查找中的使用。假设每个节点存储一项数据。
使二叉树成为二叉查找树的性质是：对于二叉树中的每个节点X，它的左子树中所有项的值都小于X中的项，它的右子树中所有项的值大于X中的项。注意，这意味着该树所有的元素可以使用某种一致的方式排序。
二叉查找树的平均深度为O(logN),所以一般不必担心栈空间被用尽，我们一般使用递归来处理查找、删除等操作。
二叉查找树要求所有项均能排序，这就要求我们实现Comparable接口。该接口告诉我们，树中任意两项都可以使用compareTo方法进行比较。
2.3.1 二叉查找树定义
根据二叉查找树的要求，我们首先让BinaryNode实现Comparable接口。
// 树节点
class BinaryNode implements Comparable {
Integer element;
BinaryNode left;
BinaryNode right;
public BinaryNode{
}
public BinaryNode(Integer element, BinaryNode left, BinaryNode right) {
this.element = element;
this.left = left;
this.right = right;
}
@Override
public int compareTo(@NonNull Object o) {
return this.element - (Integer) o;
}
}
下面我们完成对BinarySearchTree的定义（只定义关键轮廓，具体接口后续进行分析）。
public class BinarySearchTree {
//定义树的根节点
BinaryNode root;
public BinarySearchTree() {
this.root = null;
}
public void makeEmpty() {
this.root = null;
}
public boolean isEmpty() {
return this.root == null;
}
// 判断是否包含某个元素
public boolean contains(Integer x) {
//TODO:后续讲解
return false;
}
// 查找最小值
public BinaryNode findMin(){
//TODO:后续讲解
return null;
}
// 查找最大值
public BinaryNode findMax(){
//TODO:后续讲解
return null;
}
// 按照顺序插入值
public void insert(Integer x){
//TODO:后续讲解
}
// 删除某个值
public void remove(Integer x){
//TODO:后续讲解
}
// 打印树
public void printTree(){
//TODO:后续讲解
}
}
2.3.2 contains-查找
如果在树T中包含项X的节点，那么该操作返回true，否则返回false。
树的结构使得这种操作变得非常简单，如果T为空集，直接返回false；否则我们就对T的左子树或右子树进行递归查找，直到找到该项X。
代码实现如下：
/**
* 是否包含某个元素
* @param x 待查找对象
* @return 查找结果
*/
public boolean contains(Integer x) {
// 首次查找从根节点开始
return contains(x,root);
}
private boolean contains(Integer x, BinaryNode node) {
// 根节点为空的情况，不需要再查找
if (node == null) {
return false;
}
// 与当前节点进行比较
int compareResult = x.compareTo(node.element);
// 小于当前节点的值，就递归遍历左子树
if (compareResult < 0) {
return contains(x, node.left);
}
// 大于当前节点的值，就递归遍历右子树
else if (compareResult > 0) {
return contains(x, node.right);
}
// 等于当前节点值，直接返回
else {
return true;
}
}
2.3.3 查找最小值节点
从根开始并且只要有左子树就向左进行，终止点就是最小元素节点。
// 查找最小值
public BinaryNode findMin() {
return findMin(root);
}
private BinaryNode findMin(BinaryNode node) {
// 当前节点为null，直接返回null
if (node == null) {
return null;
}
// 不存在左子树，返回当前节点
if (node.left == null) {
return node;
}
// 递归遍历左子树
return findMin(node.left);
}
2.3.4 查找最大值节点
从根开始并且只要有右子树就向右进行，终止点就是最大元素节点。作为与findMin的对比，findMax方法我们抛弃了常用的递归，使用了常见的while循环来查找。
// 查找最大值
public BinaryNode findMax() {
return findMax(root);
}
private BinaryNode findMax(BinaryNode node) {
if (node != null) {
while (node.right != null) {
node = node.right;
}
}
return node;
}
2.3.5 insert-插入
插入操作在概念上是简单的，为了将X插入树T中，我们像contains一样沿着树查找。
如果找到X，那么我们可以什么都不做，也可以做一些更新操作。
否则，就将X插入到遍历路径上的最后一个节点。
代码实现如下：
public void insert(Integer x) {
root = insert(x, root);
}
// 返回的插入节点的根节点
private BinaryNode insert(Integer x, BinaryNode node) {
// 如果当前节点为null，新建节点返回
if (node == null) {
return new BinaryNode(x, null, null);
}
// 与当前节点比较
int compareResult = x.compareTo(node.element);
// 小于当前节点值，递归插入左子树，并将返回值设置为当前节点的left
if (compareResult < 0) {
node.left = insert(x, node.left);
}
// 大于当前节点值，递归插入右子树，并将返回值设置为当前节点的right
if (compareResult > 0) {
node.right = insert(x, node.right);
}
// 等于当前的值，不做任何处理
if (compareResult == 0) {
// do some update or do noting
}
return node;
}
2.3.6 remove-删除
正如许多数据结构一样，最难的操作是remove,一旦我们发现了要删除的元素，就要考虑几种可能的情况：
- 当待删除的节点为叶子节点时，直接删除。
- 当待删除节点只有一个儿子节点时，把儿子节点代替该节点的位置，然后删除该节点。
- 当待删除的节点有两个儿子节点时，一般的删除策略是用其右子树的最小的数据代替该节点的数据并递归删除那个节点(现在它是空的);因为右子树的最小节点不可能有左儿子，所以第二次Delete要容易。
// 删除某个值
public void remove(Integer x) {
remove(x, root);
}
private BinaryNode remove(Integer x, BinaryNode node) {
if (node == null) {
return null;
}
int compareResult = x.compareTo(node.element);
if (compareResult < 0) {
node.left = remove(x, node.left);
}
if (compareResult > 0) {
node.right = remove(x, node.right);
}
if (compareResult == 0) {
if (node.left != null && node.right != null) {
node.element = findMin(node.right).element;
node.right = remove(node.element, node.right);
} else {
node = (node.left != null) ? node.left : node.right;
}
}
return node;
}
2.4 AVL树
AVL树是高度平衡的而二叉树。它的特点是：AVL树中任何节点的两个子树的高度最大差别为1。
先来明确几个概念：
平衡因子：将二叉树上节点的左子树高度减去右子树高度的值称为该节点的平衡因子BF(Balance Factor)。
最小不平衡子树：距离插入节点最近的，且平衡因子的绝对值大于1的节点为根的子树。
左边二叉树的节点45的BF = 1，插入节点43后，节点45的BF=2。
节点45是距离插入点43最近的BF不在[-1,1]范围内的节点，因此以节点45为根的子树为最小不平衡子树。
2.4.1 AVL树节点实现
public class AVLTreeNode<T extends Comparable> {
// 存储的数据-用于排序
T key;
// 节点高度-用于计算父节点的BF
int height;
// 左儿子 & 右儿子
AVLTreeNode<T> left;
AVLTreeNode<T> right;
public AVLTreeNode() {
}
public AVLTreeNode(T key, AVLTreeNode<T> left, AVLTreeNode<T> right) {
this.key = key;
this.left = left;
this.right = right;
this.height = 0;
}
}
节点的定义还是比较简单的，相对于之前的定义多了一个height属性用于计算父节点的BF。
2.4.2 AVL树定义
public class AVLTree<T extends Comparable> {
// 定义树的根节点
AVLTreeNode<T> root;
public AVLTree() {
root = null;
}
}
我们之定义了一个根节点，后续分析逐渐丰富其该有的操作。
2.4.3 获取树的高度
public int height() {
return height(root);
}
private int height(AVLTreeNode<T> tree) {
if (tree != null){
return tree.height;
}
return 0;
}
本文章将空树的高度定义为0，高度以树的层次为准，根节点的高度为1，依次类推。
2.4.4 AVL失衡调整
如果在AVL树中进行插入或删除节点后，可能导致AVL树失去平衡。这种不平衡可能出现在下面四种情况中：
- 对a的左儿子的左子树进行一次插入。（LL）
- 对a的左儿子的右子树进行一次插入。（LR）
- 对a的右儿子的左子树进行一次插入。（RL）
- 对a的右儿子的右子树进行一次插入。（RR）
其中1、4是关于a点的镜像对称，2、3是关于a点的镜像对称。
第一种情况（1、4）需要通过对树的一次单旋转完成调整。
第二种情况（2、3）需要通过对树的一次双旋转完成调整。
LL旋转
在左子树上插入左孩子导致AVL树失衡,"根的左子树的高度"比"根的右子树的高度"大2。
针对该情况，我们需要进行单右旋转来完成对树的调整。
图中左边是旋转之前的树，右边是旋转之后的树。从中可以发现，旋转之后的树又变成了AVL树，而且该旋转只需要一次即可完成。
对于LL旋转，你可以这样理解为：LL旋转是围绕"失去平衡的AVL根节点"进行的，也就是节点4；而且由于是LL情况，就将节点4进行一次顺时针旋转。
代码实现：
/**
* 进行一次单右旋转
*
* @param node 最小失衡树根节点
*/
private AVLTreeNode<T> rightRotation(AVLTreeNode<T> node) {
AVLTreeNode<T> left = node.left;
node.left = left.right;
left.right = node;
// 更新高度
node.height = Math.max(height(node.left), height(node.right)) + 1;
left.height = Math.max(height(left.left), height(left.right)) + 1;
return left;
}
RR旋转
在右子树插入右孩子导致AVL失衡时，我们需要进行单左旋调整。旋转围绕最小失衡子树的根节点进行。
/**
* 进行一次单左旋转
*
* @param node 最小失衡树根节点
*/
private AVLTreeNode<T> leftRotation(AVLTreeNode<T> node) {
AVLTreeNode<T> right = node.right;
node.right = right.left;
right.left = node;
// 更新高度
node.height = Math.max(height(node.left), height(node.right)) + 1;
right.height = Math.max(height(right.left), height(right.right)) + 1;
return right;
}
RL旋转
“在右子树上插入左孩子导致AVL树失衡",此时我们需要进行先右旋后左旋的调整。
/**
* 先右旋后左旋
*
* @param node 失衡树根节点
* @return 旋转后的根节点
*/
private AVLTreeNode<T> rightLeftRotation(AVLTreeNode<T> node) {
node.right = rightRoation(node.right);
return leftRoation(node);
}
LR旋转
“在左子树上插入右孩子导致AVL树失衡",此时我们需要进行先左旋后右旋的调整。
/**
* 先左旋后右旋
*
* @param node 失衡树根节点
* @return 旋转后的根节点
*/
private AVLTreeNode<T> leftRightRotation(AVLTreeNode<T> node) {
node.left = leftRoation(node.left);
return rightLeftRoation(node);
}
2.4.5 插入
代码实现如下：
public void insert(T key) {
root = insert(root, key);
}
private AVLTreeNode<T> insert(AVLTreeNode<T> root, T key) {
if (root == null) {
root = new AVLTreeNode(key, null, null);
} else {
int cmp = key.compareTo(root.key);
// 插入左子树的情况
if (cmp < 0) {
root.left = insert(root.left, key);
if (height(root.left) - height(root.right) == 2) {
// 情况二：插入到左子树的左孩子节点上，进行右旋
if (key.compareTo(root.left.key) < 0) {
root = rightRoation(root);
}
//情况四：插入到左子树的右孩子节点上，进行先左后右旋转
else {
root = leftRightRoation(root);
}
}
}
// 插入右子树的情况
if (cmp > 0) {
root.right = insert(root.right, key);
if (height(root.right) - height(root.left) == 2) {
// //情况一：插入右子树的右节点，进行左旋
if (key.compareTo(root.right.key) > 0) {
root = leftRoation(root);
}
// 情况三：插入右子树的左节点,进行先右再左旋转
else {
root = rightLeftRoation(root);
}
}
}
if (cmp == 0) {
System.out.println("无法添加相同的节点");
}
}
root.height = Math.max(height(root.left), height(root.right)) + 1;
return root;
}
2.4.6 删除
删除节点也可能导致AVL树的失衡，实际上删除节点和插入节点是一种互逆的操作：
删除右子树的节点导致AVL树失衡时，相当于在左子树插入节点导致AVL树失衡，即情况情况二或情况四。
删除左子树的节点导致AVL树失衡时，相当于在右子树插入节点导致AVL树失衡，即情况情况一或情况三。
另外，AVL树也是一棵二叉排序树，因此在删除节点时也要维护二叉排序树的性质。
代码实现如下：
public AVLTreeNode<T> remove(T key) {
return remove(root, key);
}
private AVLTreeNode<T> remove(AVLTreeNode<T> node, T key) {
if (node != null) {
int cmp = key.compareTo(node.key);
if (cmp == 0) {
if (node.left != null && node.right != null) {
// 左子树比右子树高,在左子树上选择节点进行替换
if (height(node.left) > height(node.right)) {
//使用左子树最大节点来代替被删节点，而删除该最大节点
AVLTreeNode<T> leftMax = findMax(node.left);
node.key = leftMax.key;
remove(node.left, leftMax.key);
}
//在右子树上选择节点进行替换
else {
//使用最小节点来代替被删节点，而删除该最小节点
AVLTreeNode<T> rightMin = findMin(node.right);
node.key = rightMin.key;
remove(node.right, rightMin.key);
}
} else {
AVLTreeNode<T> tmp = node;
node = (node.left != null) ? node.left : node.right;
tmp = null;
}
}
if (cmp > 0) {
node.right = remove(node.right, key);
if (height(node.left) - height(node.right) == 2) {
//相当于在左子树上插入右节点造成的失衡（情况四）
if (height(node.left.right) > height(node.left.left))
node = leftRightRotation(node);
else//相当于在左子树上插入左节点造成的失衡（情况二）
node = rightRotation(node);
}
}
if (cmp < 0) {
node.left = remove(node.left, key);
if (height(node.right) - height(node.left) == 2) {
//相当于在右子树上插入左节点造成的失衡（情况三）
if (height(node.right.left) > height(node.right.right))
node = rightLeftRotation(node);
else//相当于在右子树上插入右节点造成的失衡（情况一）
node = leftRotation(node);
}
}
return node;
}
return null;
}
// 查找最大值
public AVLTreeNode findMax() {
return findMax(root);
}
private AVLTreeNode<T> findMax(AVLTreeNode<T> node) {
if (node != null) {
while (node.right != null) {
node = node.right;
}
}
return node;
}
private AVLTreeNode<T> findMin(AVLTreeNode<T> node) {
// 当前节点为null，直接返回null
if (node == null) {
return null;
}
// 不存在左子树，返回当前节点
if (node.left == null) {
return node;
}
// 递归遍历左子树
return findMin(node.left);
}
