数据结构——树

树形结构是一种非常重要的非线性的数据结构。树结构与线性结构不同之处：线性结构中任意一个元素最多只有一个后继元素，而树形结构中每个元素可以有多个后继；线性结构和树形结构中每个元素最多只有一个前驱元素。这篇文章为本人原创，谢绝转载。具体的内容目录如下：
一、树的属性
二、二叉树
三、二叉树与树、森林的转换
四、二叉排序树
五、平衡二叉树

一、树的属性

树又一个特定的称为根的节点，这个节点无前驱节点。树可以用递归的方式来定义，也就是说树是由若干个子树构成。如下图所示，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.链表存储结构
二叉树的链表结构有常见的两种：二叉链表、三叉链表。

• 二叉链表：包含一个数据元素，左子树指针，右子树指针。可以很容易找到该节点的子孙节点，但是不容易找到其双亲节点。

• 三叉链表：包含一个数据元素，左子树指针，右子树指针，还有一个双亲节点指针，方便找出其双亲节点。

  
  存储结构

二叉树的遍历
遍历二叉树就是以一定的顺序访问每个节点，并且每个节点只能被访问一次。
假设有一颗二叉树有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.左子树和右子树都是平衡二叉树
以上的第二点很好理解，第一点怎么理解呢？如下图中，左边是平衡二叉树，右边是非平衡二叉树。图中节点右边是该节点左右子树深度的差值。

AVL树
平衡二叉树的调整
在构建二叉排序树过程中，每插入一个新的节点，先判断插入是否会破坏树的平衡性。如果会，则找出最小不平衡子树，在保持二叉排序树的前提下，调整最小平衡子树中个节点之间的关系。可以根据失衡的原因分为以下四种类型：
(1)LL型调整
假设在A节点左孩子B的左子树上插入新的节点，导致A二叉排序树失去平衡。如下图中，插入值为2的新节点，A节点的值为10，B节点的值为6，此时A树的平衡差值从1变为2，从而失去了平衡。
调整操作：向右顺时针旋转一次，就是将B作为根节点，A作为B的有孩子，同时将B的原来的右子树作为A节点的左子树。
LL型调整

(2)RR型调整
在A节点右孩子B的右子树上插入新的节点，导致A二叉排序树失去平衡。如下图中，插入值为60的新节点，A节点的值为10，B节点的值为20，此时A、B树的平衡差值从1变为2，从而失去了平衡。
调整操作：向左逆时针旋转一次，就是将B作为根节点，A作为B的左孩子，同时B原来的左子树调整为A子树的右子树。

RR型调整

(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的左子树。

LR型调整

(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的左孩子。

RL型调整