广告

扫码关注官方微信

扫码下载APP
返回顶部
首页 > 资讯 > 后端开发 > Python >详解Java数据结构之平衡二叉树
  • 812

0
分享到

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

2024-04-02 19:04:59 812人浏览 安东尼

Python 官方文档：入门教程 => 点击学习

摘要

目录什么是二叉搜索树平衡二叉搜索树平衡二叉搜索树建树程序计算每个节点的高度计算每个节点的平衡因子合并二叉树旋转调整函数整体代码什么是二叉搜索树 简单来说，就是方便搜索的二叉树，是一种

什么是二叉搜索树

简单来说，就是方便搜索的二叉树，是一种具备特定结构的二叉树，即，对于节点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平衡二叉树的资料请关注编程网其它相关文章！

您可能感兴趣的文档:
点击免费下载>>软考高级考试备考技巧/历年真题/备考精华资料

--结束END--

本文标题: 详解Java数据结构之平衡二叉树

本文链接: https://www.lsjlt.com/news/138132.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com    QQ/279061341

本篇文章演示代码以及资料文档资料下载

下载Word文档到电脑，方便收藏和打印～

下载Word文档
去做题
猜你喜欢
  • 详解Java数据结构之平衡二叉树
    目录什么是二叉搜索树平衡二叉搜索树平衡二叉搜索树建树程序计算每个节点的高度计算每个节点的平衡因子合并二叉树旋转调整函数整体代码什么是二叉搜索树 简单来说，就是方便搜索的二叉树，是一种...
    99+
    2022-11-13
  • Java数据结构之平衡二叉树的实现详解
    目录定义结点结构查找算法插入算法LL 型RR 型LR 型RL 型插入方法删除算法概述实例分析代码完整代码定义 动机：二叉查找树的操作实践复杂度由树高度决定，所以希望控制树高，左右子...
    99+
    2022-11-13
  • Java数据结构之平衡二叉树的原理与实现
    目录1 平衡二叉树的概述2 平衡二叉树的实现原理2.1 单旋转2.2 双旋转2.3 总结3 平衡二叉树的构建3.1 类架构3.2 查找的方法3.3 检查是否平衡的方法3.4 插入的方...
    99+
    2022-11-13
  • Java数据结构之二叉搜索树详解
    目录前言性质实现节点结构初始化插入节点查找节点删除节点最后前言 今天leetcode的每日一题450是关于删除二叉搜索树节点的，题目要求删除指定值的节点，并且需要保证二叉搜索树性质不...
    99+
    2022-11-13
  • 数据结构之链式二叉树详解
    目录🍏1.二叉树的遍历🍏1.1前序遍历1.2中序遍历1.3后序遍历1.4层次遍历 🍎2.链式二叉树的实现🍎2.1二叉树的创建2.2前序遍历2.3中序遍历2.4后序遍历2.5...
    99+
    2023-05-16
    C语言链式二叉树 数据结构链式二叉树 C语言 数据结构
  • C语言之平衡二叉树详解
    目录什么是平衡二叉树平衡二叉树的基本特点为什么会出现平衡二叉树二叉树四种不平衡的情况C语言实现平衡二叉树什么是平衡二叉树 平衡二叉树是具有平衡属性的有序二叉树，所谓的平衡即当前树的左...
    99+
    2023-05-17
    C语言二叉树 C语言平衡二叉树
  • Java源码解析之平衡二叉树
    目录一、平衡二叉树的定义二、平衡二叉树的实现原理三、最终结果一、平衡二叉树的定义 平衡二叉树是一种二叉排序树，其中每一个节点的左子树和右子树的高度差至多等于1 。它是一种高度平衡的二...
    99+
    2022-11-12
  • Go 数据结构之二叉树详情
    目录Go 语言实现二叉树定义二叉树的结构二叉树遍历创建二叉树插入值测试前言： 树可以有许多不同的形状，并且它们可以在每个节点允许的子节点数量或它们在节点内组织数据值的方式上有所不同。...
    99+
    2022-11-13
  • C语言数据结构之二叉树详解
    目录1. 树概念及结构1.1树概念1.2树的表示2. 二叉树概念及结构2.1概念2.2数据结构中的二叉树2.3特殊的二叉树2.4二叉树的存储结构2.5二叉树的性质3. 二叉树顺序结构...
    99+
    2022-11-13
  • Java数据结构学习之二叉树
    一、背景知识：树（Tree） 在之前的笔记中，我们介绍的链表、栈、队列、数组和字符串都是以线性结构来组织数据的。本篇笔记要介绍的树采用的是树状结构，这是一种非线性的数据组织形式。 树...
    99+
    2022-11-12
  • java数据结构之搜索二叉树
    本文实例为大家分享了java数据结构之搜索二叉树的具体代码，供大家参考，具体内容如下 搜索二叉树的定义是：在一个二叉树上，左节点一定比父节点小，右节点一定比父节点大，其他定义跟二叉树...
    99+
    2022-11-12
  • 【Java 数据结构】树和二叉树
    篮球哥温馨提示：编程的同时不要忘记锻炼哦！ 一棵倒立过来的树.  目录 1、什么是树？ 1.1 简单认识树  1.2 树的概念  1.3 树的表示形式 2、二叉树 2.1 二叉树的概念 2.2 特殊的二叉树...
    99+
    2023-09-17
    算法 数据结构
  • C语言平衡二叉树详解
    目录调整措施：一、单旋转二、双旋转AVL树的删除操作：删除分为以下几种情况：1.要删除的节点是当前根节点T。2、要删除的节点元素值小于当前根节点T值，在左子树中进行删除。3、要删除的...
    99+
    2022-11-12
  • 数据结构TypeScript之二叉查找树实现详解
    目录树的结构特点面向对象方法封装二叉查找树（迭代版）二叉查找树的定义构造函数基本单元：二叉查找树节点主体：二叉查找树增加节点查找节点删除节点二叉树的遍历树的结构特点 树是一种有层次...
    99+
    2023-01-30
    TypeScript数据结构二叉查找树 TypeScript数据结构
  • Java数据结构二叉树难点解析
    前言 本章，我们主要需要了解以下内容 什么是线索二叉树 怎么去把二叉树线索化 怎么通过线索二叉树查找某个数的后继结点 二叉树的查看——二叉树怎们遍历...
    99+
    2022-11-12
  • C++数据结构之二叉搜索树的实现详解
    目录前言介绍实现节点的实现二叉搜索树的查找二叉搜索树的插入二叉搜索树的删除总结前言 今天我们来学一个新的数据结构：二叉搜索树。 介绍 二叉搜索树也称作二叉排序树，它具有以下性质： 非...
    99+
    2022-11-13
  • Go语言数据结构之二叉树可视化详解
    目录题目源代码做题思路扩展左右并列展示上下并列展示总结回顾题目 以图形展示任意二叉树，如下图，一个中缀表达式表示的二叉树：3.14*r²*h/3 源代码 package ...
    99+
    2022-11-11
  • 带你了解Java数据结构和算法之二叉树
    目录1、树2、二叉树3、查找节点4、插入节点5、遍历树6、查找最大值和最小值7、删除节点　　①、删除没有子节点的节点②、删除有一个子节点的节点③、删除有两个子节点的节点④、删除有必要...
    99+
    2022-11-13
  • Java数据结构之二叉排序树的实现
    目录1 二叉排序树的概述2 二叉排序树的构建2.1 类架构2.2 查找的方法2.3 插入的方法2.4 查找最大值和最小值2.5 删除的方法3 二叉排序树的总结1 二叉排序树的概述 本...
    99+
    2022-11-13
  • Java数据结构之二叉查找树的实现
    目录定义节点结构查找算法插入算法删除算法完整代码定义 二叉查找树（亦称二叉搜索树、二叉排序树）是一棵二叉树，且各结点关键词互异，其中根序列按其关键词递增排列。 等价描述：二叉查找树中...
    99+
    2022-11-13
软考高级职称资格查询
软考职称历年真题下载
软考职称资料下载
热门wiki
近期文章
推荐阅读
热门问答
热门标签
编程网，编程工程师的家园，是目前国内优秀的开源技术社区之一，形成了由开源软件库、代码分享、资讯、协作翻译、讨论区和博客等几大频道内容，为IT开发者提供了一个发现、使用、并交流开源技术的平台。

  • 官方手机版

  • 微信公众号

  • 商务合作