Java数据结构《二叉排序树的插入删除和查找》(难度系数100)

2023-12-13 22:40:17

一、前言:

? 这是怀化学院的:Java数据结构中的一道难度偏难(偏难理解)的一道编程题(此方法为博主自己研究与学习一名叫qing影的博主,问题基本解决,若有bug欢迎下方评论提出意见,我会第一时间改进代码,谢谢!) 后面其他编程题只要我写完,并成功实现,会陆续更新,记得三连哈哈! 所有答案供参考,不是标准答案,是博主自己研究的写法。(这一个题书上也有现成类似的代码,重要的是理解它的算法原理!)

二、题目要求如下:

(第 17 题) 二叉排序树的插入删除和查找(难度系数100)

二叉排序树的插入删除和查找

pre: 前序遍历
in: 中序遍历
post:后序遍历
insert: 插入,本题中不会出现相同的元素
delete: 删除,删除成功输出TRUE,没有该元素则输出FALSE,删除的方法是如果有左子树,以左子树中最大值作为新的树根,否则,以右子树最小值作为树根。
search: 查找,存在该元素输出YES, 否则输出NO
exit:退出
输入:
输入的第一行为整数 N
接下来一行为N个整数,你需要把这N个整数构建出相应的二叉排序树
之后是一组指令。

输出:
根据相应的指令进行输出。说明:遍历各元素之间用一个空格隔开。

样例输入:
10
31 15 9 5 4 7 8 50 42 2
pre
in
post
delete
15
delete
88
in
search
8
search
222
insert
15
pre
in
post
exit

样例输出:

31 15 9 5 4 2 7 8 50 42
2 4 5 7 8 9 15 31 42 50
2 4 8 7 5 9 15 42 50 31
TRUE
FALSE
2 4 5 7 8 9 31 42 50
YES
NO
31 9 5 4 2 7 8 15 50 42
2 4 5 7 8 9 15 31 42 50
2 4 8 7 5 15 9 42 50 31

注意:在样例中,我先把15删除掉了,然后再插入15,观察最开始的三个遍历,和最后的三次遍历,遍历结果是有区别的。

三、代码实现: (代码的做题原理全部在代码注释中)?

<1>因为学校的提交测试的网站:不能有自己创建的包的声明,不能有代码注释以及要把所有的操作放在同一个类中等等......,

补充:(首先我在学校提交的网站没有找到该题目,这个应该是最近新创的题,如果各位找到可以试一下不删除注释看能不能提交成功,若不行,请试一下删除所有的代码注释,代码在下方!!!!!!)

(1)我把所有的实现二叉排序树的操作放在了一个类中:?

提示:这里面最难理解的方法就是它的删除操作,就是很难很绕,一定要深思,而且我代码注释也不好讲解。所以在写之前一定要搞明白什么是二叉排序树,不能盲目下笔。还有在其插入元素也要注意。此题很多地方用到方法的递归调用以及循环,还有if...else..嵌套等等

import java.util.Scanner;

public class Main {
    //创建一个静态结点内部类,不然主方法用不了
    private static class Node {
        private int data;  //数据域
        private Node lChild;  //左孩子结点
        private Node rChild;  //右孩子结点

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

    //首先先创建该课树的一个空的根结点
    private static Node root = null;

    //插入元素操作(所有元素不会相同),要设为静态方法
    public static void insert(int data) {
        root = insert(root, data);
    }
    public static Node insert(Node node, int data) {
        if (node == null) {
            node = new Node(data);
        } else {
            //按照二叉排序的要求创建
            //若左子树不空,则左子树上所有结点的值均小于或等于它的根结点的值;
            //若右子树不空,则右子树上所有结点的值均大于或等于它的根结点的值;
            //左、右子树也分别为二叉排序树;
            if (data < node.data) {
                node.lChild = insert(node.lChild, data);
            } else if (data > node.data) {
                node.rChild = insert(node.rChild, data);
            }
        }
        return node;
    }

    //用来判断是否成功删除所要删除的元素
    private static boolean flag=false;
    //实现所有的删除操作
    public static boolean delete(int data){
        //首先要注意每次调用这个方法的时候,都要先把flag置成“false”,因为可能之前有进行过删除的操作
        flag=false;
        root=delete(root,data);  //从根开始查找并进行删除操作
        return flag;
    }
    public static Node delete(Node node,int data){
        //每次递归删除操作时首先要判断当前的"根"结点是否是空的,空的直接不进行操作返回"空"
        if(node!=null){
            //如果找到当前"根"结点的值等于要删除的值,就进行下方操作
            if(node.data==data){

                //首先在没有操作之前,因为找到了,那就代表可以删除,就把flag置为“true”,具体的删除操作就是后面要做的事了
                flag=true;
                //如果是叶子结点(就很简单,直接删除就行,不用去找合适的值替换当前要删除的"根"结点)
                if(node.lChild==null&&node.rChild==null){
                    //直接变成空,就是把它删掉了
                    node=null;
                }
                //就是按题目要求:如果有左子树,那么要找到左子树中的最大值作为新的"根"结点
                //原因就是:要满足删除后的树还是一颗排序二叉树
                else if(node.lChild!=null){
                    //创建一个标记:用来表示当前开始查找的结点(从左子树进入)
                    Node present = node.lChild;
                    //创建一个标记:用来存储当前结点的父结点
                    Node last =node.lChild;
                    //开始循环遍历向下:直到找到当前结点的左子树没有右子树为止(因为要找最大值:根据二叉排序树的创建原理要往其右子树找)
                    while(present.rChild!=null){
                        last=present;  //每次先记录当前标记,当最后循环结束时,它就是最后一个右子树的父结点了
                        present=present.rChild; //只要循环那条满足,就代表有右子树,那么就要更新下一个要查找的标记
                    }
                    //退出循环后,一定是当前的结点再也没有:没访问过的右孩子了
                    //先把之前要删除的"根"结点赋上找到的最大值
                    node.data=present.data;
                    //再处理那个被拿去给删去的"根"结点赋新值的结点
                    //首先就是如果找到的符合条件的值就是其左孩子的值,那"present"与"last"是不是没有变
                    if(present==last){
                        //注意其左孩子没有右孩子
                        node.lChild=present.lChild; //就是现在赋了新值的结点的左孩子是:原来找到最大值的结点的左孩子,因为它没有右孩子(代表"根"结点的左子树的值可以等于其"根"结点的值)
                    }
                    //这个的意思就是找到的最大值是其左子树中的右子树里的值
                    //删去该"根"结点后,那么被找到的那个最大值结点的父结点:应该把其右孩子结点变成最大值结点的左孩子(这个不好描述)
                    //因为它右孩子在循环时已经是最后的那个右孩子了(现在被拿去赋值,就相当于没右孩子了)
                    else if(present!=last){
                        last.rChild=present.lChild;
                    }

                }
                //就是按题目要求:如果有右子树,那么要找到右子树中的最小值作为新的"根"结点
                else if(node.rChild!=null){
                    //创建一个标记:用来表示当前开始查找的结点(从右子树进入)
                    Node present = node.rChild;
                    //创建一个标记:用来存储当前结点的父结点
                    Node last = node.rChild;
                    //开始循环遍历向下:直到找到当前结点的右子树没有左子树为止(因为要找最小值:根据二叉排序树的创建原理要往其左子树找)
                    while(present.lChild!=null){
                        last=present;  //每次先记录当前标记,当最后循环结束时,它就是最后一个左子树的父结点了
                        present=present.lChild; //只要循环那条满足,就代表有左子树,那么就要更新下一个要查找的标记
                    }
                    //退出循环后,一定是当前的结点再也没有:没访问过的左孩子了
                    //先把之前要删除的"根"结点赋上找到的最小值
                    node.data=present.data;
                    //再处理那个被拿去给删去的"根"结点赋新值的结点
                    //首先就是如果找到的符合条件的值就是其右孩子的值,那"present"与"last"是不是没有变
                    if(present==last){
                        //注意其右孩子没有左孩子
                        node.rChild=present.rChild; //就是现在赋了新值的结点的右孩子是:原来找到最小值的结点的右孩子,因为它没有左孩子(代表"根"结点的右子树的值可以等于其"根"结点的值)
                    }
                    //这个的意思就是找到的最小值是其右子树中的左子树里的值
                    //删去该"根"结点后,那么被找到的那个最小值结点的父结点:应该把其左孩子结点变成最小值结点的右孩子(这个不好描述)
                    //因为它左孩子在循环时已经是最后的那个左孩子了(现在被拿去赋值,就相当于没左孩子了)
                    else if(present!=last){
                        last.lChild=present.rChild;
                    }

                }

            }
            else if(data<node.data){
                //如果要删除的值小于当前"根"结点的值,就代表要从当前"根"结点的左子树开始去进行删除操作,一直找到要删除的"根"结点为止,再进行操作
                node.lChild=delete(node.lChild,data);
            }
            else if(data>node.data){
                //如果要删除的值打于当前"根"结点的值,就代表要从当前"根"结点的右子树开始去进行删除操作,一直找到要删除的"根"结点为止,再进行操作
                node.rChild=delete(node.rChild,data);
            }

        }
        return node;
    }

    //实现查找元素功能
    public static boolean search(int data){
        //首先是创建一个初始的查找结点
        Node curr = root;  //从最初的根结点开始
        while(curr!=null){  //条件是一直向下找,直到找到为止。如果到最后叶子结点也没有找到那就是不存在该元素
            if(curr.data==data){
                return true;
            }
            //如果要查找的值小于当前的"根"结点,那就向其左子树查
            else if(data<curr.data){
                curr=curr.lChild;
            }
            //如果要查找的值小于当前的"根"结点,那就向其左子树查
            else if(data>curr.data){
                curr=curr.rChild;
            }
        }
        return false;
    }


    //主方法测试输入
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        for (int i = 0; i < N; i++) {
            insert(sc.nextInt());
        }
        String command =sc.next();  //输入所要操作的所有指令
        while (!command.equals("exit")){  //只要输入的指令不是"exit",就不会退出对二叉排序树的操作
            if(command.equals("pre")){
                preOrder();  //进行前序遍历
            }else if(command.equals("in")){
                inOrder();  //进行中序遍历
            }else if(command.equals("post")){
                postOrder();  //进行后序遍历
            }else if(command.equals("insert")){
                insert(sc.nextInt());   //插入元素
            }else if(command.equals("delete")){
               delete(sc.nextInt());
               if(flag){
                   System.out.println("TRUE");
               }else{
                   System.out.println("FALSE");
               }
            }else if(command.equals("search")){
                if(search(sc.nextInt())){
                    System.out.println("YES");
                }else {
                    System.out.println("NO");
                }
            }
            command=sc.next();
        }
    }

    //实现前序遍历("根"结点 -> 左孩子 -> 右孩子)
    public static void preOrder() {
        preOrder(root);
        System.out.println();   //遍历完记得换行
    }
    public static void preOrder(Node node) {
        //首先判断传进来的"根结点"是否为空
        if (node != null) {
            //只要不为空就先输出当前"根结点"并继续遍历其左孩子,直到左孩子无左右孩子,再输出当前"根结点",再往前递归
            System.out.print(node.data+" ");
            preOrder(node.lChild);
            preOrder(node.rChild);
        }
    }

    //实现中序遍历(左孩子 -> "根"结点 ->右孩子)
    public static void inOrder() {
        inOrder(root);
        System.out.println();  //遍历完记得换行
    }
    public static void inOrder(Node node) {
        //首先判断传进来的"根结点"是否为空,然后先遍历左孩子,直到左孩子的左孩子为空,那就输出当前的"根结点",再遍历右孩子,再往前递归
        if (node != null) {
            inOrder(node.lChild);
            System.out.print(node.data+" ");
            inOrder(node.rChild);
        }
    }

    //实现后序遍历(左孩子 -> 右孩子 ->"根"结点 )
    public static void postOrder() {
        postOrder(root);
        System.out.println();  //遍历完记得换行
    }
    public static void postOrder(Node node) {
        //首先判断传进来的"根结点"是否为空,然后先遍历左孩子,直到左孩子的左右孩子为空,那就输出当前的"根结点",再往前递归
        if (node != null) {
            postOrder(node.lChild);
            postOrder(node.rChild);
            System.out.print(node.data+" ");
        }
    }

}

四、不同情况的代码测试运行结果:

<1>题目中的测试输入样例:(最好手打输入测试,直接复制可能格式问题导致报错!)

文章来源:https://blog.csdn.net/m0_74363339/article/details/134909106
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。