java建立BinarySearchTree(二叉搜索树)的实例和一些方法

BinarySearchTree.java

import java.util.Scanner;

public class BinarySearchTree {
    //定义根节点
    private static Node root;

    // 定义节点类
    private static class Node {
        int key;//节点值
        Node left;//左节点
        Node right;//右节点
        //初始化节点
        Node(int key) {
            this.key = key;
        }
        //获取节点值
        public int getKey(){
            return key;
        }
    }

    //中序遍历
    public static void InorderTraversal() {
        StringBuilder stringBuilder = new StringBuilder();
        InorderTraversal(root, stringBuilder);
        System.out.println(stringBuilder);
    }

    // 递归中序遍历
    private static void InorderTraversal(Node node, StringBuilder stringBuilder) {
        if (node != null) {
            InorderTraversal(node.left, stringBuilder);//遍历左子树
            stringBuilder.append(node.key).append(" ");//输出节点值
            InorderTraversal(node.right, stringBuilder);//遍历右子树
        }
    }

    // 增加节点
    protected static Node Insert(Node node, int key) {
        if (node == null) {
            return new Node(key);
        }
        if (key < node.key) {
            node.left = Insert(node.left, key);
        } else if (key > node.key) {
            node.right = Insert(node.right, key);
        }
        return node;
    }

    // 插入数组元素
    public static void InsertArray(int[] nums) {
        //遍历数组，对未出现在树中的元素进行插入
        for (int num : nums) {
            if (Search(num) == null) {
                root = Insert(root, num);
            }
        }
    }

    // 寻找节点
    protected static Node Search(int key) {
        Node node = root;
        //从根节点开始遍历
        while (node != null) {
            if (key == node.key) {
                return node;
            } else if (key < node.key) {
                node = node.left;
            } else {
                node = node.right;
            }
        }
        return null;
    }

    // 查找最小节点
    private static Node FindMin(Node node) {
        //节点为空则返回空
        if (node == null) {
            return null;
        }
        //没有左子树，则该节点为最小节点
        if (node.left == null) {
            return node;
        }
        //向左节点继续查找
        return FindMin(node.left);
    }

    // 删除节点
    public static void Delete(int key) {
        root = Delete(root, key);
    }

    // 递归删除节点
    protected static Node Delete(Node node, int key) {
        //未找到要删除的节点
        if (node == null) {
            return null;
        }
        //小于当前节点值，则进入左子树继续查找
        if (key < node.key) {
            node.left = Delete(node.left, key);
            //大于当前节点值，则进入右子树继续查找
        } else if (key > node.key) {
            node.right = Delete(node.right,key);
        } else {
            if (node.left == null) {
                return node.right;
            } else if (node.right == null) {
                return node.left;
            } else {
                //查找右子树中的最小节点
                Node minNode = FindMin(node.right);
                //将该节点替换要删除的节点
                node.key = minNode.key;
                //递归地在右子树中删除该最小节点
                node.right = Delete(node.right, minNode.key);
            }
        }
        return node;
    }

    // 修改节点值
    public static void Modify(int oldKey, int newKey) {
        //查找要修改的节点
        Node node = Search(oldKey);
        if (node == null) {
            System.out.println("要修改的节点不存在！");
            return;
        }
        if (Search(newKey) != null) {
            System.out.println("该节点值已经存在！");
            return;
        }
        //删除原来的节点
        Delete(oldKey);
        //插入新节点
        root = Insert(root, newKey);
        //遍历输出修改后的树
        InorderTraversal();
    }

    //查询指定节点的父节点
    private static Node FindParent(Node node,int key){
        if (node != null){
            if ((node.left != null && node.left.key == key) ||(node.right != null && node.right.key == key)){
                return node;
            }else {
                Node leftResult = FindParent(node.left,key);
                if (leftResult != null){
                    return leftResult;
                }else {
                    return FindParent(node.right,key);
                }
            }
        }
        return null;
    }

    //successor查找
    private static Node Successor(Node node){
        //右子树上存在节点，则返回右子树上的最小值
        if (node.right != null){
            return FindMin(node.right);
        }
        //右子树为空，则查找其父节点，直至该节点为其父节点的左子节点
        Node parent = FindParent(root,node.key);
        while (parent != null && node == parent.right){
            node = parent;
            parent = FindParent(root,parent.key);
        }
        return parent;
    }

    //左旋
    public static void LeftRotate(int key){
        //找到要左旋的节点
        Node node = Search(key);
        if (node == null){
            System.out.println("要旋转的节点不存在！");
            return;
        }
        Node parent = FindParent(root,key);
        //当前节点若无右子树，则无法左旋
        if (node.right == null){
            System.out.println("当前节点没有右子树,无法进行左旋操作！");
            return;
        }
        //记录右子节点
        Node rightNode = node.right;
        //将右子节点的左子树挂到当前接节点的右子树上
        node.right = rightNode.left;
        //将当前节点作为右子节点的左子节点
        rightNode.left = node;
        //若当前节点是根节点
        if (parent == null){
            root = rightNode;
        }else {
            if (parent.left == node){
                parent.left = rightNode;
            }else {
                parent.right = rightNode;
            }
        }
        //遍历输出左旋后的树
        InorderTraversal();
    }

    //右旋
    private static void RightRotate(int key){
        //找到要右旋的节点
        Node node = Search(key);
        if (node == null){
            System.out.println("要旋转的节点不存在！");
            return;
        }
        //若当前节点无左子树，则无法右旋
        Node parent = FindParent(root,key);
        if (node.left == null){
            System.out.println("当前节点没有左子树，无法进行右旋操作！");
            return;
        }
        //记录左子节点
        Node leftNode = node.left;
        //将左子节点的右子树挂到当前接节点的左子树上
        node.left = leftNode.right;
        //将当前节点作为左子节点的右子节点
        leftNode.right = node;
        // 如果当前节点是根节点
        if (parent == null) {
            root = leftNode;
        } else {
            // 如果当前节点是父节点的左子节点
            if (parent.left == node) {
                parent.left = leftNode;
            } else { // 如果当前节点是父节点的右子节点
                parent.right = leftNode;
            }
        }
        //遍历输出旋转后的树
        InorderTraversal();
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入数组中的元素个数: ");
        int n = sc.nextInt();
        int[] nums = new int[n];
        System.out.println("请输入数组包含的元素值，以空格符隔开: ");
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        BinarySearchTree.InsertArray(nums);
        InorderTraversal();

        System.out.println("请输入要进行的操作(增加:I,删除:D,查找:S,修改:M,查找后继:SU,左旋:LR,右旋:RR,退出:Q): ");
        String operation = sc.next().toUpperCase(); // 将输入转化为大写形式
        while (!operation.equals("Q")) {
            if (operation.equals("I")) {
                System.out.println("请输入需要增加的节点值: ");
                int key = sc.nextInt();
                if (Search(key) != null) {
                    System.out.println("该节点已存在！");
                } else {
                    root = Insert(root, key);
                    System.out.println("插入成功！");
                    InorderTraversal();
                }
            } else if (operation.equals("D")) {
                System.out.println("请输入要删除的节点值: ");
                int key = sc.nextInt();
                Node node = Search(key);
                if (node != null) {
                    root = Delete(root, key);
                    System.out.println("删除成功！");
                    InorderTraversal();
                } else {
                    System.out.println("要删除的节点不存在！");
                }
            } else if (operation.equals("S")) {
                System.out.println("请输入要查找的节点值: ");
                int key = sc.nextInt();
                Node node = Search(key);
                if (node != null) {
                    System.out.println("该节点存在！");
                } else {
                    System.out.println("该节点不存在！");
                }
            } else if (operation.equals("M")) {
                System.out.println("请输入要修改的节点值: ");
                int oldKey = sc.nextInt();
                System.out.println("请输入新的节点值: ");
                int newKey = sc.nextInt();
                Modify(oldKey, newKey);
            }else if (operation.equals("SU")){
                System.out.println("请输入要查找后继节点的节点值: ");
                int key = sc.nextInt();
                Node successor = Successor(Search(key));
                if (successor == null){
                    System.out.println("该节点没有后继节点！");
                }else {
                    System.out.println("后继节点的值为: " + successor.getKey());
                }
            } else if (operation.equals("LR")) {
                System.out.println("请输入要左旋的节点值: ");
                int key = sc.nextInt();
                LeftRotate(key);
            } else if (operation.equals("RR")) {
                System.out.println("请输入要右旋的节点值: ");
                int key = sc.nextInt();
                RightRotate(key);
            } else {
                System.out.println("输入错误，请重新输入: ");
            }
            System.out.println("请输入要进行的操作(插入:I,删除:D,查找:S,修改:M,查找后继:SU,左旋:LR,右旋:RR,退出:Q): ");
            operation = sc.next().toUpperCase(); // 将输入转化为大写形式
        }
    }
}