详解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);
    }
}


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.左左型旋转

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.右右型旋转


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.左右型旋转


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.右左型旋转


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);
        }
    }

    
    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;
    }

    
    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;
    }

    
    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;
    }

    
    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;
    }

    
    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平衡二叉树的资料请关注编程网其它相关文章！

文章详情

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

目录

什么是二叉搜索树

平衡二叉搜索树

平衡二叉搜索树建树程序

计算每个节点的高度

计算每个节点的平衡因子

合并二叉树

旋转调整函数

整体代码

软考中级精品资料免费领

相关文章

猜你喜欢

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

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

Java数据结构之平衡二叉树的原理与实现

Java数据结构之二叉搜索树详解

数据结构之链式二叉树详解

C语言之平衡二叉树详解

Java源码解析之平衡二叉树

java数据结构之搜索二叉树

Go 数据结构之二叉树详情

Java数据结构学习之二叉树

C语言数据结构之二叉树详解

【Java 数据结构】树和二叉树

C语言平衡二叉树详解

数据结构TypeScript之二叉查找树实现详解

Java数据结构二叉树难点解析

C++数据结构之二叉搜索树的实现详解

Java数据结构之二叉排序树的实现

Go语言数据结构之二叉树可视化详解

Java数据结构之二叉查找树的实现

带你了解Java数据结构和算法之二叉树