数据结构之二叉树和平衡二叉树

1、二叉树：

package com.datastructure.tree;
//一个常用的第三方库是Apache Commons Collections，它提供了一个名为BinaryTree的类，用于表示二叉树。
//可以使用org.apache.commons.collections4.BinaryTree类创建二叉树和进行操作。
//可以在Maven中添加以下依赖项：
//<dependency>
//<groupId>org.apache.commons</groupId>
//<artifactId>commons-collections4</artifactId>
//<version>4.4</version>
//</dependency>
public class BinaryTree {
    private Node root;

    private class Node {
        private int data;
        private Node left;
        private Node right;

        public Node(int data) {
            this.data = data;
            this.left = null;
            this.right = null;
        }
    }

    // 插入节点
    public void insert(int data) {
        root = insert(root, data);
    }

    private Node insert(Node node, int data) {
        if (node == null) {
            node = new Node(data);
        } else {
            if (data <= node.data) {
                node.left = insert(node.left, data);
            } else {
                node.right = insert(node.right, data);
            }
        }
        return node;
    }

    // 前序遍历
    public void preOrderTraversal() {
        preOrderTraversal(root);
    }

    private void preOrderTraversal(Node node) {
        if (node != null) {
            System.out.println(node.data);
            preOrderTraversal(node.left);
            preOrderTraversal(node.right);
        }
    }

    // 中序遍历
    public void inOrderTraversal() {
        inOrderTraversal(root);
    }

    private void inOrderTraversal(Node node) {
        if (node != null) {
            inOrderTraversal(node.left);
            System.out.println(node.data);
            inOrderTraversal(node.right);
        }
    }

    // 后序遍历
    public void postOrderTraversal() {
        postOrderTraversal(root);
    }

    private void postOrderTraversal(Node node) {
        if (node != null) {
            postOrderTraversal(node.left);
            postOrderTraversal(node.right);
            System.out.println(node.data);
        }
    }
}

package com.datastructure.tree;

public class BinaryTreeDemo {
    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        tree.insert(5);
        tree.insert(3);
        tree.insert(7);
        tree.insert(2);
        tree.insert(4);
        tree.insert(6);
        tree.insert(8);

        System.out.println("前序遍历:");
        tree.preOrderTraversal();

        System.out.println("中序遍历:");
        tree.inOrderTraversal();

        System.out.println("后序遍历:");
        tree.postOrderTraversal();
    }
}

2、平衡二叉树：

package com.datastructure.tree;
//平衡树
//AVLTree是一个泛型类，可以存储任意实现了Comparable接口的类型。
//在AVLTree类中，使用Node类来表示树节点，并在节点中保存了节点值、左子节点、右子节点和节点高度。
//在插入操作中，使用递归的方式在树中查找合适的位置插入新节点，并在返回时重新平衡树。
//在插入节点之后，检查当前节点的平衡因子，如果超出范围，则通过旋转操作来恢复平衡。
//除了插入操作之外，还可以实现其他操作，例如删除节点、查找节点、遍历等。
public class AVLTreeDemo<T extends Comparable<T>> {
    private class Node {
        T value;
        Node left;
        Node right;
        int height;

        Node(T value) {
            this.value = value;
            this.height = 1;
        }
    }

    private Node root;

    private int height(Node node) {
        if (node == null) {
            return 0;
        }
        return node.height;
    }

    private int balanceFactor(Node node) {
        if (node == null) {
            return 0;
        }
        return height(node.left) - height(node.right);
    }

    private Node rotateLeft(Node x) {
        Node y = x.right;
        Node T2 = y.left;

        y.left = x;
        x.right = T2;

        x.height = Math.max(height(x.left), height(x.right)) + 1;
        y.height = Math.max(height(y.left), height(y.right)) + 1;

        return y;
    }

    private Node rotateRight(Node y) {
        Node x = y.left;
        Node T2 = x.right;

        x.right = y;
        y.left = T2;

        y.height = Math.max(height(y.left), height(y.right)) + 1;
        x.height = Math.max(height(x.left), height(x.right)) + 1;

        return x;
    }

    public void insert(T value) {
        root = insert(root, value);
    }

    private Node insert(Node node, T value) {
        if (node == null) {
            return new Node(value);
        }

        if (value.compareTo(node.value) < 0) {
            node.left = insert(node.left, value);
        } else if (value.compareTo(node.value) > 0) {
            node.right = insert(node.right, value);
        } else {
            return node; // 不允许插入重复的值
        }

        node.height = Math.max(height(node.left), height(node.right)) + 1;

        int balance = balanceFactor(node);
        if (balance > 1 && value.compareTo(node.left.value) < 0) {
            return rotateRight(node);
        }
        if (balance < -1 && value.compareTo(node.right.value) > 0) {
            return rotateLeft(node);
        }
        if (balance > 1 && value.compareTo(node.left.value) > 0) {
            node.left = rotateLeft(node.left);
            return rotateRight(node);
        }
        if (balance < -1 && value.compareTo(node.right.value) < 0) {
            node.right = rotateRight(node.right);
            return rotateLeft(node);
        }

        return node;
    }

    public void delete(T value) {
        root = delete(root, value);
    }

    private Node delete(Node node, T value) {
        if (node == null) {
            return null;
        }

        if (value.compareTo(node.value) < 0) {
            node.left = delete(node.left, value);
        } else if (value.compareTo(node.value) > 0) {
            node.right = delete(node.right, value);
        } else {
            if (node.left == null || node.right == null) {
                Node temp = null;
                if (node.left != null) {
                    temp = node.left;
                } else {
                    temp = node.right;
                }

                if (temp == null) {
                    temp = node;
                    node = null;
                } else {
                    node = temp;
                }
            } else {
                Node temp = minValueNode(node.right);
                node.value = temp.value;
                node.right = delete(node.right, temp.value);
            }
        }

        if (node == null) {
            return node;
        }

        node.height = Math.max(height(node.left), height(node.right)) + 1;

        int balance = balanceFactor(node);
        if (balance > 1 && balanceFactor(node.left) >= 0) {
            return rotateRight(node);
        }
        if (balance > 1 && balanceFactor(node.left) < 0) {
            node.left = rotateLeft(node.left);
            return rotateRight(node);
        }
        if (balance < -1 && balanceFactor(node.right) <= 0) {
            return rotateLeft(node);
        }
        if (balance < -1 && balanceFactor(node.right) > 0) {
            node.right = rotateRight(node.right);
            return rotateLeft(node);
        }

        return node;
    }

    private Node minValueNode(Node node) {
        Node current = node;
        while (current.left != null) {
            current = current.left;
        }
        return current;
    }

    // 其他操作方法...
    
    // 中序遍历
    public void inorderTraversal() {
        inorderTraversal(root);
    }
    
    private void inorderTraversal(Node node) {
        if (node != null) {
            inorderTraversal(node.left);
            System.out.print(node.value + " ");
            inorderTraversal(node.right);
        }
    }
}

package com.datastructure.tree;
//可以在项目中添加Apache Commons Collections库的依赖。
//可以在Maven项目中的pom.xml文件中添加以下代码片段：
//<dependency>
//<groupId>org.apache.commons</groupId>
//<artifactId>commons-collections4</artifactId>
//<version>4.4</version>
//</dependency>
//import org.apache.commons.collections4.map.AVLTree;
public class AVLTreeDemoMain {
    public static void main(String[] args) {
        AVLTreeDemo<Integer> tree = new AVLTreeDemo<>();

        tree.insert(5);
        tree.insert(10);
        tree.insert(3);
        tree.insert(7);
        tree.insert(8);
        tree.insert(1);

        System.out.println("Inorder Traversal:");
        tree.inorderTraversal();

        tree.delete(5);

        System.out.println("nAfter deleting 5:");
        tree.inorderTraversal();
    }
}