当前位置：首页 > article >正文

数据结构和算法-07平衡二叉树-01

article 2025/1/16 1:04:31

树的发展历程

来认识我们的树结构

平衡二叉树

如果得知二叉树是否平衡，直接的方法是左右子树的高度值不大于1。我们在节点中添加height指标用来检验二叉树的高度差。

规范：如果为空，高度 0。默认产生一个节点高度为： 1

tips：高度为虚拟高度（类似于层）

添加height属性

定义height属性，默认高度为1，即height=1为根节点。

package com.ffyc.tree.node;

/**
 * 树的节点
 */
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public int height;

    public TreeNode() {
    }

    public TreeNode(int val) {
        this.val = val;
        this.height = 1; //默认高度为1
    }

    public TreeNode(int val, TreeNode left, TreeNode right, int height) {
        this.val = val;
        this.left = left;
        this.right = right;
        this.height = height;
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "val=" + val +
                ", left=" + left +
                ", right=" + right +
                ", height=" + height +
                '}';
    }
}

获取height

public int getHeight(TreeNode curr) {
    if (curr == null) return 0;
    return curr.height;
}

更新insert

public TreeNode insert(TreeNode curr, int val) {
    if (curr == null) {
        size++;
        return new TreeNode(val);
    }

    if (val < curr.val) { //比左节点小
        curr.left = insert(curr.left, val);
    } else {
        curr.right = insert(curr.right, val);
    }
    curr.height = 1 + Math.max(getHeight(curr.left), getHeight(curr.right));
    return curr;
}

计算负载因子

public int balanceFactor(TreeNode curr) {
    if (curr == null) return 0;
    return Math.abs(getHeight(curr.left) - getHeight(curr.right));
}

如何判断一棵树是否为BST树

public boolean isBST(TreeNode curr) {
    if (curr == null) return true;
    List<Integer> list = new ArrayList<>();
    inOrder(curr, list);
    for (int i = 1; i < list.size(); i++) {
        if (list.get(i) < list.get(i - 1)) {
            return false;
        }
    }
    return true;
}

中序遍历

private  void inOrder(TreeNode root, List<Integer> list) {
    if (root == null) {
        return;
    }
    //System.out.print(root.val + "\t");
    inOrder(root.left, list);
    list.add(root.val);
    inOrder(root.right, list);
}

测试

int[] arr = {53, 51, 11, 23, 47, 62, 41, 9, 85, 19, 24, 13, 17, 50};
TreeNode  root = new TreeNode(arr[0]);
Bst bst= new Bst();
for(int i=1;i<arr.length;i++){
    root = bst.insert(root,arr[i]);

}
bst.inOrder(root);
new TreePrint<Integer>().print(root);
System.out.println(bst.getHeight(root.left));
System.out.println(bst.balanceFactor(root.left));
System.out.println(bst.isBST(root));