java怎么实现平衡二叉树

59次阅读
没有评论

共计 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 网 – 提供最优质的资源集合!

正文完
 
丸趣
版权声明:本站原创文章,由 丸趣 2023-12-12发表,共计2999字。
转载说明:除特殊说明外本站除技术相关以外文章皆由网络搜集发布,转载请注明出处。
评论(没有评论)