Java实现一颗二叉搜索树的增删查改操作

Java实现一颗二叉搜索树的增删查改操作：

树节点：

package test.tree;


public class TreeNode {

    private int val;
    private TreeNode left;
    private TreeNode right;

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

    public int getVal() {
        return val;
    }
    public void setVal(int val) {
        this.val = val;
    }
    public TreeNode getLeft() {
        return left;
    }
    public void setLeft(TreeNode left) {
        this.left = left;
    }
    public TreeNode getRight() {
        return right;
    }
    public void setRight(TreeNode right) {
        this.right = right;
    }

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

二叉搜索树：

package test.tree;


public class BinaryTree {

    private TreeNode root;

    public BinaryTree() {
        root = null;
    }
    public void insert(int val) {
        root = insert(root, val);
    }

    private TreeNode insert(TreeNode node, int val) {
        if (node == null) {
            node = new TreeNode(val);
        } else {
            if (val < node.getVal()) {
                node.setLeft(insert(node.getLeft(), val));
            } else {
                node.setRight(insert(node.getRight(), val));
            }
        }
        return node;
    }
    public void delete(int val) {
        root = delete(root, val);
    }
    private TreeNode delete(TreeNode node, int val) {
        if (node == null) {
            return null;
        }
        if (val < node.getVal()) {
            node.setLeft(delete(node.getLeft(), val));
        } else if (val > node.getVal()) {
            node.setRight(delete(node.getRight(), val));
        } else {
            if (node.getLeft() == null) {
                return node.getRight();
            } else if (node.getRight() == null) {
                return node.getLeft();
            }
            node.setVal(minValue(node.getRight()));
            node.setRight(delete(node.getRight(), node.getVal()));
        }
        return node;
    }
    private int minValue(TreeNode node) {
        int minVal = node.getVal();
        while (node.getLeft() != null) {
            minVal = node.getLeft().getVal();
            node = node.getLeft();
        }
        return minVal;
    }
    public TreeNode search(int val) {
        return search(root, val);
    }

    private TreeNode search(TreeNode node, int val) {
        if (node == null || node.getVal() == val) {
            return node;
        }
        if (val < node.getVal()) {
            return search(node.getLeft(), val);
        } else {
            return search(node.getRight(), val);
        }
    }
    public void modify(int oldVal, int newVal) {
        delete(oldVal);
        insert(newVal);
    }

    //    前序遍历（先遍历根节点，再遍历左子树和右子树）
    public static void preOrderTraversal(TreeNode root) {
        if (root != null) {
            System.out.print(root.getVal() + " ");
            preOrderTraversal(root.getLeft());
            preOrderTraversal(root.getRight());
        }
    }

    //    中序遍历（先遍历左子树，再遍历根节点和右子树）
    public static void inOrderTraversal(TreeNode root) {
        if (root != null) {
            inOrderTraversal(root.getLeft());
            System.out.print(root.getVal() + " ");
            inOrderTraversal(root.getRight());
        }
    }

    //    后序遍历（先遍历左子树和右子树，再遍历根节点）
    public static void postOrderTraversal(TreeNode root) {
        if (root != null) {
            postOrderTraversal(root.getLeft());
            postOrderTraversal(root.getRight());
            System.out.print(root.getVal() + " ");
        }
    }

    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.print("In-order traversal: ");
        inOrderTraversal(tree.root);
        System.out.println();
        System.out.println("Search for node with value 4: " + tree.search(4).getVal());

        tree.delete(5);
        System.out.print("In-order traversal: ");
        inOrderTraversal(tree.root);
        System.out.println();
        tree.modify(4, 9);
        System.out.print("In-order traversal: ");
        inOrderTraversal(tree.root);
        System.out.println();
    }
}

测试：

package test.tree;


public class TreeTest {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.setLeft(new TreeNode(2));
        root.setRight(new TreeNode(3));
        root.getLeft().setLeft(new TreeNode(4));
        root.getLeft().setRight(new TreeNode(5));
        System.out.println(root);

        System.out.print("Pre-order traversal: ");
        preOrderTraversal(root);
        System.out.println();
        System.out.print("In-order traversal: ");
        inOrderTraversal(root);
        System.out.println();
        System.out.print("Post-order traversal: ");
        postOrderTraversal(root);
    }

//    前序遍历（先遍历根节点，再遍历左子树和右子树）
    public static void preOrderTraversal(TreeNode root) {
        if (root != null) {
            System.out.print(root.getVal() + " ");
            preOrderTraversal(root.getLeft());
            preOrderTraversal(root.getRight());
        }
    }

//    中序遍历（先遍历左子树，再遍历根节点和右子树）
    public static void inOrderTraversal(TreeNode root) {
        if (root != null) {
            inOrderTraversal(root.getLeft());
            System.out.print(root.getVal() + " ");
            inOrderTraversal(root.getRight());
        }
    }

//    后序遍历（先遍历左子树和右子树，再遍历根节点）
    public static void postOrderTraversal(TreeNode root) {
        if (root != null) {
            postOrderTraversal(root.getLeft());
            postOrderTraversal(root.getRight());
            System.out.print(root.getVal() + " ");
        }
    }
}