java怎么实现平衡二叉树

共计 2999 个字符，预计需要花费 8 分钟才能阅读完成。

要实现平衡二叉树，可以使用红黑树或 AVL 树这样的自平衡二叉搜索树。
以下是使用 AVL 树实现平衡二叉树的示例代码：

// AVL 树节点类
class Node {
    int val;
    int height;
    Node left;
    Node right;
    Node(int val) {
        this.val = val;
        this.height = 1;
    }
}
// 平衡二叉树类
class AVLTree {
    private Node root;
    // 获取节点的高度 
    private int getHeight(Node node) {
        if (node == null) {
            return 0;
        }
        return node.height;
    }
    // 更新节点的高度 
    private void updateHeight(Node node) {
        node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
    }
    // 获取节点的平衡因子 
    private int getBalanceFactor(Node node) {
        if (node == null) {
            return 0;
        }
        return getHeight(node.left) - getHeight(node.right);
    }
    // 右旋操作 
    private Node rightRotate(Node node) {
        Node newRoot = node.left;
        node.left = newRoot.right;
        newRoot.right = node;
        updateHeight(node);
        updateHeight(newRoot);
        return newRoot;
    }
    // 左旋操作 
    private Node leftRotate(Node node) {
        Node newRoot = node.right;
        node.right = newRoot.left;
        newRoot.left = node;
        updateHeight(node);
        updateHeight(newRoot);
        return newRoot;
    }
    // 平衡节点 
    private Node balance(Node node) {
        if (node == null) {
            return null;
        }
        updateHeight(node);
        int balanceFactor = getBalanceFactor(node);
        if (balanceFactor > 1) {
            if (getBalanceFactor(node.left) >= 0) {
                return rightRotate(node);
            } else {
                node.left = leftRotate(node.left);
                return rightRotate(node);
            }
        } else if (balanceFactor < -1) {
            if (getBalanceFactor(node.right) <= 0) {
                return leftRotate(node);
            } else {
                node.right = rightRotate(node.right);
                return leftRotate(node);
            }
        }
        return node;
    }
    // 插入节点 
    public void insert(int val) {
        root = insert(root, val);
    }
    private Node insert(Node node, int val) {
        if (node == null) {
            return new Node(val);
        }
        if (val < node.val) {
            node.left = insert(node.left, val);
        } else if (val > node.val) {
            node.right = insert(node.right, val);
        } else {
            // 如果树中已经存在相同值的节点，则不进行插入 
            return node;
        }
        return balance(node);
    }
    // 中序遍历 
    public void inorderTraversal() {
        inorderTraversal(root);
    }
    private void inorderTraversal(Node node) {
        if (node == null) {
            return;
        }
        inorderTraversal(node.left);
        System.out.print(node.val + " ");
        inorderTraversal(node.right);
    }
}
// 测试代码
public class Main {
    public static void main(String[] args) {
        AVLTree tree = new AVLTree();
        tree.insert(3);
        tree.insert(2);
        tree.insert(1);
        
        tree.inorderTraversal();  // 输出：1 2 3
    }
}

以上是使用 AVL 树实现平衡二叉树的示例代码，其中包含了插入节点、平衡节点和中序遍历等操作。你可以根据需要进行修改和扩展。

丸趣 TV 网 – 提供最优质的资源集合！