树形结构是一种非常重要的非线性的数据结构。树结构与线性结构不同之处：线性结构中任意一个元素最多只有一个后继元素，而树形结构中每个元素可以有多个后继；线性结构和树形结构中每个元素最多只有一个前驱元素。这篇文章为本人原创，谢绝转载。具体的内容目录如下：
一、树的属性
二、二叉树
三、二叉树与树、森林的转换
四、二叉排序树
五、平衡二叉树
一、树的属性
树又一个特定的称为根的节点，这个节点无前驱节点。树可以用递归的方式来定义，也就是说树是由若干个子树构成。如下图所示，A是根节点，没有前驱节点，B、C是A的子节点，也是一棵树。这里要简单说下树的一些术语。
1.节点：表示树中的一个数据元素。如下图中，A、B、C、D、E、F、G、H、I都是是节点。
2.孩子节点：表示树中节点的直接后驱节点。如下图中，A的孩子节点为B、C。
3.双亲节点：表示树中节点的直接前驱节点，如下图中，D、E、F的双亲节点是B。
4.兄弟节点：表示具有相同双亲节点的节点。如下图中，D、E、F是兄弟节点。
5.祖先节点：表示从根节点到该节点的双亲节点都是祖先节点。如下图中，I的祖先节点为A、B、E。
6.子孙节点：表示该节点下所有孩子节点，包括子节点的子节点。如下图中，A的子孙节点为B、C、D、E、F、G、H、I。
7.节点的度：该节点的子树的个数，可以理解为该节点后代的代数。如下图中，A的度为3，D的度为0。
8.叶子节点：度为0的节点，也就是没有后驱节点。如下图中，D、H、I、G都是叶子节点。
9.分支节点：度不为0的节点，可以理解为树枝，有后驱节点。B、C、E都是分支节点。
10.树的层数：树的根节点所在的层树为1，其他节点的层数等于他的双亲节点的层数+1。如下图中，A树的层数为4，B树的层数为3。
11.树的深度：表示整棵树的最大层数，也叫高度。如下图中，深度为4。
12.森林：零棵树或有限棵树互不相交的树的集合叫森林。如下图中，将A节点去掉，B树与C树可以构成森林。
13.有序树与无序树：树中节点的子树从左到右是有次序的称为有序树，否则为无序树。
二、二叉树
二叉树是一颗每个节点有不超过两个孩子节点的树。两颗子树有左右之分，称为左子树和右子树，左子树和右子树都可以为空，如果不为空时，子树也是一颗二叉树。二叉树也有一种递归的概念。二叉树有五种基本形态
1.空树：根节点为空的二叉树
2.只有根节点：只有根节点，根节点没有左右子树
3.只有左子树：只有左子树，没有右子树
4.只有右子树：只有右子树，没有左子树
5.有左右子树：该节点同时有左右子树
二叉树的性质
1.二叉树第i(i>=1)层上最多有2^(i-1)个节点。
2.深度为k(k>=1)的二叉树最陡有2^k-1个节点。
3.满二叉树：深度为k并且含有2k-1个节点的二叉树。可以理解为，树枝节点都有左右子树。通俗地讲，在不增加树的深度的前提下，无法再多添加一个节点的二叉树称为满二叉树。
4.完全二叉树：深度为k，有n个节点的二叉树，当且仅当每个节点的编号与相应满二叉树节点顺序编号从1～n相对应时，则称为完全二叉树。通俗地讲，完全二叉树相当于删除满二叉树的最底层最右边的连续若干个节点。
二叉树的存储结构
1.顺序存储结构
将二叉树中所有节点元素存储到一维数组中，这是最简单的顺序存储结构。设一维数组list，list[0]空置不用，从第一个开始，每个数组元素存储树的每一个节点元素。按照完全二叉树编号从上到下，从左到右的顺序将每个节点元素存储到数组中。如下图所示，第i个节点的双亲节点为i/2，左右孩子节点分别为2i、2i+1。
如果二叉树是一颗单边二叉树(只有左子树或只有右子树)，对于每个二叉树而言，有插入新元素的可以，所以需要保留存储空间。如下图中，红色表示可以插入新元素，用虚线连接。
下图表示单边二叉树的顺序存储结构，本来只有四个元素，却要分配8个存储空间。如果一颗深度为k的单边二叉树，至少要
2^k个存储空间，则有2^k-k个空间为空，这样造成资源浪费。这种存储结构适合于满二叉树和完全二叉树，一般的二叉树很少采用这种存储结构。
2.链表存储结构
二叉树的链表结构有常见的两种：二叉链表、三叉链表。
- 二叉链表：包含一个数据元素，左子树指针，右子树指针。可以很容易找到该节点的子孙节点，但是不容易找到其双亲节点。
-
三叉链表：包含一个数据元素，左子树指针，右子树指针，还有一个双亲节点指针，方便找出其双亲节点。
存储结构
一般树的存储结构
1.双亲表示法：存储父节点的序号，方便于查找父节点。下图中的左边为一般的树形结构，右边为存储结构。
2.孩子表示法：存储孩子节点的指针，方便于查找孩子节点。下图中的左边为一般的树形结构，右边为存储结构。
3.双亲孩子表示法：结合上述两种方式。可方便查找双亲和孩子节点。
4.二叉树表示法：将一个普通树转换为二叉树，具体规则如下：
-左指针域指向该节点的第一个子节点；
-右指针域指向该节点的第一个兄弟节点；
二叉树的遍历
遍历二叉树就是以一定的顺序访问每个节点，并且每个节点只能被访问一次。
假设有一颗二叉树有7个节点，为了方便理解，为每个没有同时存在左右子树的节点补充一个空的节点。如下图所示，图中的红色表示补充的空的节点，外围虚线表示搜索路径。
按照从左到右的方式，可以分为三种遍历方式
注意：递归算法实现简单，但效率较低，这是因为系统需要维护一个工作栈以保证递归方法的正确执行，所有在实际使用中推荐非递归方式。
1.先序遍历：先访问根节点，再访问左子树，再访问右子树。如上图中，第一次搜索经过的节点为A、B、D、G、C、E、F。具体的算法如下：
/**
* 二叉树的先序遍历(非递归)
* @param root 根节点
*/
public static void fristOrderTraversalByStack(WLTreeNode root) {
Stack<WLTreeNode> stack = new Stack<>();
WLTreeNode node = root;
//将所有左孩子压栈
while (node != null || stack.size() > 0) {
if(node != null) {
printTreeNode(node);
stack.push(node);
node = node.getLeft();
}else {
node = stack.pop();
node = node.getRight();
}
}
}
/**
* 二叉树的先序遍历
* @param root 根节点
*/
public static void firstOrderTraversal(WLTreeNode root) {
if(root != null) {
printTreeNode(root);
if(root.getLeft() != null) {
firstOrderTraversal(root.getLeft());
}
if(root.getRight() != null) {
firstOrderTraversal(root.getRight());
}
}
}
2.中序遍历：先访问左子树，再访问根节点，再访问右子树。如上图中，第二次搜索经过的节点为G、D、B、A、E、C、F。具体的算法如下：
/**
* 二叉树的中序遍历(非递归)
* @param root 根节点
*/
public static void inOrderTraversalByStack(WLTreeNode root) {
Stack<WLTreeNode> stack = new Stack<>();
WLTreeNode node = root;
while (node != null || stack.size() > 0) {
if(node != null) {
stack.push(node);
node = node.getLeft();
}else {
node = stack.pop();
printTreeNode(node);
node = node.getRight();
}
}
}
/**
* 二叉树的中序遍历
* @param root 根节点
*/
public static void inOrderTraversal(WLTreeNode root) {
if(root != null) {
if(root.getLeft() != null) {
inOrderTraversal(root.getLeft());
}
printTreeNode(root);
if(root.getRight() != null) {
inOrderTraversal(root.getRight());
}
}
}
3.后序遍历：先访问左子树，在访问右子树，在访问根节点。如上图中，第三次搜索经过的节点为G、D、B、E、F、C、A。具体的算法如下：
/**
* 二叉树的后序遍历(非递归)
* @param root 根节点
*/
public static void postOrderTraversalByStack(WLTreeNode root) {
Stack<WLTreeNode> stack = new Stack<>();
Stack<WLTreeNode> output = new Stack<>();
WLTreeNode node = root;
while (node != null || stack.size() > 0) {
if(node != null) {
stack.push(node);
output.push(node);
node = node.getRight();
}else {
node = stack.pop();
node = node.getLeft();
}
}
while (output.size() > 0) {
printTreeNode(output.pop());
}
}
/**
* 二叉树的后序遍历
* @param root 根节点
*/
public static void postOrderTraversal(WLTreeNode root) {
if(root != null) {
if(root.getLeft() != null) {
postOrderTraversal(root.getLeft());
}
if(root.getRight() != null) {
postOrderTraversal(root.getRight());
}
printTreeNode(root);
}
}
二叉树的其他操作
/**
* 按层遍历二叉树
* 1.将二叉树根节点入队列
* 2.将队头节点出队列，并判断此节点算法有左右孩子，如果有，则将其左右孩子入队列
* @param root 根节点
*/
public static void levelTraversal(WLTreeNode root) {
if(root != null) {
List<WLTreeNode> list = new ArrayList<>();
//1.根节点入队列
list.add(root);
while (list.size() > 0) {
//取出队头节点
WLTreeNode node = list.get(0);
printTreeNode(node);
list.remove(0);
//判断是否有左右孩子
if(node.getLeft() != null) {
list.add(node.getLeft());
}
if(node.getRight() != null) {
list.add(node.getRight());
}
}
}
}
/**
* 按层遍历二叉树
* @param root 根节点
* @param index 第几个节点，从0开始
* @return 节点
*/
public static WLTreeNode findNodeByIndex(WLTreeNode root,int index) {
if(root != null && index >= 0) {
List<WLTreeNode> list = new ArrayList<>();
//根节点入队列
list.add(root);
while (list.size() > 0) {
//取出队头节点
WLTreeNode node = list.get(0);
//==0，则找到
if(index == 0) {
return node;
}
//弹出队头节点
list.remove(0);
index --;
//如果该节点有左右节点，则入队列
if(node.getLeft() != null) {
list.add(node.getLeft());
}
if(node.getRight() != null) {
list.add(node.getRight());
}
}
}
return null;
}
/**
* 二叉树的深度
* @param root 根节点
* @return 深度值 根节点深度为1
*/
public static int depthOfBinaryTree(WLTreeNode root) {
if(root != null) {
if(root.getLeft() == null && root.getRight() == null) {
return 1;
}
int leftDepth = depthOfBinaryTree(root.getLeft());
int rightDepth = depthOfBinaryTree(root.getRight());
return Math.max(leftDepth, rightDepth)+1;
}
return 0;
}
/**
* 二叉树的宽度是指二叉树各层结点个数的最大值
* @param root 根节点
* @return 深度值 根节点深度为1
*/
public static int widthOfBinaryTree(WLTreeNode root) {
if(root != null) {
List<WLTreeNode>list = new ArrayList<>();
list.add(root);
int maxWidth = 1;//已有根节点
int curWidth = 0;
while (list.size() > 0) {
curWidth = list.size();
if(maxWidth < curWidth) {
maxWidth = curWidth;
}
for (int i = 0; i < curWidth; i++) {
WLTreeNode node = list.get(0);
list.remove(0);
if(node.getLeft() != null) {
list.add(node.getLeft());
}
if(node.getRight() != null) {
list.add(node.getRight());
}
}
}
return maxWidth;
}
return 0;
}
/**
* 二叉树的节点个数
* @param root 根节点
* @return 全部节点个数
*/
public static int numberOfBinaryTree(WLTreeNode root) {
if(root != null) {
int count = 0;
List<WLTreeNode>list = new ArrayList<>();
list.add(root);
while (list.size() > 0) {
WLTreeNode node = list.get(0);
list.remove(0);
if(node.getLeft() != null) {
list.add(node.getLeft());
}
if(node.getRight() != null) {
list.add(node.getRight());
}
count++;
}
return count;
}
return 0;
}
/**
* 二叉树某一层的全部节点个数
* @param root 根节点
* @return 节点个数
*/
public static int numberOfNodeOnLevel(WLTreeNode root,int level) {
if(root != null && level >= 0) {
//根节点只有一个节点
if(level == 1) {
return 1;
}
return numberOfNodeOnLevel(root.getLeft(), level-1) + numberOfNodeOnLevel(root.getRight(), level-1);
}
return 0;
}
/**
* 二叉树的叶子节点个数
* @param root 根节点
* @return
*/
public static int numberOfLeafNode(WLTreeNode root) {
if(root != null) {
if(root.getLeft() == null && root.getRight() == null) {
return 1;
}
return numberOfLeafNode(root.getLeft()) + numberOfLeafNode(root.getRight());
}
return 0;
}
/**
* 二叉树中某个节点到根节点的路径
* 1.将根节点压入栈，再从左子树中查找，如果没找到，再从右子树中查找，如果没找到，则弹出根节点，再遍历栈中上一个节点
* 2.如果找到，则栈中存放的节点就是路径经过的节点
* @param root 根节点
* @param node 起点节点
* @return 路径数组
*/
public static List<WLTreeNode> pathOfTreeNode(WLTreeNode root,WLTreeNode node){
List<WLTreeNode>list = new ArrayList<>();
boolean isFound = isFoundTreeNode(root, node, list);
System.out.println("isFound = "+isFound);
return list;
}
/**
* 查找二叉树中是否包含该节点
* @param root 根节点
* @param node 待查找节点
* @param list 路径数组
* @return 是否找到
*/
public static boolean isFoundTreeNode(WLTreeNode root,WLTreeNode node,List<WLTreeNode>list) {
if(root == null || node == null) {
return false;
}
//判断是否为当前节点
if(root.getValue() == node.getValue()) {
return true;
}
System.out.println("find root value = "+root.getValue());
//将根节点压入栈
list.add(root);
//先从左子树中查找
boolean isFound = isFoundTreeNode(root.getLeft(),node,list);
if(!isFound) {
//左子树中没找到，则从右子树中查找
isFound = isFoundTreeNode(root.getRight(),node,list);
}
//左右子树中都没找到，则弹出此根节点
if(!isFound) {
list.remove(list.size()-1);
}
return isFound;
}
/**
* 是否为满二叉树
* 除了叶子节点，每个节点都有左右子节点
* @param root 根节点
* @return
*/
public static boolean isFullBinaryTree(WLTreeNode root) {
if(root != null) {
int depth = depthOfBinaryTree(root);
int nodeCount = numberOfBinaryTree(root);
if(nodeCount == Math.pow(2, depth)-1) {
return true;
}
}
return false;
}
/**
* 是否为平衡二叉树
* 定义：一颗空树或左右子树的高度差的绝对值不超过1，并且左右子树都是一个平衡二叉树
* @param root 根节点
* @return
*/
public static boolean isAVLBinaryTree(WLTreeNode root) {
//一颗空树
if(root == null) {
avlHeight = 0;
return false;
}
//只有根节点
if(root.getLeft() == null && root.getRight() == null) {
avlHeight = 1;
return true;
}
boolean isLeft = isAVLBinaryTree(root.getLeft());
int leftHeight = avlHeight;
boolean isRight = isAVLBinaryTree(root.getRight());
int rightHeight = avlHeight;
avlHeight = Math.max(leftHeight, rightHeight);
if(isLeft && isRight && Math.abs(leftHeight-rightHeight) <= 1) {
return true;
}
return false;
}
/**
* 反转二叉树 非递归
* @param root
* @return
*/
public static WLTreeNode invertBinaryTreeByQueue(WLTreeNode root) {
if(root == null) {
return root;
}
List<WLTreeNode>list = new ArrayList<>();
list.add(root);
while (list.size() > 0) {
WLTreeNode node = list.get(0);
list.remove(0);
WLTreeNode tmpNode = node.getLeft();
node.setLeft(node.getRight());
node.setRight(tmpNode);
if(node.left != null) {
list.add(node.getLeft());
}
if(node.right != null) {
list.add(node.getRight());
}
}
return root;
}
/**
* 打印树形结构
*/
private static void printTreeNode(WLTreeNode node) {
System.out.println(node.getValue());
}
三、二叉树与树、森林的转换
1.树转换为二叉树
(1)加线：在树中所有相邻的兄弟节点之间加一条线。
(2)抹线：对树中的每个节点，只保留与第一个孩子节点之间的连线，删除与其他孩子节点之间的连线。
(3)调整：以每个节点为轴心，将其右侧所有节点按顺时针转动45度，使之称为一颗二叉树。
2.二叉树转换为树
树与二叉树之间的转换是可逆的，将二叉树转换为树也分为三步：
(1)加线：若某个节点是其双亲节点的左孩子，则把该节点的所有右子孙节点都与该节点的双亲节点用线连起来。
(2)抹线：删除二叉树中所有双亲节点与右孩子节点之间的连线。
(3)调整：把虚线改为实线，把节点按层次排列。
3.森林转换为二叉树
森林是树的集合，树可以和二叉树相互转换，森林也可以，只不过要麻烦一点点。
(1)转换：将森林中的每棵子树转换为二叉树，给每棵子树编号为1,2,3,......n棵二叉树。
(2)加线：在所有的二叉树的根节点之间加一条线，也就是从第二棵二叉树开始，将第i+1棵二叉树作为第i棵树的右子树。
4.二叉树转换为森林
(1)抹线：从二叉树的根节点开始搜索所有的右子孙节点，将其之间的连线抹去，这样就得到包含若干棵二叉树的森林。
(2)还原：将每棵二叉树还原为一般的树。
四、二叉排序树
二叉排序树，顾名思义就是用二叉树实现排序功能，是一种特殊的二叉树，需要满足一下性质
1.若左子树不为空，则左子树中所有节点的数据值均小于根节点的数据值。
2.若右子树不为空，则右子树中所有节点的数据值均大于根接待你的数据值。
3.左子树和右子树也分别是二叉排序树。
面试的时候可能会遇到这样的问题，给出一组数字，按照顺序插入，画出二叉排序树的结构图。下面举个例子，画出10,20,16,6,4,8,30,55这组数字的二叉排序树的结构。这里要说明一下插入的原理，插入的元素比上一个元素大，则插入在元素的右边，否则插入在元素的左边。
二叉排序树的插入
二叉排序树是动态查找，动态插入的树表，不是一次完成的。在查找的过程中，当书中不存在待插入的值时才进行插入操作。新插入的节点一定是叶子节点。
/**
* 二叉排序树的插入节点操作
* @param root 树的根节点
* @param value 插入值
* @return 插入的新节点
*/
public static WLTreeNode binaryTreeInsertion(WLTreeNode root,int value) {
//创建新节点
WLTreeNode node = new WLTreeNode(null, null, value);
if(root == null) {
return node;
}
WLTreeNode pNode = root;
WLTreeNode fNode = null;//找出新节点的直接父节点
//遍历二叉树，查找新节点添加位置
while (pNode != null) {
fNode = pNode;
if (value < pNode.getValue()) {
pNode = pNode.getLeft();
}else if(value > pNode.getValue()){
pNode = pNode.getRight();
}else {
break;
}
}
if(value < fNode.getValue()) {
fNode.setLeft(node);
}else if(value > fNode.getValue()){
fNode.setRight(node);
}
return node;
}
二叉排序树的查找
二叉排序树的查找就是遍历每个节点，比较关键字与每个节点的值是否相等，如果相等，则查找成功；否则在根节点的左子树或右子树中继续查找，这是一个递归的过程。
(1)如果二叉排序树为空，则查找失败，返回空指针。
(2)如果查找关键字和根节点值相等，则查找成功，返回根节点指针。
(3)如果查找关键字小于根节点值，则在根节点的左子树中查找。
(4)如果查找关键字大于根节点值，则在根节点的右子树中查找。
/**
* 二叉排序树的查找
* @param root 根节点
* @param x 关键字
* @return 关键字节点
*/
public static WLTreeNode binaryTreeSearch(WLTreeNode root,int x) {
if(root == null) {
return null;
}else if (x == root.getValue()) {
return root;
}else if (x < root.getValue()) {
return binaryTreeSearch(root.getLeft(), x);
}else {
return binaryTreeSearch(root.getRight(), x);
}
}
/**
* 二叉排序树的查找 非递归
* @param root 根节点
* @param x 关键字
* @return 关键字节点
*/
public static WLTreeNode binaryTreeSearchByStack(WLTreeNode root,int x) {
if(root != null) {
Stack<WLTreeNode> stack = new Stack<>();
while (root != null) {
if(root.getValue() == x) {
return root;
}else if (root.getValue() > x) {
stack.push(root);
root = root.getLeft();
}else {
stack.push(root);
root = root.getRight();
}
}
}
return null;
}
二叉排序树的删除
二叉排序树的删除操作是在查找的基础上进行的，也就是在二叉排序树中查找是否存在待删除关键字的节点，如果存在，则删除。二叉排序树的删除节点比较麻烦，可以分为一下四种情况：
(1)待删除节点为叶子节点，则直接删除
(2)待删除节点只有左子树，没有右子树，则用左子树代替该节点
(3)待删除节点只有右子树，没有左子树，则用右子树代替该节点
(4)待删除节点有左右子树，找出右子树中最小值的节点，将最小值节点替换该节点，
具体的实现方法如下：
/**
* 二叉排序树删除节点操作
* 1.如果节点为叶子节点，直接删除
* 2.如果节点只有左子树，无右子树，则用左子树代替该节点
* 3.如果节点只有右子树，无左子树，则用右子树代替该节点
* 4.如果节点有左、右子树，则找出其右子树最小值节点代替该节点
* @param root 树的根节点
* @param value 删除值
* @return 删除后的树
*/
public static WLTreeNode binaryTreeDelete(WLTreeNode root,int value) {
if(root != null) {
WLTreeNode pNode = root;//待删除节点
WLTreeNode fNode = null;//fNode为pNode的直接父节点
//找出pNode节点和pNode的直接父节点
while(pNode != null) {
if(value == pNode.getValue()) {
break;
}else if (value < pNode.getValue()) {
fNode = pNode;
pNode = pNode.getLeft();
}else {
fNode = pNode;
pNode = pNode.getRight();
}
}
//没有该节点
if(pNode == null) {
return root;
}
if(pNode.getLeft() == null && pNode.getRight() == null) {//待删除节点为叶子节点
//判断是否为根节点
if(fNode != null) {
if (pNode == fNode.getLeft()) {
fNode.setLeft(pNode.getLeft());
}else if (pNode == fNode.getRight()) {
fNode.setRight(pNode.getRight());
}
fNode = null;
}else {
root = null;
}
pNode = null;
}else if (pNode.getLeft() != null && pNode.getRight() == null) {//待删除节点只有左子树，没有右子树
if(fNode != null) {
if(pNode == fNode.getLeft()) {
fNode.setLeft(pNode.getLeft());
}else if (pNode == fNode.getRight()) {
fNode.setRight(pNode.getLeft());
}
fNode = null;
}else {
root = root.getLeft();
}
pNode = null;
}else if (pNode.getLeft() == null && pNode.getRight() != null) {//待删除节点只有右子树，没有左子树
if(fNode != null) {
if(pNode == fNode.getLeft()) {
fNode.setLeft(pNode.getRight());
}else if (pNode == fNode.getRight()) {
fNode.setRight(pNode.getRight());
}
}else {
root = root.getRight();
}
}else {//待删除节点同时有左右子树
//1.查找待删除节点的直接后驱节点，也就是该节点右子树中最小值节点qNode
//2.将qNode节点替换待删除节点
WLTreeNode sNode = pNode.getRight();//直接后驱节点
WLTreeNode qNode = sNode;//直接后驱节点的直接父节点
while (sNode.getLeft() != null) {
qNode = sNode;
sNode = sNode.getLeft();
}
if(sNode == qNode) {
fNode.setRight(qNode);
qNode.setLeft(pNode.getLeft());
}else {
qNode.setLeft(sNode.getLeft());
fNode.setRight(sNode);
sNode.setLeft(pNode.getLeft());
sNode.setRight(pNode.getRight());
}
pNode = null;
qNode = null;
fNode = null;
sNode = null;
}
return root;
}
return root;
}
五、平衡二叉树
在说平衡二叉树之前，需要先讲讲二叉排序树的查找的时间复杂度。对于含有n个节点的二叉排序树，查找关键字节点是从根节点开始，所需要比较次数就是该节点所在的层数。例如下图中，分别查找关键字10，6，16，55，查找的次数分别为1，2，3，4。假设每个节点的查找概率相等，所以平均查找次数为(1+22+34+4)/8 ≈ 2.6。如果是一颗单边二叉排序树(全部只有左子树或只有右子树)，则平均查找次数为(1+2+3+4+6+7+8)/8 = 4.5。
总结一下，在最好的情况下，一颗包含n个节点的二叉排序树的查找复杂度为O(log2(n))；在最坏的情况下，复杂度为O(n)。一般的情况下，复杂度介于O(log2(n))到O(n)之间。因此才需要构造一颗平衡的二叉排序树。
平衡二叉树的定义
平衡二叉树又叫AVL树，具有以下性质
1.左子树和右子树的深度的差值的绝对值不大于1
2.左子树和右子树都是平衡二叉树
以上的第二点很好理解，第一点怎么理解呢？如下图中，左边是平衡二叉树，右边是非平衡二叉树。图中节点右边是该节点左右子树深度的差值。
平衡二叉树的调整
在构建二叉排序树过程中，每插入一个新的节点，先判断插入是否会破坏树的平衡性。如果会，则找出最小不平衡子树，在保持二叉排序树的前提下，调整最小平衡子树中个节点之间的关系。可以根据失衡的原因分为以下四种类型：
(1)LL型调整
假设在A节点左孩子B的左子树上插入新的节点，导致A二叉排序树失去平衡。如下图中，插入值为2的新节点，A节点的值为10，B节点的值为6，此时A树的平衡差值从1变为2，从而失去了平衡。
调整操作：向右顺时针旋转一次，就是将B作为根节点，A作为B的有孩子，同时将B的原来的右子树作为A节点的左子树。
(2)RR型调整
在A节点右孩子B的右子树上插入新的节点，导致A二叉排序树失去平衡。如下图中，插入值为60的新节点，A节点的值为10，B节点的值为20，此时A、B树的平衡差值从1变为2，从而失去了平衡。
调整操作：向左逆时针旋转一次，就是将B作为根节点，A作为B的左孩子，同时B原来的左子树调整为A子树的右子树。
(3)LR型调整
在A节点的左孩子B的右子树C上插入新节点导致二叉排序树A失去平衡。如下图中，插入值为9的新节点，A节点的值为10，B节点的值为5，C节点值为7，此时A、B、C树的平衡差值从1变为2，从而失去平衡。
调整操作：进行两次选转，先顺时针在逆时针。就是将C作为根节点，A作为C的右孩子，B作为C的左孩子，同时调整C原来的两棵子树。将C原来的左子树作为B的右子树，C的右子树作为A的左子树。
(4)RL型调整
在A的右孩子B的左子树C上插入新的节点导致A树失去平衡。如下图中，插入值为9的新节点，A节点的值为10，B节点的值为20，C节点的值为16，此时A、B树的平衡差值从1变为2，C树的平衡差值从0变为1，从而失去平衡。
调整操作：将C节点作为根节点，A作为C的左孩子，B作为C的右孩子，同时调整C原来的两棵子树，将C原来的左子树调整为A的右子树，C原来的右子树调整为B的左孩子。
