详解Java数据结构之平衡二叉树

什么是二叉搜索树

简单来说，就是方便搜索的二叉树，是一种具备特定结构的二叉树，即，对于节点n，其左子树的所有节点的值都小于等于其值，其右子树的所有节点的值都大于等于其值。​

以序列2,4,1,3,5,10,9,8为例，如果以二叉搜索树建树的方式，我们建立出来的逐个步骤应该为

第一步：

第二步：

第三步：

第四步：

第五步：

第六步：

第七步：

第八步：

按照不平衡的普通方法生成的二叉搜索树就是这么一个样子。其实现代码如下：

package com.chaojilaji.book.searchtree;

import com.chaojilaji.auto.autocode.utils.json;

import java.util.objects;

public class searchtreeutils {

    public static searchtree buildtree(searchtree searchtree, integer value) {
        if (value >= searchtree.getvalue()) {
            if (objects.isnull(searchtree.getrightchild())) {
                searchtree searchtree1 = new searchtree();
                searchtree1.setvalue(value);
                searchtree.setrightchild(searchtree1);
            } else {
                buildtree(searchtree.getrightchild(), value);
            }
        } else {
            if (objects.isnull(searchtree.getleftchild())) {
                searchtree searchtree1 = new searchtree();
                searchtree1.setvalue(value);
                searchtree.setleftchild(searchtree1);
            } else {
                buildtree(searchtree.getleftchild(), value);
            }
        }
        return searchtree;
    }

    public static void main(string[] args) {
        int[] a = new int[]{2, 4, 1, 3, 5, 10, 9, 8};
        searchtree searchtree = new searchtree();
        searchtree.setvalue(a[0]);
        for (int i = 1; i < a.length; i++) {
            searchtree = buildtree(searchtree,a[i]);
        }
        system.out.println(json.tojson(searchtree));
    }
}

运行的结果如下：

{
    "value": 2,
    "left_child": {
        "value": 1,
        "left_child": null,
        "right_child": null
    },
    "right_child": {
        "value": 4,
        "left_child": {
            "value": 3,
            "left_child": null,
            "right_child": null
        },
        "right_child": {
            "value": 5,
            "left_child": null,
            "right_child": {
                "value": 10,
                "left_child": {
                    "value": 9,
                    "left_child": {
                        "value": 8,
                        "left_child": null,
                        "right_child": null
                    },
                    "right_child": null
                },
                "right_child": null
            }
        }
    }
}

与我们的目标结果是一致的。

好了，那我们本节就完毕了。可是转过头可能你也发现了，直接生成的这个二叉搜索树似乎有点太长了，层数有点太多了，一般来说，一个长度为8的序列，四层结构的二叉树就可以表现出来了，这里却使用了六层，显然这样的结果不尽人意，同时太深的层数，也增加了查找的时间复杂度。

这就给我们的树提了要求，我们需要将目前构造出来的树平衡一下，让这棵二叉搜索树的左右子树“重量”最好差不多。

平衡二叉搜索树

首先需要掌握两个概念

• 平衡因子
• 旋转

平衡因子就是对于这棵二叉搜索树的每个节点来说，其左子树的高度减去右子树的高度即为该节点的平衡因子，该数值能很快的辨别出该节点究竟是左子树高还是右子树高。在平衡二叉树中规定，当一个节点的平衡因子的绝对值大于等于2的时候，我们就认为该节点不平衡，需要进行调整。那么这种调整的手段称之为节点与节点的旋转，通俗来说，旋转就是指的节点间的指向关系发生变化，在c语言中就是指针指向的切换。

在调用旋转之前，我们需要判断整棵树是否平衡，即，这棵二叉搜索树的所有平衡因子是否有绝对值大于等于2的，如果有，就找出最小的一棵子树。可以确定的是，如果前一次二叉搜索树是平衡的，那么此时如果加一个节点进去，造成不平衡，那么节点从叶子开始回溯，找到的第一个大于等于2的节点势必为最小不平衡子树的根节点。

对于这棵最小不平衡的子树，我们需要得到两个值，即根节点的平衡因子a，以及左右子树根节点中平衡因子绝对值较大者的平衡因子b。
我们可以将需要旋转的类型抽象为以下四种：​

1.左左型（正正型，即 a>0 && b>0）

左左型最后想要达到的目标是第二个节点成为根节点，第一个节点成为第二个节点的右节点。

所以用伪代码展示就是（设a1，a2，a3分别为图里面从上到下的三个节点）

a2的右子树 = (合并(a2的右子树,a1的右子树) + a1顶点值) 一起构成的二叉搜索树;

返回 a2 

2.左右型（正负型，即 a>0 && b<0）

设a1，a2，a3分别为图里面从上到下的三个节点

首先应该通过将a3和a2调换上下位置，使之变成左左型，然后再调用左左型的方法就完成了。

从左右型调换成左左型，即将a2及其左子树成为a3左子树的一部分，然后将a1的左子树置为a3即可。

伪代码如下：

a3的左子树 = a2及其左子树与a3的左子树合并成的一棵二叉搜索树;

a1的左子树 = a3;

3.右右型（负负型，即 a<0 && b<0）

设a1，a2，a3分别为图里面从上到下的三个节点

右右型与左左型类似，要达到的目的就是a1成为a2左子树的一部分，伪代码为：

a2的左子树 = （合并a2的左子树和a1的左子树）+ a1顶点的值构成的二叉搜索树;

返回a2

4.右左型（负正型，即 a<0 && b>0）

设a1，a2，a3分别为图里面从上到下的三个节点

右左型需要先转换成右右型，然后在调用右右型的方法即可。

从右左型到右右型，即需要将a2及其右子树成为a3右子树的一部分，然后将a1的右子树置为a3即可。

伪代码如下：

a3的右子树 = a2及其右子树与a3的右子树合并成的一棵二叉搜索树;

a1的右子树 = a3;

从上面的分析可以得出，我们不仅仅需要实现旋转的方法，还需要实现合并二叉树等方法，这些方法都是基础方法，读者需要确保会快速写出来。

请读者朋友们根据上面的内容，先尝试写出集中平衡化的方法。

平衡二叉搜索树建树程序

平衡二叉搜索树建树，需要在二叉搜索树建树的基础上加上平衡的过程，即子树之间指针转换的问题，同时，由于这种指针转换引起的子树的子树也会产生不平衡，所以上面提到的四种旋转调整方式都是递归的。

首先，先构建节点基础结构：

public class searchtree {

    private integer value;

    private searchtree leftchild;
    private searchtree rightchild;
    private integer balancenumber = 0;
    private integer height = 0;
}

值，高度，平衡因子，左子树，右子树

计算每个节点的高度

这是计算二叉搜索树中每个平衡因子的基础，我们设最低层为高度1，则计算节点高度的代码为：

public static integer countheight(searchtree searchtree) {
    if (objects.isnull(searchtree)) {
        return 0;
    }
    searchtree.setheight(math.max(countheight(searchtree.getleftchild()),
                                  countheight(searchtree.getrightchild())) + 1);
    return searchtree.getheight();
}

这里有个半动态规划的结论：当前节点的高度，等于左右子树的最大高度+1；这里的写法有点树形dp的味道。

计算每个节点的平衡因子

public static void countbalancenumber(searchtree searchtree, maxnumber max, searchtree fathertree, integer type) {
    if (objects.nonnull(searchtree.getvalue())) {
        if (objects.isnull(searchtree.getleftchild()) 
            && objects.nonnull(searchtree.getrightchild())) {
            searchtree.setbalancenumber(-searchtree.getrightchild().getheight());
        }
        if (objects.nonnull(searchtree.getleftchild()) 
            && objects.isnull(searchtree.getrightchild())) {
            searchtree.setbalancenumber(searchtree.getleftchild().getheight());
        }
        if (objects.isnull(searchtree.getleftchild()) 
            && objects.isnull(searchtree.getrightchild())) {
            searchtree.setbalancenumber(0);
        }
        if (objects.nonnull(searchtree.getleftchild()) 
            && objects.nonnull(searchtree.getrightchild())) {
            searchtree.setbalancenumber(searchtree.getleftchild().getheight() 
                                        - searchtree.getrightchild().getheight());
        }
    }

    if (objects.nonnull(searchtree.getleftchild())) {
        countbalancenumber(searchtree.getleftchild(), max, searchtree, 1);
    }
    if (objects.nonnull(searchtree.getrightchild())) {
        countbalancenumber(searchtree.getrightchild(), max, searchtree, 2);
    }

}

本质上讲，平衡因子就是左子树高度减去右子树高度，注意这里左右子树都有可能不存在，所以加入了一堆特判。

判断当前二叉树是否平衡

static class maxnumber {
    public integer max;
    public searchtree childtree;
    public searchtree fathertree;
    public integer flag = 0; // 0 代表自己就是根,1代表childtree是左子树，2代表childtree是右子树
}

public static maxnumber checkbalance(searchtree searchtree) {
    maxnumber max = new maxnumber();
    max.max = 0;
    countbalancenumber(searchtree, max, null, 0);
    return max;
}

public static void countbalancenumber(searchtree searchtree, maxnumber max, searchtree fathertree, integer type) {
    if (objects.nonnull(searchtree.getvalue())) {
        if (objects.isnull(searchtree.getleftchild()) 
            && objects.nonnull(searchtree.getrightchild())) {
            searchtree.setbalancenumber(-searchtree.getrightchild().getheight());
        }
        if (objects.nonnull(searchtree.getleftchild()) 
            && objects.isnull(searchtree.getrightchild())) {
            searchtree.setbalancenumber(searchtree.getleftchild().getheight());
        }
        if (objects.isnull(searchtree.getleftchild()) 
            && objects.isnull(searchtree.getrightchild())) {
            searchtree.setbalancenumber(0);
        }
        if (objects.nonnull(searchtree.getleftchild()) 
            && objects.nonnull(searchtree.getrightchild())) {
            searchtree.setbalancenumber(searchtree.getleftchild().getheight() 
                                        - searchtree.getrightchild().getheight());
        }
    }


    if (objects.nonnull(searchtree.getleftchild())) {
        countbalancenumber(searchtree.getleftchild(), max, searchtree, 1);
    }
    if (objects.nonnull(searchtree.getrightchild())) {
        countbalancenumber(searchtree.getrightchild(), max, searchtree, 2);
    }
    if (math.abs(searchtree.getbalancenumber()) >= math.abs(max.max)) {
        if (math.abs(searchtree.getbalancenumber()) == math.abs(max.max) 
            && max.childtree == null) {
            max.childtree = searchtree;
            max.fathertree = fathertree;
            max.flag = type;
            max.max = searchtree.getbalancenumber();
        }
        if (math.abs(searchtree.getbalancenumber()) > math.abs(max.max)) {
            max.childtree = searchtree;
            max.fathertree = fathertree;
            max.flag = type;
            max.max = searchtree.getbalancenumber();
        }
    }
}

其中，maxnumber类是为了保存第一棵不平衡的子树而存在的结构，为了使这棵子树平衡之后能重新回到整棵树中，需要在maxnumber中存储当前子树父节点，同时标明当前子树是父节点的左子树还是右子树，还是本身。

合并二叉树

public static void getallvalue(searchtree tree, set<integer> sets) {
    if (objects.isnull(tree)) return;
    if (objects.nonnull(tree.getvalue())) {
        sets.add(tree.getvalue());
    }
    if (objects.nonnull(tree.getleftchild())) {
        getallvalue(tree.getleftchild(), sets);
    }
    if (objects.nonnull(tree.getrightchild())) {
        getallvalue(tree.getrightchild(), sets);
    }
}

/**
     * 合并两棵二叉搜索树
     *
     * @param a
     * @param b
     * @return
     */
public static searchtree mergetree(searchtree a, searchtree b) {
    set<integer> vals = new hashset<>();
    getallvalue(b, vals);
    for (integer c : vals) {
        a = buildtree(a, c);
    }
    return a;
}

将一棵树转成数字集合，然后通过建树的方式建到另外一棵树上即可。

旋转调整函数

1.左左型旋转
/**
     * 左左
     *
     * @param searchtree
     * @return
     */
public static searchtree leftrotate1(searchtree father, searchtree searchtree) {
    searchtree b = father;
    searchtree newright = mergetree(father.getrightchild(), searchtree.getrightchild());
    newright = buildtree(newright, b.getvalue());
    countheight(newright);
    while (math.abs(checkbalance(newright).childtree.getbalancenumber()) >= 2) {
        newright = rotate(checkbalance(newright).childtree);
        countheight(newright);
    }
    searchtree.setrightchild(newright);
    return searchtree;
}

2.右右型旋转

/**
     * 右右
     * @param father
     * @param searchtree
     * @return
     */
public static searchtree rightrotate1(searchtree father, searchtree searchtree) {
    searchtree b = father;
    searchtree newleft = mergetree(father.getleftchild(), searchtree.getleftchild());
    newleft = buildtree(newleft, b.getvalue());
    countheight(newleft);
    while (math.abs(checkbalance(newleft).childtree.getbalancenumber()) >= 2) {
        newleft = rotate(checkbalance(newleft).childtree);
        countheight(newleft);
    }
    searchtree.setleftchild(newleft);
    return searchtree;
}

3.左右型旋转

/**
     * 左右
     *
     * @param searchtree
     * @return
     */
public static searchtree rightrotate2(searchtree father, searchtree searchtree) {
    searchtree a1 = father;
    searchtree a2 = searchtree;
    searchtree a3 = searchtree.getrightchild();
    searchtree newleft = mergetree(a2.getleftchild(), a3.getleftchild());
    newleft = buildtree(newleft, a2.getvalue());
    countheight(newleft);
    while (math.abs(checkbalance(newleft).childtree.getbalancenumber()) >= 2) {
        newleft = rotate(checkbalance(newleft).childtree);
        countheight(newleft);
    }
    a3.setleftchild(newleft);
    a1.setleftchild(a3);
    return a1;
}

4.右左型旋转

/**
     * 右左
     *
     * @param searchtree
     * @return
     */
public static searchtree leftrotate2(searchtree father, searchtree searchtree) {
    searchtree a1 = father;
    searchtree a2 = searchtree;
    searchtree a3 = searchtree.getleftchild();
    searchtree newright = mergetree(a2.getrightchild(), a3.getrightchild());
    newright = buildtree(newright, a2.getvalue());
    countheight(newright);
    while (math.abs(checkbalance(newright).childtree.getbalancenumber()) >= 2) {
        newright = rotate(checkbalance(newright).childtree);
        countheight(newright);
    }
    a3.setrightchild(newright);
    a1.setrightchild(a3);
    return a1;
}

旋转调用函数：

public static searchtree rotate(searchtree searchtree) {
    int a = searchtree.getbalancenumber();
    if (math.abs(a) < 2) {
        return searchtree;
    }
    int b = objects.isnull(searchtree.getleftchild()) ? 0 
        : searchtree.getleftchild().getbalancenumber();
    int c = objects.isnull(searchtree.getrightchild()) ? 0 
        : searchtree.getrightchild().getbalancenumber();
    if (a > 0) {
        if (b > 0) {
            // todo: 2022/1/13 左左
            searchtree = leftrotate1(searchtree, searchtree.getleftchild());
        } else {
            // todo: 2022/1/13 左右
            searchtree = rightrotate2(searchtree, searchtree.getleftchild());
            searchtree = leftrotate1(searchtree, searchtree.getleftchild());
        }
    } else {
        if (c > 0) {
            // todo: 2022/1/13 右左
            searchtree = leftrotate2(searchtree, searchtree.getrightchild());
            searchtree = rightrotate1(searchtree, searchtree.getrightchild());
        } else {
            // todo: 2022/1/13 右右
            searchtree = rightrotate1(searchtree, searchtree.getrightchild());
        }
    }
    return searchtree;
}

整体代码

package com.chaojilaji.book.searchtree;

import com.chaojilaji.auto.autocode.utils.json;
import com.chaojilaji.book.tree.handle;
import com.chaojilaji.book.tree.tree;
import org.omg.corba.obj_adapter;

import java.util.hashset;
import java.util.objects;
import java.util.set;

public class searchtreeutils {


    static class maxnumber {
        public integer max;
        public searchtree childtree;
        public searchtree fathertree;
        public integer flag = 0; // 0 代表自己就是根,1代表childtree是左子树，2代表childtree是右子树
    }

    public static searchtree rotate(searchtree searchtree) {
        int a = searchtree.getbalancenumber();
        if (math.abs(a) < 2) {
            return searchtree;
        }
        int b = objects.isnull(searchtree.getleftchild()) ? 0 : searchtree.getleftchild().getbalancenumber();
        int c = objects.isnull(searchtree.getrightchild()) ? 0 : searchtree.getrightchild().getbalancenumber();
        if (a > 0) {
            if (b > 0) {
                // todo: 2022/1/13 左左
                searchtree = leftrotate1(searchtree, searchtree.getleftchild());
            } else {
                // todo: 2022/1/13 左右
                searchtree = rightrotate2(searchtree, searchtree.getleftchild());
                searchtree = leftrotate1(searchtree, searchtree.getleftchild());
            }
        } else {
            if (c > 0) {
                // todo: 2022/1/13 右左
                searchtree = leftrotate2(searchtree, searchtree.getrightchild());
                searchtree = rightrotate1(searchtree, searchtree.getrightchild());
            } else {
                // todo: 2022/1/13 右右
                searchtree = rightrotate1(searchtree, searchtree.getrightchild());
            }
        }
        return searchtree;
    }

    public static void getallvalue(searchtree tree, set<integer> sets) {
        if (objects.isnull(tree)) return;
        if (objects.nonnull(tree.getvalue())) {
            sets.add(tree.getvalue());
        }
        if (objects.nonnull(tree.getleftchild())) {
            getallvalue(tree.getleftchild(), sets);
        }
        if (objects.nonnull(tree.getrightchild())) {
            getallvalue(tree.getrightchild(), sets);
        }
    }

    /**
     * 合并两棵二叉搜索树
     *
     * @param a
     * @param b
     * @return
     */
    public static searchtree mergetree(searchtree a, searchtree b) {
        set<integer> vals = new hashset<>();
        getallvalue(b, vals);
        for (integer c : vals) {
            a = buildtree(a, c);
        }
        return a;
    }

    /**
     * 左左
     *
     * @param searchtree
     * @return
     */
    public static searchtree leftrotate1(searchtree father, searchtree searchtree) {
        searchtree b = father;
        searchtree newright = mergetree(father.getrightchild(), searchtree.getrightchild());
        newright = buildtree(newright, b.getvalue());
        countheight(newright);
        while (math.abs(checkbalance(newright).childtree.getbalancenumber()) >= 2) {
            newright = rotate(checkbalance(newright).childtree);
            countheight(newright);
        }
        searchtree.setrightchild(newright);
        return searchtree;
    }

    /**
     * 右左
     *
     * @param searchtree
     * @return
     */
    public static searchtree leftrotate2(searchtree father, searchtree searchtree) {
        searchtree a1 = father;
        searchtree a2 = searchtree;
        searchtree a3 = searchtree.getleftchild();
        searchtree newright = mergetree(a2.getrightchild(), a3.getrightchild());
        newright = buildtree(newright, a2.getvalue());
        countheight(newright);
        while (math.abs(checkbalance(newright).childtree.getbalancenumber()) >= 2) {
            newright = rotate(checkbalance(newright).childtree);
            countheight(newright);
//            system.out.println(json.tojson(newright));
        }
        a3.setrightchild(newright);
        a1.setrightchild(a3);
        return a1;
    }

    /**
     * 右右
     * @param father
     * @param searchtree
     * @return
     */
    public static searchtree rightrotate1(searchtree father, searchtree searchtree) {
        searchtree b = father;
        searchtree newleft = mergetree(father.getleftchild(), searchtree.getleftchild());
        newleft = buildtree(newleft, b.getvalue());
        countheight(newleft);
//         todo: 2022/1/13 合并后的也有可能有问题
        while (math.abs(checkbalance(newleft).childtree.getbalancenumber()) >= 2) {
            newleft = rotate(checkbalance(newleft).childtree);
            countheight(newleft);
//            system.out.println(json.tojson(newleft));
        }
        searchtree.setleftchild(newleft);
        return searchtree;
    }

    /**
     * 左右
     *
     * @param searchtree
     * @return
     */
    public static searchtree rightrotate2(searchtree father, searchtree searchtree) {
        searchtree a1 = father;
        searchtree a2 = searchtree;
        searchtree a3 = searchtree.getrightchild();
        searchtree newleft = mergetree(a2.getleftchild(), a3.getleftchild());
        newleft = buildtree(newleft, a2.getvalue());
        countheight(newleft);
        while (math.abs(checkbalance(newleft).childtree.getbalancenumber()) >= 2) {
            newleft = rotate(checkbalance(newleft).childtree);
            countheight(newleft);
        }
        a3.setleftchild(newleft);
        a1.setleftchild(a3);
        return a1;
    }

    public static maxnumber checkbalance(searchtree searchtree) {
        maxnumber max = new maxnumber();
        max.max = 0;
        countbalancenumber(searchtree, max, null, 0);
        return max;
    }


    public static integer countheight(searchtree searchtree) {
        if (objects.isnull(searchtree)) {
            return 0;
        }
        searchtree.setheight(math.max(countheight(searchtree.getleftchild()), countheight(searchtree.getrightchild())) + 1);
        return searchtree.getheight();
    }


    public static void countbalancenumber(searchtree searchtree, maxnumber max, searchtree fathertree, integer type) {
        if (objects.nonnull(searchtree.getvalue())) {
            if (objects.isnull(searchtree.getleftchild()) && objects.nonnull(searchtree.getrightchild())) {
                searchtree.setbalancenumber(-searchtree.getrightchild().getheight());
            }
            if (objects.nonnull(searchtree.getleftchild()) && objects.isnull(searchtree.getrightchild())) {
                searchtree.setbalancenumber(searchtree.getleftchild().getheight());
            }
            if (objects.isnull(searchtree.getleftchild()) && objects.isnull(searchtree.getrightchild())) {
                searchtree.setbalancenumber(0);
            }
            if (objects.nonnull(searchtree.getleftchild()) && objects.nonnull(searchtree.getrightchild())) {
                searchtree.setbalancenumber(searchtree.getleftchild().getheight() - searchtree.getrightchild().getheight());
            }
        }


        if (objects.nonnull(searchtree.getleftchild())) {
            countbalancenumber(searchtree.getleftchild(), max, searchtree, 1);
        }
        if (objects.nonnull(searchtree.getrightchild())) {
            countbalancenumber(searchtree.getrightchild(), max, searchtree, 2);
        }
        if (math.abs(searchtree.getbalancenumber()) >= math.abs(max.max)) {
            if (math.abs(searchtree.getbalancenumber()) == math.abs(max.max) && max.childtree == null) {
                max.childtree = searchtree;
                max.fathertree = fathertree;
                max.flag = type;
                max.max = searchtree.getbalancenumber();
            }
            if (math.abs(searchtree.getbalancenumber()) > math.abs(max.max)) {
                max.childtree = searchtree;
                max.fathertree = fathertree;
                max.flag = type;
                max.max = searchtree.getbalancenumber();
            }
        }
    }

    public static searchtree buildtree(searchtree searchtree, integer value) {
        if (objects.isnull(searchtree)) {
            searchtree = new searchtree();
        }
        if (objects.isnull(searchtree.getvalue())) {
            searchtree.setvalue(value);
            return searchtree;
        }
        if (value >= searchtree.getvalue()) {
            if (objects.isnull(searchtree.getrightchild())) {
                searchtree searchtree1 = new searchtree();
                searchtree1.setvalue(value);
                searchtree.setrightchild(searchtree1);
            } else {
                buildtree(searchtree.getrightchild(), value);
            }
        } else {
            if (objects.isnull(searchtree.getleftchild())) {
                searchtree searchtree1 = new searchtree();
                searchtree1.setvalue(value);
                searchtree.setleftchild(searchtree1);
            } else {
                buildtree(searchtree.getleftchild(), value);
            }
        }
        return searchtree;
    }

    public static void main(string[] args) {
//        int[] a = new int[]{2, 4, 1, 3, 5, 10, 9, 8};
        int[] a = new int[]{2, 4, 1, 3, 5, 10, 9, 8, 6, 7};
        searchtree searchtree = new searchtree();
        for (int i = 0; i < a.length; i++) {
            searchtree = buildtree(searchtree, a[i]);
            countheight(searchtree);
            maxnumber maxnumber = checkbalance(searchtree);
            searchtree searchtree1 = maxnumber.childtree;
            if (math.abs(searchtree1.getbalancenumber()) >= 2) {
                searchtree1 = rotate(searchtree1);
                if (maxnumber.flag == 0) {
                    maxnumber.fathertree = searchtree1;
                    searchtree = searchtree1;
                } else if (maxnumber.flag == 1) {
                    maxnumber.fathertree.setleftchild(searchtree1);
                } else if (maxnumber.flag == 2) {
                    maxnumber.fathertree.setrightchild(searchtree1);
                }
                countheight(searchtree);
            }

        }
        system.out.println("最终为\n" + json.tojson(searchtree));
    }
}

以序列2, 4, 1, 3, 5, 10, 9, 8, 6, 7为例，构造的平衡二叉搜索树结构为

{
    "value": 4,
    "left_child": {
        "value": 2,
        "left_child": {
            "value": 1,
            "left_child": null,
            "right_child": null,
            "balance_number": 0,
            "height": 1
        },
        "right_child": {
            "value": 3,
            "left_child": null,
            "right_child": null,
            "balance_number": 0,
            "height": 1
        },
        "balance_number": 0,
        "height": 2
    },
    "right_child": {
        "value": 8,
        "left_child": {
            "value": 6,
            "left_child": {
                "value": 5,
                "left_child": null,
                "right_child": null,
                "balance_number": 0,
                "height": 1
            },
            "right_child": {
                "value": 7,
                "left_child": null,
                "right_child": null,
                "balance_number": 0,
                "height": 1
            },
            "balance_number": 0,
            "height": 2
        },
        "right_child": {
            "value": 10,
            "left_child": {
                "value": 9,
                "left_child": null,
                "right_child": null,
                "balance_number": 0,
                "height": 1
            },
            "right_child": null,
            "balance_number": 1,
            "height": 2
        },
        "balance_number": 0,
        "height": 3
    },
    "balance_number": -1,
    "height": 4
}

以上就是详解java数据结构之平衡二叉树的详细内容，更多关于java平衡二叉树的资料请关注其它相关文章！