二叉排序树的插入删除和查找(数据结构实训)(难度系数100)-Toy模板网

这篇具有很好参考价值的文章主要介绍了二叉排序树的插入删除和查找(数据结构实训)(难度系数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，观察最开始的三个遍历，和最后的三次遍历，遍历结果是有区别的。文章来源地址https://www.toymoban.com/news/detail-822175.html

import java.util.*;

public class Xingyuxingxi {
    static TreeNode root;
    static boolean pd;//定义全局变量，就无需导入到方法里面
    public static class TreeNode{
        TreeNode lc;
        TreeNode rc;
        int item;
        public TreeNode(int item) {
            this.item=item;
        }
    }
    public static TreeNode insert(TreeNode root,int item) {
        if(root==null) {//如果要插入的位置为空，则直接加入新结点
            root=new TreeNode(item);
        }
        else if(item > root.item) {//如果插入的数大该结点的数则进该结点的右子树找位置
            root.rc=insert(root.rc,item);
        }
        else if(item< root.item) {//如果插入的数小于该结点的数则进该结点的左子树找位置
            root.lc=insert(root.lc,item);
        }
        return root;
    }
    public static TreeNode delete(TreeNode root,int item){
        if(root==null)
        {
            return null;
        }
    if(root.item==item) {
        pd=true;
        if (root.lc == null && root.rc == null) {//如果删除的结点左子树和右子树都为空
            root = null;//则直接删除该结点
        } else if (root.lc != null) {//如果删除结点的左子树不为空，应该在左子树中找到最大的结点
            TreeNode node1 = root.lc;//储存该结点的左子树结点
            TreeNode node2 = root.lc;//储存该结点的左子树结点
            while (node1.rc != null) {//最大的值肯定在左子树结点的右子树上，如果没有则该结点就是最大值，因为二叉搜索树要求左子树小于前结点，右子树大于前结点
                node2 = node1;
                node1 = node1.rc;
            }//如果进了循环，则node1和node2不相等
            if (node1 != node2) {//如果不相等表示，则node2储存的将会是node1的父亲结点，node1储存的是node2的右子树结点
                node2.rc = node1.lc;//让node2右子树结点连接node1的左子树结点，此时node1已经是最大的，所以没有右子树
                root.item = node1.item;//删除结点用删除结点左子树的最大值替换
            } else {//如果两个储存的结点相等，则该结点无右结点，只需要将删除结点替换为该结点并且连接其原本的左子树结点即可
                root.item = node1.item;
                root.lc = node1.lc;
            }
        } else {//如果删除结点的右子树不为空，应该在右子树中找到最小的结点
            TreeNode node1 = root.rc;//储存该结点的左子树结点
            TreeNode node2 = root.rc;//储存该结点的左子树结点
            while (node1.lc != null) {//最小的值肯定在右子树结点的左子树上，如果没有则该结点就是最小值，因为二叉搜索树要求左子树小于前结点，右子树大于前结点
                node2 = node1;
                node1 = node1.lc;
            }//如果进了循环，则node1和node2不相等
            if (node2 != node1) {//如果不相等表示，则node2储存的将会是node1的父亲结点，node1储存的是node2的左子树结点
                node2.lc = node1.rc;//让node2左子树结点连接node1的右子树结点，此时node1已经是最小的，所以没有左子树
                root.item = node1.item;//删除结点用删除结点左子树的最大值替换
            } else {//如果两个储存的结点相等，则该结点无左结点，只需要将删除结点替换为该结点并且连接其原本的右子树结点即可
                root.item = node1.item;
                root.rc = node1.rc;
            }
        }
    }
    else if(item<root.item){//如果删除的结点比该结点小，进左子树找
        root.lc=delete(root.lc,item);
    }
    else {//如果大则进右子树找
        root.rc=delete(root.rc,item);
    }
    return root;
    }
    public static void search(int item) {
        TreeNode node = root;
        while(node!=null) {
            if(item<node.item){//如果小于该结点则进左边找
                node=node.lc;
            } else if (item>node.item){//大于则进右边找
                node=node.rc;
            }else {//找到了就退出
                pd=true;//标记为true
                break;
            }
        }
    }
    public static void pre(TreeNode root) {//先序遍历递归顺序，中左右
        if(root==null) {//如果根结点为空则返回
            return;
        }
        System.out.print(root.item+" ");//中
        pre(root.lc);//左
        pre(root.rc);//右
    }
    public static void in(TreeNode root) {//中序遍历递归顺序，左中右
        if(root==null) {//如果根结点为空则返回
            return;
        }
        in(root.lc);//左
        System.out.print(root.item+" ");//中
        in(root.rc);//右
    }
    public static void post(TreeNode root) {//后序遍历递归顺序，左右中
        if(root==null) {//如果根结点为空则返回
            return;
        }
        post(root.lc);//左
        post(root.rc);//右
        System.out.print(root.item+" ");//中
    }
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        root=null;//初始化
        for (int i = 0; i < n; i++) {
            int item=sc.nextInt();
            root=insert(root,item);//就是插入操作
        }
        String str;
        while(sc.hasNext()) {
            str=sc.next();
            if(str.equals("exit")) {//退出
                break;
            } else if(str.equals("insert")) {//插入
                int item=sc.nextInt();
                root=insert(root,item);
            } else if(str.equals("delete")) {//删除
            int item=sc.nextInt();
            pd=false;
            root=delete(root,item);
            if(pd){//如果成功删除"TRUE"
                System.out.println("TRUE");
            }else {//否则"FALSE",实际上只有没有要删除的数才为"FALSE"
                System.out.println("FALSE");
            }
            } else if(str.equals("search")) {//查找
            int item= sc.nextInt();
            pd=false;
            search(item);
            if(pd){//找到则为"YES"
                System.out.println("YES");
            } else {//否则为"NO"
                System.out.println("NO");
            }
            } else if(str.equals("pre")) {//先序遍历
            pre(root);
            System.out.println();
            } else if(str.equals("in")) {//中序遍历
            in(root);
            System.out.println();
            } else if(str.equals("post")) {//后序遍历
            post(root);
            System.out.println();
            }
        }
    }
}

到了这里，关于二叉排序树的插入删除和查找(数据结构实训)(难度系数100)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！