数据结构和算法学习笔记六_树结构的实际应用(2)

package com.lxf.binarysorttree;

public class BinaryTreeDemo {
    public static void main(String[] args) {
        int[] arr={7,3,10,12,5,1,9};
        BinarySortTree binarySortTree = new BinarySortTree();
        //循环的添加结点到二叉排序树
        for (int i : arr) {
            binarySortTree.add(new Node(i));
        }
        //中序遍历:1 3 5 7 9 10 12(预期)
        binarySortTree.midOrder();
    }
}

class BinarySortTree{
    private  Node root;

    /**
     * 添加结点的方法
     * @param node
     */
    public void add(Node node){
        if (root == null) {
            root=node;//如果root为空，直接让root指向node
        }else{
            root.add(node);
        }
    }

    /**
     * 中序遍历
     */
    public void midOrder(){
        if(root!=null){
            root.midOrder();
        }else{
            System.out.println("根节点为空，无法遍历!");
        }
    }
}

/**
 * 创建node结点
 */
class Node{
    int value;
    Node left;
    Node right;

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


    /**
     * 添加结点的方法
     * 递归的形式添加结点，注意需要满足二叉排序树的基本要求
     * @param node
     */
    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);
            }

        }
    }

    /**
     * 中序遍历
     */
    public void midOrder(){
        if(this.left!=null){
            this.left.midOrder();
        }
        System.out.print(this+" ");
        if(this.right!=null){
            this.right.midOrder();
        }
    }


    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }
}

1.3、二叉排序树的删除

1.3.1、问题分析：

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

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

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

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

1.3.2、问题分析操作的思路分析:

第一种情况：删除叶子结点(比如：2，5，9，12)

思路：

1. 先去找到要删除的结点,targetNode

2. 找到targetNode的父节点的parent

3. 确定targetNode是parent的左子结点，还是右子结点

4. 根据前面的情况来对应删除

左子结点：parent.left=null

右子结点：parent.right=null

第二种情况：删除只有一颗子树的节点，比如值为1的结点

思路：

1. 先去找到要删除的结点 targeNode

2. 找到targeNode的父结点parent

3. 确定targeNode的子节点是左子结点还是右子结点

4. 判断targetNode是parent的左子结点还是左子结点

   • targetNode是parent的左子结点
     • targeNode的子节点也是左子结点，则parent.left=targetNode.left;
     • targetNode的子节点是右子结点，则parent.left=targeNode.right;
   • targetNode是parent的右子结点
     • targeNode的子节点是左子结点，则parent.right=targetNode.left;
     • targeNode的子节点也是右子结点，则parent.right=targetNode.right;

第三种情况：有两颗子树的节点，比如值为10的结点

思路：

1. 先去找到要删除的结点targerNode
2. 找到targetNode的父节点parent
3. 从targeNode的右子树找到最小的结点
4. 用一个临时变量，将最小结点的值保存temp=12
5. 删除该最小结点
6. targetNode.value=temp

代码实现：

package com.lxf.binarysorttree;

public class BinaryTreeDemo {
    public static void main(String[] args) {
        int[] arr={7,3,10,12,5,1,9,2};
        BinarySortTree binarySortTree = new BinarySortTree();
        //循环的添加结点到二叉排序树
        for (int i : arr) {
            binarySortTree.add(new Node(i));
        }
        //中序遍历:1 3 5 7 9 10 12(预期)
        System.out.println("中序遍历二叉排序树:");
        binarySortTree.midOrder();

        //测试删除叶子结点
        binarySortTree.delNode(7);
        System.out.println("删除结点后：");
        binarySortTree.midOrder();
    }
}

class BinarySortTree{
    private  Node root;


    /**
     * 查找要删除的结点
     * @param value  查找的值
     * @return 返回要删除的结点
     */
    public Node search(int value){
        if (root == null) {
            return null;
        }else{
            return root.search(value);
        }
    }
    /**
     * 查找要删除的结点的父节点
     * @param value  查找的值
     * @return 返回要删除的结点的父节点
     */
    public Node searchParent(int value){
        if (root == null) {
            return null;
        }else{
            return root.searchParent(value);
        }
    }

    /**
     * 方法：
     * 1.返回以node.right为根节点的二叉排序树的最小结点值
     * 2.删除node.为结点的二叉排序树的最小的结点
     *
     * @param node 传入的结点(当做排序二叉排序树的根结点)
     * @return 返回的以node为根结点的二叉排序树的最小结点的值
     */
    public int delRightTreeMin(Node node){
            Node target=node.right;
            //循环的查找左节点
            while(target.left!=null){
                target=target.left;
            }
            //这时target就指向了最小结点

            //删除最小结点
            delNode(target.value);

            return target.value;
    }
    /**
     * 删除结点
     * @param value
     */
    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 minValue=delRightTreeMin(