精华内容
下载资源
问答
  • 二叉排序树删除节点

    2021-04-27 16:37:09
    删除节点总共有三种情况 删除是叶子结点 删除只有一颗子树的节点 删除有两个子树的节点 第一种情况思路 1.先去找到要删除的节点 targetNode 2.找到tar的父节点 3.确定tar是父节点的左子节点还是右子节点 4....

    删除节点总共有三种情况

    1. 删除是叶子结点
    2. 删除只有一颗子树的节点
    3. 删除有两个子树的节点
    • 第一种情况思路

    1.先去找到要删除的节点 targetNode
    2.找到tar的父节点
    3.确定tar是父节点的左子节点还是右子节点
    4.根据前面情况来删除

    • 第二种情况

    1.先去找到要删除的节点 targetNode
    2.找到tar的父节点
    3.确定tar有左子节点还是右子节点
    4.tar是parentNode的左子节点还是右子节点
    5.如果tar有左子节点
    5.1 tar是partner的左子节点
    parentNode.left=tar.left
    5.2 tar是partner的右子节点
    parentNode.right=tar.left
    6. 如果tar有右子节点
    6.1 tar是partner的左子节点
    parentNode.left =tar.right
    6.2 tar是partner的右子节点
    parentNode.right =tar.right

    • 第三种情况

    1.先去找到要删除的节点 targetNode
    2.找到tar的父节点
    3.从tar的右子树找到最小值的节点(如果是从左子树找找所有节点中最大的值)
    4.用一个临时变量存储这个最小值(最大值)
    5.删除找到的这个极值
    6.tar.val=temp

    package com.cl.TreeCon.BinarySortTree;
    
    public class BinarySortTreeDemo {
        public static void main(String[] args) {
            int[] arr = {7, 3, 10, 12, 5, 1, 9, 0};
            BinarySortTree binarySortTree = new BinarySortTree();
            for (int i = 0; i < arr.length; i++) {
                binarySortTree.add(new Node(arr[i]));
            }
            System.out.println("中序遍历二叉排序树");
            binarySortTree.infixOrder();
            binarySortTree.delNode(3);
            System.out.println("删除节点后,中序遍历二叉排序树");
            binarySortTree.infixOrder();
        }
    }
    
    //创建二叉排序树
    class BinarySortTree {
        Node root;
    
        //查找该节点
        public Node search(int value) {
            if (root == null) {
                return null;
            } else {
                return root.search(value);
            }
        }
    
        //查找父节点
        public Node searchParent(int value) {
            if (root == null) {
                return null;
            } else {
                return root.searchParent(value);
            }
        }
    
        /**
         * 1.传入要删除的有两个子树的节点
         * 2.找到以该节点为根节点的最小节点的值
         * 3.删除这个最小节点并返回
         *
         * @param node 传入的节点(有两个子树要删除的节点)
         * @return 返回以该节点为根节点的最小节点的值
         */
        public int delRightTreeMin(Node node) {
            Node tempNode = node;
            //找到最小节点值
            while (tempNode.left != null) {
                tempNode = tempNode.left;
            }
            delNode(tempNode.value);
            return tempNode.value;
        }
    
        public void delNode(int value) {
            if (root == null) {
                return;
            } else {
                //先去找到要删除的节点
                Node targetNode = search(value);
                //没有找到要删除的叶子结点
                if (targetNode == null) {
                    return;
                }
                //判断要删除的节点是否是根节点,如果是直设置this.root.value=null
                if (root.left == null && root.rigth == null) {
                    return;
                }
                Node parentNode = searchParent(value);
                if (targetNode.rigth == null && targetNode.left == null) {
                    if (parentNode.rigth != null && parentNode.rigth.value == value) {
                        parentNode.rigth = null;
                    } else if (parentNode.left != null && parentNode.left.value == value) {
                        parentNode.left = null;
                    }
                } else if (targetNode.left != null && targetNode.rigth != null) {
                    int min = delRightTreeMin(targetNode.left);
                    targetNode.value = min;
                } else { // 删除只有一个节点
                    //要删除的节点只有右节点
                    if (targetNode.rigth != null) {
                        if (parentNode.left.value == value) {//该节点是父节点的左节点
                            parentNode.left = targetNode.rigth;
                        } else {//该节点是父节点的右节点
                            parentNode.rigth = targetNode.rigth;
                        }
                    } else {
                        //要删除的节点只有左节点
                        if (parentNode.left.value == value) { //该节点是父节点的左节点
                            parentNode.left = targetNode.left;
                        } else {//该节点是父节点的右节点
                            parentNode.rigth = targetNode.left;
                        }
                    }
                }
            }
        }
    
        public void add(Node node) {
            if (root == null) {
                root = node;
            } else {
                root.add(node);
            }
        }
    
        //中序遍历
        public void infixOrder() {
            if (root != null) {
                root.infixOrder();
            } else {
                System.out.println("二叉排序树为空");
            }
        }
    
    }
    
    class Node {
        int value;
        Node left;
        Node rigth;
    
        public Node(int value) {
            this.value = value;
        }
    
        /**
         * 查找要删除的节点
         *
         * @param value 查找要删除节点的值
         * @return
         */
        public Node search(int value) {
            if (this.value == value) {
                return this;
            } else if (value < this.value) {
                //如果左子节点为空
                if (this.left == null) {
                    return null;
                }
                return this.left.search(value);
            } else {
                if (this.rigth == null) {
                    return null;
                }
                return this.rigth.search(value);
            }
        }
    
        //查找要删除节点的父节点
        public Node searchParent(int value) {
            if ((this.rigth != null && this.rigth.value == value) ||
                    (this.left != null && this.left.value == value)) {
                return this;
            } else {
                if (this.value > value && this.left != null) {
                    return this.left.searchParent(value);
                } else if (this.value < value && this.rigth != null) {
                    return this.rigth.searchParent(value);
                } else {
                    return null;
                }
            }
        }
    
        @Override
        public String toString() {
            return "Node{" +
                    "value=" + value +
                    '}';
        }
    
        public void add(Node node) {
            if (node == null) {
                return;
            }
            //判断当前节点值与,当前节点根节点的值比较
            if (node.value < this.value) {
                if (this.left == null) {
                    this.left = node;
                } else {
                    this.left.add(node);
                }
            } else {//添加的值如果大于当前节点的值
                if (this.rigth == null) {
                    this.rigth = node;
                } else {
                    this.rigth.add(node);
                }
            }
        }
    
        //中序遍历
        public void infixOrder() {
            if (this.left != null) {
                this.left.infixOrder();
            }
            System.out.println(this);
            if (this.rigth != null) {
                this.rigth.infixOrder();
            }
        }
    
    }
    
    

    结果

    中序遍历二叉排序树
    Node{value=0}
    Node{value=1}
    Node{value=3}
    Node{value=5}
    Node{value=7}
    Node{value=9}
    Node{value=10}
    Node{value=12}
    删除节点后,中序遍历二叉排序树
    Node{value=1}
    Node{value=0}
    Node{value=5}
    Node{value=7}
    Node{value=9}
    Node{value=10}
    Node{value=12}

    展开全文
  • 什么是二叉排序树(BST) 二叉排序树(Binary Sort Tree),又称二叉查找树(Binary Search Tree),亦称二叉搜索树。在一般情况下,查询效率比链表结构要高。 要求:对于二叉树中的任何一个非叶子结点,要求左子结点...

    二叉排序树(BST)

    1. 简介

    • 为什么使用二叉排序树

      对于顺序存储的二叉树:不排序-查找/删除/插入困难

      ​ 排序-删除/插入困难

      链式存储的二叉树:是否排序-都会查找困难(每次都需要从头结点开始找)

      而二叉排序树就解决了以上问题

    • 什么是二叉排序树

      百度百科定义:二叉排序树(Binary Sort Tree),又称二叉查找树(Binary Search Tree),亦称二叉搜索树。在一般情况下,查询效率比链表结构要高。

      要求: 对于二叉树中的任何一个非叶子结点,要求左子结点比当前结点值小,右子结点比当前结点值大。

    举例:

    需求-将如下数字 {7,3,11,13,5,1,9} 变成一颗二叉排序树

    实现思路:将第一个数作为根节点,依次比较,比它大的放右子节点,小的放子节点

    ​ 如果子节点还有子节点,那么就需要接着往下比较,直到找到一个合适的位置,如下图

    在这里插入图片描述

    如果我们想插入任意一个数字,比如插入10

    比较过程:和7比较->和11比较->和9比较->插入到9的右子节点

    2. 代码实现

    2.1 涉及的操作

    add() 增加结点-使其变成一颗二叉排序树

    midShow() 中序遍历输出二叉排序树-使用中序遍历刚好能够输出排序好的序列

    search() 查找节点-输入value,如果找到返回value

    delete() 删除节点-只删除传入的目标节点,其他结点不删除并且删除后还是一颗二叉排序树

    情况一: 删除的节点是叶子结点

    ​ 只需切断父节点和删除节点的联系即可

    情况二: 删除节点有一颗子树:左子树或右子树

    ​ 需要用删除节点的子树替换掉目标结点, 如:删除节点是left,它的子树是left parent.left=target.left

    情况三: 删除节点有两棵子树,左子树和右子树

    ​ 删除节点的左子树中结点值都小于删除节点,右子树都大于删除节点

    ​ 要删除目标节点,我们要找到可以替代它位置的节点,而这个结点就是左子树最大的或者右子树最小的

    ​ Way1:删除目标节点左子树中最大的结点并存储它的value,用value替换掉目标节点value

    ​ Way2:删除目标节点右子树中最小的结点并存储它的value,用value替换掉目标节点value

    ​ (以下我们采用方式二)

    2.2 代码

    BinarySortTree.java

    //二叉排序树
    public class BinarySortTree {
        Node root;
        //添加节点
        public void add(Node node){
            //第一次进入方法时,是一颗空树,设置为根节点root
            if(root==null){
                root=node;
            }else{
                //调用节点的add方法
                root.add(node);
            }
        }
        //中序遍历,输出二叉排序树结果
        public void midShow(){
            if(root!=null){
                root.midShow(root);
            }
        }
        //查找节点
        public Node search(int value){
            if(root!=null){
                return root.search(value);
            }
            return null;
        }
        //删除结点
        public void delete(int value){
            if(root==null){
                return;
            }
            root.delete(value);
        }
        //查找父节点
        public Node SearchParent(int value){
            if(root!=null){
                return root.searchParent(value);
            }
            return null;
        }
    }
    

    Node.java

    public class Node {
        int value;
        Node left;
        Node right;
    
        public Node(int value) {
            this.value = value;
        }
    
        //添加节点
        public void add(Node node) {
            //小于当前结点值
            if(node.value<this.value){
                //往左节点查找
                if(this.left==null){
                    this.left=node;
                    return;
                }
                //没有找到继续往下递归查找
                this.left.add(node);
            }
            //大于当前结点值
            if(node.value>this.value){
                //往右节点查找
                if(this.right==null){
                    this.right=node;
                    return;
                }
                //没有找到继续往下递归查找
                this.right.add(node);
            }
        }
        //中序遍历
        public void midShow(Node node) {
            if(node==null){
                return;
            }
            //遍历左儿子
            midShow(node.left);
            //输出当前值
            System.out.print(node.value+" ");
            //遍历右儿子
            midShow(node.right);
        }
    
        //查找节点
        public Node search(int value) {
            //找到节点直接返回
            if(this.value==value){
                return this;
            }
            //要查找的value比当前小,查找左节点
            else if(value<this.value){
                if(this.left==null){
                    return null;
                }
                return this.left.search(value);
            }
            //要查找的value比当前大,查找右节点
            else if(value>this.value){
                if(this.right==null){
                    return null;
                }
                return this.right.search(value);
            }
            return null;
        }
        //删除结点
        public void delete(int value) {
            Node target=search(value);
            if(target==null){
                return;
            }
            //找到父节点
            Node parent = searchParent(value);
            //如果删除的节点是叶子节点
            if(target.left==null&&target.right==null){
                if(parent.left==target){
                    parent.left=null;
                }else{
                    parent.right=null;
                }
    
            //删除的节点有左右两棵子树
            }else if(target.left!=null&&target.right!=null){
                //删除目标节点右子树中最小的结点,并存储最小节点值
                int rightMin= findRightMin(target.right);
                //替换目标节点value,这是就相当于我们删除了目标元素
                target.value=rightMin;
    
            //删除的节点有左子树或右子树
            }else{
                //目标节点是父节点的左节点
                if(target==parent.left){
                    //目标元素有左子树
                    if(target.left!=null){
                        parent.left=target.left;
                    //目标元素有右子树
                    }else{
                        parent.left=target.right;
                    }
                //目标节点是父节点的右节点
                }else{
                    if(target.right!=null){
                        parent.right=target.right;
                    }else{
                        parent.right=target.left;
                    }
                }
            }
        }
        //找到并删除右子树中最小节点值的节点返回该节点的值
        public int findRightMin(Node right) {
            //一直找左儿子,直到为空
            while(right.left!=null){
                right=right.left;
            }
            int value=right.value;
            //这里我们直接调用delete方法,必定是叶子结点,这种情况我们上面已经考虑到
            delete(value);
            return value;
        }
    
        //查找父节点
        public Node searchParent(int value) {
            //如果当前节点的左儿子或右儿子是目标节点,找到父节点,返回
            if((this.left!=null&&this.left.value==value)||(this.right!=null&&this.right.value==value)){
                return this;
            }else{
                //往左子树递归查找
                if(value<this.value&&this.left!=null){
                    return this.left.searchParent(value);
                //往右子树递归查找
                }else if(value>this.value&&this.right!=null){
                    return this.right.searchParent(value);
                }
            }
            return null;
        }
    }
    
    

    测试类 TestBinarySortTree.java

    public class TestBinarySortTree {
        public static void main(String[] args) {
            //二叉排序树的组成节点值
            int[] arr={7,3,11,13,5,1,9};
            //创建二叉排序树
            BinarySortTree binarySortTree = new BinarySortTree();
            //遍历给二叉排序树添加节点
            for (int value : arr) {
                binarySortTree.add(new Node(value));
            }
            //遍历输出二叉排序树(中序遍历)
            System.out.println("二叉排序树遍历结果:");
            binarySortTree.midShow();
            //查找节点
            System.out.println("\n查找value=9的结点:"+binarySortTree.search(9).value);
            System.out.println("查找value=10的结点:"+binarySortTree.search(10));
    
            //测试删除节点
            binarySortTree.delete(7);//删除有两棵子树的节点7
            System.out.print("删除结点7:");
            binarySortTree.midShow();
            System.out.print("\n删除结点1:");
            binarySortTree.delete(1);//删除叶子结点1
            binarySortTree.midShow();
            System.out.print("\n删除结点3:");
            binarySortTree.delete(3);//删除只有一颗子树的节点3
            binarySortTree.midShow();
        }
    }
    

    2.3 运行结果

    二叉排序树遍历结果:
    1 3 5 7 9 11 13 
    查找value=9的结点:9
    查找value=10的结点:null
    删除结点71 3 5 9 11 13 
    删除结点13 5 9 11 13 
    删除结点35 9 11 13 
    
    展开全文
  • 二叉排序树删除

    2021-03-25 20:50:06
    二叉排序树删除情况比较复杂,有下面三种情况需要考虑。 1 删除叶子节点。(比如:2,5,9,12)。 2 删除只有一颗子树的节点。(比如:1)。 3 删除有两颗子树的节点.。(比如:7,3,10 )。 二 思路分析 对删除结点...

    一 点睛

    二叉排序树的删除情况比较复杂,有下面三种情况需要考虑。

    1 删除叶子节点。(比如:2,5,9,12)。

    2 删除只有一颗子树的节点。(比如:1)。

    3 删除有两颗子树的节点.。(比如:7,3,10 )。

    二 思路分析

    对删除结点的有三种情况需要分析。

    第一种情况:删除叶子节点。(比如:2,5,9,12)。

    (1) 需求先去找到要删除的结点 targetNode。

    (2) 找到 targetNode 的 父结点 parent。

    (3) 确定 targetNode 是 parent 的左子结点还是右子结点。

    (4) 根据前面的情况来对应删除。

    左子结点 parent.left = null

    右子结点 parent.right = null

    第二种情况: 删除只有一颗子树的节点。(比如:1)。

    (1) 需求先去找到要删除的结点 targetNode。

    (2) 找到 targetNode 的 父结点 parent。

    (3) 确定 targetNode 的子结点是左子结点还是右子结点。

    (4) targetNode 是 parent 的左子结点还是右子结点。

    (5) 如果 targetNode 有左子结点

    a 如果 targetNode 是 parent 的左子结点

    parent.left = targetNode.left;

    b 如果 targetNode 是 parent 的右子结点

    parent.right = targetNode.left;

    (6) 如果 targetNode 有右子结点

    a 如果 targetNode 是 parent 的左子结点

    parent.left = targetNode.right;

    b 如果 targetNode 是 parent 的右子结点

    parent.right = targetNode.right

    第三种情况:删除有两颗子树的节点.。(比如:7,3,10 )。

    (1) 需求先去找到要删除的结点 targetNode。

    (2) 找到 targetNode 的 父结点 parent。

    (3) 从 targetNode 的右子树找到最小的结点。

    (4) 用一个临时变量, 将最小结点的值保存到 temp

    (5) 删除该最小结点

    (6) targetNode.value = temp

    三 代码

    package com.atguigu.binarysorttree;
    
    /**
    * @className: BinarySortTreeDemo
    * @description: 二叉排序树
    * @date: 2021/3/22
    * @author: cakin
    */
    public class BinarySortTreeDemo {
        /**
         * 功能描述:二叉排序树测试
         *
         * @param args 命令行
         * @author cakin
         * @date 2021/3/22
         */
        public static void main(String[] args) {
            int[] arr = {7, 3, 10, 12, 5, 1, 9, 2};
            BinarySortTree binarySortTree = new BinarySortTree();
            // 循环的添加结点到二叉排序树
            for (int i = 0; i < arr.length; i++) {
                binarySortTree.add(new Node(arr[i]));
            }
            // 中序遍历二叉排序树
            System.out.println("中序遍历二叉排序树:");
            binarySortTree.infixOrder(); // 1, 3, 5, 7, 9, 10, 12
            // 删除节点测试
            binarySortTree.delNode(12);
            binarySortTree.delNode(5);
            binarySortTree.delNode(10);
            binarySortTree.delNode(2);
            binarySortTree.delNode(3);
            binarySortTree.delNode(9);
            binarySortTree.delNode(1);
            binarySortTree.delNode(7);
    
    
            System.out.println("root=" + binarySortTree.getRoot());
            System.out.println("删除结点后");
            binarySortTree.infixOrder();
        }
    }
    
    /**
    * @className: BinarySortTreeDemo
    * @description: 二叉排序树
    * @date: 2021/3/22
    * @author: cakin
    */
    class BinarySortTree {
        // 根节点
        private Node root;
    
    
        public Node getRoot() {
            return root;
        }
    
        /**
         * 功能描述:查找要删除的结点
         *
         * @param value 要删除节点的值
         * @return Node 要删除的节点
         * @author 贝医
         * @date 2021/3/25
         */
        public Node search(int value) {
            if (root == null) {
                return null;
            } else {
                return root.search(value);
            }
        }
    
        /**
         * 功能描述:要删除节点的父节点
         *
         * @param value 要删除节点的值
         * @return Node 要删除节点的父节点
         * @author 贝医
         * @date 2021/3/25
         * @description:
         */
        public Node searchParent(int value) {
            if (root == null) {
                return null;
            } else {
                return root.searchParent(value);
            }
        }
    
        /**
         * 功能描述:返回以 node 为根结点的二叉排序树的最小结点的值
         *
         * @param node 传入的结点(当做二叉排序树的根结点)
         * @return 返回的以 node 为根结点的二叉排序树的最小结点的值
         */
        public int delRightTreeMin(Node node) {
            Node target = node;
            // 循环的查找左子节点,就会找到最小值
            while (target.left != null) {
                target = target.left;
            }
            // target就指向了最小结点
            // 删除最小结点
            delNode(target.value);
            return target.value;
        }
    
        /**
         * 功能描述:删除结点
         *
         * @param value 待删除节点的值
         * @author 贝医
         * @date 2021/3/25
         */
        public void delNode(int value) {
            if (root == null) {
                return;
            } else {
                // 1 先去找到要删除的结点 targetNode
                Node targetNode = search(value);
                // 如果没有找到要删除的结点
                if (targetNode == null) {
                    return;
                }
                // 如果发现当前这颗二叉排序树只有一个结点
                if (root.left == null && root.right == null) {
                    root = null;
                    return;
                }
    
                // 去找到 targetNode 的父结点
                Node parent = searchParent(value);
                // 如果要删除的结点是叶子结点
                if (targetNode.left == null && targetNode.right == null) {
                    // 判断 targetNode 是父结点的左子结点,还是右子结点
                    if (parent.left != null && parent.left.value == value) { // 是左子结点
                        parent.left = null;
                    } else if (parent.right != null && parent.right.value == value) { // 是由子结点
                        parent.right = null;
                    }
                } else if (targetNode.left != null && targetNode.right != null) { // 删除有两颗子树的节点
                    int minVal = delRightTreeMin(targetNode.right);
                    targetNode.value = minVal;
                } else { // 删除只有一颗子树的结点
                    // 如果要删除的结点有左子结点
                    if (targetNode.left != null) {
                        if (parent != null) {
                            // 如果 targetNode 是 parent 的左子结点
                            if (parent.left.value == value) {
                                parent.left = targetNode.left;
                            } else { //  targetNode 是 parent 的右子结点
                                parent.right = targetNode.left;
                            }
                        } else {
                            root = targetNode.left;
                        }
                    } else { // 如果要删除的结点有右子结点
                        if (parent != null) {
                            // 如果 targetNode 是 parent 的左子结点
                            if (parent.left.value == value) {
                                parent.left = targetNode.right;
                            } else { // 如果 targetNode 是 parent 的右子结点
                                parent.right = targetNode.right;
                            }
                        } else {
                            root = targetNode.right;
                        }
                    }
                }
            }
        }
    
        /**
         * 功能描述:添加结点
         *
         * @param node 节点
         * @author cakin
         * @date 2021/3/22
         */
        public void add(Node node) {
            if (root == null) {
                root = node; // 如果root为空则直接让root指向node
            } else {
                root.add(node);
            }
        }
    
        /**
         * 功能描述:中序遍历
         *
         * @author cakin
         * @date 2021/3/22
         */
        public void infixOrder() {
            if (root != null) {
                root.infixOrder();
            } else {
                System.out.println("二叉排序树为空,不能遍历");
            }
        }
    }
    
    /**
    * @className: Node
    * @description: 节点
    * @date: 2021/3/22
    * @author: cakin
    */
    class Node {
        // 节点值
        int value;
        // 左子树根节点
        Node left;
        // 右子树根节点
        Node right;
    
        public Node(int value) {
            this.value = value;
        }
    
        /**
         * 功能描述:查找要删除的结点
         *
         * @param value 希望删除的结点的值
         * @return 如果找到返回该结点,否则返回null
         */
        public Node search(int value) {
            if (value == this.value) { // 找到该结点
                return this;
            } else if (value < this.value) {// 如果查找的值小于当前结点值,向左子树递归查找
                // 如果左子结点为空
                if (this.left == null) {
                    return null;
                }
                return this.left.search(value);
            } else { // 如果查找的值不小于当前结点,向右子树递归查找
                if (this.right == null) {
                    return null;
                }
                return this.right.search(value);
            }
        }
    
        /**
         * 功能描述:查找要删除结点的父结点
         *
         * @param value 要删除的结点的值
         * @return 返回的是要删除的结点的父结点,如果没有就返回null
         */
        public Node searchParent(int value) {
            // 如果当前结点就是要删除的结点的父结点
            if ((this.left != null && this.left.value == value) ||
                    (this.right != null && this.right.value == value)) {
                return this;
            } else {
                // 如果查找的值小于当前结点的值, 并且当前结点的左子结点不为空
                if (value < this.value && this.left != null) {
                    return this.left.searchParent(value); // 向左子树递归查找
                } else if (value >= this.value && this.right != null) {
                    return this.right.searchParent(value); // 向右子树递归查找
                } else {
                    return null; // 找到父结点
                }
            }
        }
    
        @Override
        public String toString() {
            return "Node [value=" + value + "]";
        }
    
        /**
         * 功能描述:添加节点到二叉排序树
         *
         * @param node 节点
         * @author cakin
         * @date 2021/3/22
         */
        public void add(Node node) {
            if (node == null) {
                return;
            }
    
            // 传入的结点的值小于当前子树的根结点的值
            if (node.value < this.value) {
                // 当前结点左子树根结点为null
                if (this.left == null) {
                    this.left = node;
                } else {
                    // 递归的向左子树添加
                    this.left.add(node);
                }
            } else { // 传入的结点的值大于当前子树的根结点的值
                if (this.right == null) {
                    this.right = node;
                } else {
                    // 递归的向右子树添加
                    this.right.add(node);
                }
            }
        }
    
        /**
         * 功能描述:中序遍历
         *
         * @author cakin
         * @date 2021/3/22
         */
        public void infixOrder() {
            if (this.left != null) {
                this.left.infixOrder();
            }
            System.out.println(this);
            if (this.right != null) {
                this.right.infixOrder();
            }
        }
    }

    四 测试

    中序遍历二叉排序树:
    Node [value=1]
    Node [value=2]
    Node [value=3]
    Node [value=5]
    Node [value=7]
    Node [value=9]
    Node [value=10]
    Node [value=12]
    root=null
    删除结点后
    二叉排序树为空,不能遍历

     

    展开全文
  • 一、二叉排序树 二叉排序树,又称二叉查找树(BST(Binary Sort/Search Tree) )或者是一棵空树,或者是具有下列特性的二叉树: (1)若左子树非空,则左子树上所有结点的值均小于根结点的值。 (2)若右子树非空,则...

    一、二叉排序树

    二叉排序树,又称二叉查找树(BST(Binary Sort/Search Tree) )或者是一棵空树,或者是具有下列特性的二叉树:
    (1)若左子树非空,则左子树上所有结点的值均小于根结点的值
    (2)若右子树非空,则右子树删所有结点的值均大于根结点的值
    (3)左右子树分别为一棵二叉排序树

    根据二叉排序树的定义,左子树结点值<根结点值<右子树结点值,则对二叉排序树进行中序遍历,可以得到一个递增的有序序列。如果有相同的值,可以将该节点放在左子节点或右子节点。
    E.g:下图所示的二叉排序树的中序遍历序列为1 2 3 4 5 6 8。
    在这里插入图片描述
    二、二叉排序树的基本操作

    1、添加子结点

    1.1、实现思路

    (1)若添加结点为空,则无法添加;
    (2)若添加结点的值小于当前结点的值,根据二叉排序树的定义,我们需要向当前结点的左子树添加结点。若当前结点的左子树为空,则直接添加成为当前结点的左子树;若当前结点的左子树不为空,则递归向当前结点的左子树遍历。
    (3)若添加结点的值大于等于当前结点的值,根据二叉排序树的定义,我们需要向当前结点的右子树添加结点。若当前结点的右子树为空,则直接添加成为当前结点的右子树;若当前结点的右子树不为空,则递归向当前结点的右子树遍历。

    1.2、实现代码

    public void add(Node node) {
    		if(node==null) {//添加结点为空
    			return;
    		}
    		if(node.value<this.value) {//添加结点值小于当前结点值,根据二叉排序树定义应向左边寻找
    			if(this.left==null) {//当前结点没有左孩子直接放在当前结点左边
    				this.left=node;
    			}else {
    				this.left.add(node);//否则递归向当前结点的左子树遍历
    			}
    		}else {//添加结点值大于等于当前结点值,根据二叉排序树定义应向右边寻找
    			if(this.right==null) {//当前结点没有右孩子直接放在当前结点右边
    				this.right=node;
    			}else {
    				this.right.add(node);//否则递归向当前结点的右子树遍历
    			}
    		}
    	}
    

    2、查找子结点

    2.1 实现思路

    (1)若查找值等于当前结点值则直接返回;
    (2)若查找值小于当前结点的值,根据二叉排序树的定义,我们需要向当前结点的左子树查找。若当前结点的左子树为空,则无法找到返回为空;若当前结点的左子树不为空,则递归向当前结点的左子树查找。
    (3)若查找值大于等于当前结点的值,根据二叉排序树的定义,我们需要向当前结点的右子树查找。若当前结点的右子树为空,则无法找到返回为空;若当前结点的右子树不为空,则递归向当前结点的右子树查找。

    2.2 实现代码

    public  Node search(int value) {
    		if(value==this.value) {//查找值等于当前结点值直接返回
    			return this;
    		}else if(value<this.value) {//查找值小于当前结点值,根据二叉排序树定义则向左子树查找
    			if(this.left==null) {//当前结点的左子树为空则找不到
    				return null;
    			}
    			return this.left.search(value);
    		}else {//查找值大于等于当前结点值,根据二叉排序树定义则向右子树查找
    			if(this.right==null) {//当前结点的右子树为空则找不到
    				return null;
    			}
    			return this.right.search(value);
    		}
    	}
    

    3、删除子结点

    3.1 实现思路
    3.1.1 删除叶子结点

    (1)是否为叶子结点的判断条件为:targetNode.left == null && targetNode.right==null,即左右结点均为空;
    (2)若targetNode为左子结点则将parent的左子结点置空即删除,即parent.left=null;若targetNode为右子结点则将parent的右子结点置空即删除,即parent.right=null。

    3.1.2 删除只有一棵子树的结点

    (1)是否为只有一棵子树的结点:targetNode.left ==null || targetNode.right ==null,即targetNode.left 和 targetNode.right 中有且仅有一个为 null;
    (2)若删除的结点有左子结点时,当targetNode是 parent 的左子结点,使parent.left=targetNode.left;当targetNode是 parent 的右子结点,使parent.right=targetNode.left;最后使root=targetNode.left。
    (3)若删除的结点有右子结点时,当targetNode是 parent 的左子结点,使parent.left=targetNode.right;当targetNode是 parent的右子结点,使parent.right=targetNode.right;最后使root=targetNode.right。

    若删除的结点有左子结点时,两种示意图:
    (1)当targetNode是 parent 的左子结点
    在这里插入图片描述
    (2)当targetNode是 parent的右子结点
    在这里插入图片描述

    若删除的结点有右子结点时,两种示意图:
    (1)当targetNode是 parent 的左子结点
    在这里插入图片描述
    (2)当targetNode是 parent的右子结点
    在这里插入图片描述

    3.1.3 删除有两棵子树的结点

    (1)先找到删除结点 targetNode,再找到其父结点parent;
    (2)利用递归在 targetNode的左子树中寻找值最小的结点,用临时变量temp保存;
    (3)删除该最小结点:delete(temp.value),再将 targetNode.value 设置为 temp即可。

    3.2 实现代码

    //结点类Node
    //查找删除结点的父结点
    	public Node searchParent(int value) {
    		if((this.left!=null&&this.left.value==value)||(this.right!=null&&this.right.value==value)) {
    			return  this;//若当前结点即为需要删除结点的父结点直接返回
    		}else {
    			if(value<this.value&&this.left!=null) {//删除结点值小于当前结点值且当前结点的左子树不为空,则向左子树递归查找删除
    				return this.left.searchParent(value);
    			}else if(value>=this.value&&this.right!=null) {//删除结点值大于等于当前结点值且当前结点的右子树不为空,则向右子树递归查找删除
    				return this.right.searchParent(value);
    			}else {//左右子树均未找到即返回空
    				return null;
    			}
    		}
    	}
    
    
    
    
    //二叉排序树定义类SortTree
    //删除子结点
    public void delete(int value) {
    		if(root==null) {//根结点为空无法操作直接返回
    			return;
    		}else {
    			Node targetNode=search(value);//找到要删除的结点targetNode
    			if(targetNode==null) {//若没有找到要删除的结点直接返回
    				return;
    			}
    			if(root.left==null&&root.right==null) {//若二叉排序树只有一个结点即根结点,将根结点置空即删除
    				root=null;
    				return;
    			}
    			
    			Node parent=searchParent(value);//寻找targetNode的父结点
    			
    			if(targetNode.left==null&&targetNode.right==null) {//删除结点为叶子结点
    				//判断targetNode是父结点的左子结点还是右子结点
    				if(parent.left!=null&&parent.left.value==value) {//targetNode为左子结点则将parent的左子结点置空即删除
    					parent.left=null;
    				}else if(parent.right!=null&&parent.right.value==value) {//targetNode为右子结点则将parent的右子结点置空即删除
    					parent.right=null;
    				}
    			}else if(targetNode.left!=null&&targetNode.right!=null){//删除有两颗子树的节点
    				int min=delRightMinTree(targetNode.right);
    				targetNode.value=min;
    			}else {//删除只有一颗子树的结点
    				if(targetNode.left!=null) {//若删除的结点有左子结点
    					if(parent!=null) {
    						if(parent.left.value==value) {//若targetNode是 parent 的左子结点
    							parent.left=targetNode.left;
    						}else { //若targetNode是 parent 的右子结点
    							parent.right=targetNode.left;
    						}
    					}else {
    						root=targetNode.left;
    					}
    				}else {//若删除的结点有右子结点
    					if(parent!=null) {
    						if(parent.left.value==value) {//若targetNode是 parent 的左子结点
    							parent.left=targetNode.right;
    						}else {//若targetNode是 parent的右子结点
    							parent.right=targetNode.right;
    						}
    					}else {
    						root=targetNode.right;
    					}
    				}
    			}
    		}
    	}
    	
    	/**
    	 * @param node   二叉排序树的根结点
    	 * @return       返回的 以node为根结点的二叉排序树的最小结点的值
    	 */
    	public int delRightMinTree(Node node) {
    		Node temp=node;
    		while(temp.left!=null) {//循环的查找左子节点,会找到最小值(因为左子树结点值<根结点值<右子树结点值)
    			temp=temp.left;
    		}
    		delete(temp.value);//退出循环时temp指向最小结点,则删除最小值结点,此时该结点必为左叶子结点
    		return temp.value;
    	}
    

    三、完整实现代码

    package Tree;
    
    public class BinarySortTree {
    	public static void main(String[] args) {
    		int[] arr= { 7, 3, 10, 12, 5, 1, 9};
    		 SortTree binarysorttree = new SortTree();
    		for(int i=0;i<arr.length;i++) {
    			binarysorttree.add(new Node(arr[i]));
    		}
    		
    		System.out.println("初始二叉排序树的中序遍历");
    		binarysorttree.inOrder();// 1,3, 5, 7, 9, 10, 12
    
    	    //测试删除叶子结点
    		binarysorttree.delete(1);
    		System.out.println("删除叶子结点后二叉排序树的中序遍历");
    	    binarysorttree.inOrder();//3, 5, 7, 9, 10, 12
    	    //测试删除只有一颗子树的结点
    	    binarysorttree.delete(3);
    	  	System.out.println("删除只有一颗子树的结点后二叉排序树的中序遍历");
    	  	binarysorttree.inOrder();//5, 7, 9, 10, 12
    	    //测试删除有两颗子树的节点
    	  	binarysorttree.delete(10);
    	  	System.out.println("删除有两颗子树的节点后二叉排序树的中序遍历");
    	  	binarysorttree.inOrder();//5, 7, 9, 12
    	}
    }
    
    class SortTree{
    	private Node root;//二叉排序树根结点
    	
    	public Node getRoot() {//获取二次排序树根结点
    		return root;
    	}
    	
    	public void add(Node node) {//添加子结点
    		if(root==null) {//若根结点为空直接让添加结点成为子结点
    			root=node;
    		}else {
    			root.add(node);
    		}
    	}
    	
    	public void inOrder() {//中序遍历
    		if(root!=null) {//若根结点不为空则调用结点的inOrder
    			root.inOrder();
    		}else {
    			System.out.println("二叉排序树为空,无法遍历!");
    		}
    	}
    	
    	public Node search(int value) {//查找子结点
    		if(root==null) {
    			return null;
    		}else{
    			return root.search(value);
    		}
    	}
    	
    	public Node searchParent(int value) {//查找父结点
    		if(root==null) {//根结点为空无法操作返回为空
    			return null;
    		}else {
    			return root.searchParent(value);
    		}
    	}
    	
    	//删除子结点
    	public void delete(int value) {
    		if(root==null) {//根结点为空无法操作直接返回
    			return;
    		}else {
    			Node targetNode=search(value);//找到要删除的结点targetNode
    			if(targetNode==null) {//若没有找到要删除的结点直接返回
    				return;
    			}
    			if(root.left==null&&root.right==null) {//若二叉排序树只有一个结点即根结点,将根结点置空即删除
    				root=null;
    				return;
    			}
    			
    			Node parent=searchParent(value);//寻找targetNode的父结点
    			
    			if(targetNode.left==null&&targetNode.right==null) {//删除结点为叶子结点
    				//判断targetNode是父结点的左子结点还是右子结点
    				if(parent.left!=null&&parent.left.value==value) {//targetNode为左子结点则将parent的左子结点置空即删除
    					parent.left=null;
    				}else if(parent.right!=null&&parent.right.value==value) {//targetNode为右子结点则将parent的右子结点置空即删除
    					parent.right=null;
    				}
    			}else if(targetNode.left!=null&&targetNode.right!=null){//删除有两颗子树的节点
    				int min=delRightMinTree(targetNode.right);
    				targetNode.value=min;
    			}else {//删除只有一颗子树的结点
    				if(targetNode.left!=null) {//若删除的结点有左子结点
    					if(parent!=null) {
    						if(parent.left.value==value) {//若targetNode是 parent 的左子结点
    							parent.left=targetNode.left;
    						}else { //若targetNode是 parent 的右子结点
    							parent.right=targetNode.left;
    						}
    					}else {
    						root=targetNode.left;
    					}
    				}else {//若删除的结点有右子结点
    					if(parent!=null) {
    						if(parent.left.value==value) {//若targetNode是 parent 的左子结点
    							parent.left=targetNode.right;
    						}else {//若targetNode是 parent的右子结点
    							parent.right=targetNode.right;
    						}
    					}else {
    						root=targetNode.right;
    					}
    				}
    			}
    		}
    	}
    	
    	/**
    	 * @param node   二叉排序树的根结点
    	 * @return       返回的 以node为根结点的二叉排序树的最小结点的值
    	 */
    	public int delRightMinTree(Node node) {
    		Node temp=node;
    		while(temp.left!=null) {//循环的查找左子节点,会找到最小值(因为左子树结点值<根结点值<右子树结点值)
    			temp=temp.left;
    		}
    		delete(temp.value);//退出循环时temp指向最小结点,则删除最小值结点,此时该结点必为左叶子结点
    		return temp.value;
    	}
    }
    
    
    class Node{
    	int value;
    	Node left;
    	Node right;
    	 
    	public Node(int value) {//Node的构造函数(无返回值)
    		this.value=value;
    	}
    
    	@Override
    	public String toString() {//重写toString方法
    		return "Node [value=" + value + "]";
    	}
    	
    	public void inOrder() {//中序遍历二叉排序树得到有序序列
    		if(this.left!=null) {
    			this.left.inOrder();
    		}
    		System.out.println(this);
    		if(this.right!=null) {
    			this.right.inOrder();
    		}
    	}
    	
    	//添加子结点
    	public void add(Node node) {
    		if(node==null) {//添加结点为空
    			return;
    		}
    		if(node.value<this.value) {//添加结点值小于当前结点值,根据二叉排序树定义应向左边寻找
    			if(this.left==null) {//当前结点没有左孩子直接放在当前结点左边
    				this.left=node;
    			}else {
    				this.left.add(node);//否则递归向当前结点的左子树遍历
    			}
    		}else {//添加结点值大于等于当前结点值,根据二叉排序树定义应向右边寻找
    			if(this.right==null) {//当前结点没有右孩子直接放在当前结点右边
    				this.right=node;
    			}else {
    				this.right.add(node);//否则递归向当前结点的右子树遍历
    			}
    		}
    	}
    	
    	//查找子结点
    	public  Node search(int value) {
    		if(value==this.value) {//查找值等于当前结点值直接返回
    			return this;
    		}else if(value<this.value) {//查找值小于当前结点值,根据二叉排序树定义则向左子树查找
    			if(this.left==null) {//当前结点的左子树为空则找不到
    				return null;
    			}
    			return this.left.search(value);
    		}else {//查找值大于等于当前结点值,根据二叉排序树定义则向右子树查找
    			if(this.right==null) {//当前结点的右子树为空则找不到
    				return null;
    			}
    			return this.right.search(value);
    		}
    	}
    	
    	//查找删除结点的父结点
    	public Node searchParent(int value) {
    		if((this.left!=null&&this.left.value==value)||(this.right!=null&&this.right.value==value)) {
    			return  this;//若当前结点即为需要删除结点的父结点直接返回
    		}else {
    			if(value<this.value&&this.left!=null) {//删除结点值小于当前结点值且当前结点的左子树不为空,则向左子树递归查找删除
    				return this.left.searchParent(value);
    			}else if(value>=this.value&&this.right!=null) {//删除结点值大于等于当前结点值且当前结点的右子树不为空,则向右子树递归查找删除
    				return this.right.searchParent(value);
    			}else {//左右子树均未找到即返回空
    				return null;
    			}
    		}
    	}
    }
    

    运行结果:

    初始二叉排序树的中序遍历
    Node [value=1]
    Node [value=3]
    Node [value=5]
    Node [value=7]
    Node [value=9]
    Node [value=10]
    Node [value=12]
    删除叶子结点后二叉排序树的中序遍历
    Node [value=3]
    Node [value=5]
    Node [value=7]
    Node [value=9]
    Node [value=10]
    Node [value=12]
    删除只有一颗子树的结点后二叉排序树的中序遍历
    Node [value=5]
    Node [value=7]
    Node [value=9]
    Node [value=10]
    Node [value=12]
    删除有两颗子树的节点后二叉排序树的中序遍历
    Node [value=5]
    Node [value=7]
    Node [value=9]
    Node [value=12]
    

    该初始二叉排序树如下图所示:
    在这里插入图片描述

    展开全文
  • 步骤:首先,我们先从根节点开始查找到要删除的这个节点,然后删除该节点,然后再妥善安置该该节点的子树或子节点。 要删除的节点分为三种情况:1,当要删除的节点的是叶子结点的时候;2,当要删除的节点只有一个子...
  • 一、二叉排序树概述 二叉排序树(Binary Sort Tree),又称二叉查找树(Binary Search Tree),亦称二叉搜索树。对于二叉排序树的任何一个非叶子节点,要求左子节点的值比当前节点的值小,右子节点的值比当前节点的...
  • 在分析treemap时,分析到了红黑树,而红黑树是由二叉排序树变体产生的,因此学习二叉排序树是常用树的基础;本篇文章主要分析二叉排序树的构建 ,及原理解析,遍历方式。
  • 二叉查找 二叉树包含许多特殊的形式,每一种形式都有自己的作用,但是其最主要的应用还在于进行查找操作和维持相对顺序这两个方面。 二叉查找的定义(Binary Search Tree): 该是一颗二叉树。 如果左子树...
  • 一、二叉排序树(二叉查找树)的概念 (1)若左子树非空,则左子树上所有结点的值均小于根节点的值 (2)若右子树非空,则右子树上所有结点的值均大于根节点的值 (3)左右子树分别也是一棵二叉排序树 tip:可以...
  • 二叉排序树的插入和删除(C语言)

    万次阅读 2021-04-21 20:30:38
    } void DelBST(BinTreeNode *T,int key)//在二叉排序树删除结点 {//因为一个结点一旦有左子树,就要有区分左右大小的任务,所以以有无左子树来分类讨论 BinTreeNode *p,*f,*s,*q; p=T; f=NULL; while(p)//查找为...
  • // 二叉搜索,以特定的规则来进行构建// 1,所有节点中,该节点的左子树中的节点的键值 =< 该节点,右子中节点的键值 >= 该节点.// 2,当进行一次中序遍历,则会得到升序排列#include #include struct Node{int ...
  • 二叉排序树的构造、查找、删除
  • 二叉排序树

    2021-08-22 22:25:22
    文章目录 二叉排序树 二叉排序树插入 查询 查找分析 插入 建立 二叉排序树删除    二叉排序树   二叉排序树: 或者是一棵空树;或者是具有下列性质的二叉树:(1)若它的左子树不空,则左子树上所有结点的值均小于...
  • 文章目录二叉排序树二叉排序树-定义二叉排序树-查找二叉排序树-插入二叉排序树-建立二叉排序树-遍历二叉排序树-删除二叉排序树-性能分析 二叉排序树-定义 ​ 空树或者是具有如下特性的二叉树被称为二叉
  • 详解Java二叉排序树

    2021-02-25 19:27:57
    一、二叉排序树定义1.二叉排序树的定义二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree)。其定义为:二叉排序树或者是空树,或者是满足如下性质的二叉树:①若它的左子树非空,则左子树上所有...
  • 文章目录二叉排序树的定义二叉排序树的查找二叉排序树的插入二叉排序树的构造二叉排序树删除 二叉排序树的定义 二叉排序树(Binary Sort Tree, BST),也称二叉查找树。 二叉排序树或者是一棵空树,或者是一棵...
  • 用二叉树的所学知识建立二叉排序树,对已建立的排序二叉树进行遍历(中序),插入,查找,删除 二、算法的基本思想 二叉排序树插入结点的算法: 1若建立的二叉排序树中已有与欲插入的数相同的结点则无须插入;2以...
  • 删除二叉排序树中的一个节点 假设被删结点是p,其双亲是f,设p是f的左孩子,三种情况 若结点p是叶子结点,则只需修改其双亲结点f的指针即可。 若结点*p只有左子树PL或者只有右子树PR,则只要使PL或PR 成为其双亲...
  • 对于一个二叉排序树,要删除其某个结点,重点要找到两个关键结点(自身与父结点),代码实现如下: #include<iostream> #include<string> using namespace std; class Node{ public: int value; ...
  • 二叉排序树删除一个结点时,需保证删除后的二叉树仍然是二叉排序树。为讨论方便,假定被删除结点为p,其双亲结点为f。删除的过程可按下述的两种情况分别处理。 在这里我们用红色三角形表示我们要删除的结点,...
  • 二叉排序树 对于二叉排序树的任何一个非叶子节点,要求左子节点的值比当前节点的值小,右子节点的值比当前节点的值大。 特点:中序遍历正好是数列的升序排列。 实现思路与注意 1:创建每一个Node节点对应的对象,...
  • 非递归实现三、二叉排序树的插入四、二叉排序树删除 参考博文:《二叉排序树的查找、插入、删除》 一、定义 二叉排序树(BST)(二叉查找树)或者是一棵空树,或者是具有下列特性的二叉树: 1)若左子树非空,则左子树...
  • 二叉排序树(Binary Sort Tree),又称二叉查找树(Binary Search Tree),亦称二叉搜索树。是数据结构中的一类。在一般情况下,查询效率比链表结构要高。 二叉排序树的定义 一棵空树,或者是具有下列性质的...
  • 二叉排序树(BST)

    2021-06-18 17:00:35
    二叉排序树(也称二叉查找树)。 性质:左子树结点值 < 根结点值 < 右子树结点值 所以对二叉排序树进行中序遍历,可以得到一个递增的xu'l
  • 二叉排序树 二叉排序树(Binary sort tree,BST),又称为二叉查找树,或者是一棵空树;或者是具有下列性质的二叉树: (1)若它的左子树不为空,则左子树上所有节点的值均小于它的根节点的值; (2)若它的右子树...
  • 功能要求: ...(8)从二叉排序树删除一条学生记录; (9)从二叉排序树中查询一条学生记录; (10)以广义表的形式输出二叉排序树 //定义学生记录类型 Struct student { Char num[6]; //学号 Int grade; .
  • 它或则是一颗空树,或者是带有以下性质的二叉树:构造二叉排序树的目的,并不是为了顺序,而是为了提升查找和插入删除关键字的速度。以下程序在DEV C++中安装运行通过。#include#include/*二叉树的二叉链表结点结构...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 44,758
精华内容 17,903
关键字:

二叉排序树的删除