1、二叉樹：

package com.datastructure.tree;
//一個常用的第三方庫是Apache Commons Collections，它提供了一個名為BinaryTree的類，用于表示二叉樹。
//可以使用org.apache.commons.collections4.BinaryTree類創(chuàng)建二叉樹和進行操作。
//可以在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;
        }
    }

    // 插入節(jié)點
    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、平衡二叉樹：文章來源地址http://www.zghlxwxcb.cn/news/detail-854199.html

package com.datastructure.tree;
//平衡樹
//AVLTree是一個泛型類，可以存儲任意實現(xiàn)了Comparable接口的類型。
//在AVLTree類中，使用Node類來表示樹節(jié)點，并在節(jié)點中保存了節(jié)點值、左子節(jié)點、右子節(jié)點和節(jié)點高度。
//在插入操作中，使用遞歸的方式在樹中查找合適的位置插入新節(jié)點，并在返回時重新平衡樹。
//在插入節(jié)點之后，檢查當(dāng)前節(jié)點的平衡因子，如果超出范圍，則通過旋轉(zhuǎn)操作來恢復(fù)平衡。
//除了插入操作之外，還可以實現(xiàn)其他操作，例如刪除節(jié)點、查找節(jié)點、遍歷等。
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; // 不允許插入重復(fù)的值
        }

        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();
    }
}

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)之二叉樹和平衡二叉樹的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！