0090 二叉排序树

 

 

 

 

 

 

 

 

/*
 * 二叉排序树（BST）
 * 对于二叉排序树的任何一个非叶子节点，要求左子节点值比当前节点值小，右子节点值比当前节点值大
 * 如果有相同的值，可以将该结点放在左子节点或右子节点
 * 
 * 用一个数组创建成对应的二叉排序树，并使用中序遍历二叉排序树
 * int[] arr = {7,3,10,12,5,1,9,2};
 * 
 * 二叉排序树的删除
 * 1.删除叶子节点（如5，9，12）
 *         1.找到要删除的目标结点 targetNode
 *         2.找到目标结点的父节点 parent
 *         3.确定目标节点是父节点的左子节点还是右子节点
 *         4.左子节点：parent.left = null;
 *        右子节点：parent.right = null;
 *  
 * 2.删除只有一颗子树的节点（如1）
 *         1.找到要删除的目标结点 targetNode
 *         2.找到目标结点的父节点 parent
 *         3.确定目标结点的子节点是左子节点还是右子节点
 *         4.确定目标节点是父节点的左子节点还是右子节点
 *         5.目标结点的子节点是左子节点：
 *             1.目标结点是父节点的左子节点：parent.left = targetNode.left
 *             2.目标结点是父节点的右子节点：parent.right = targetNode.left
 *         6.目标结点的子节点是右子节点
 *             1.目标结点是父节点的左子节点：parent.left = targetNode.right
 *             2.目标结点是父节点的右子节点：parent.right = targetNode.right
 * 
 * 3.删除有两颗子树的节点（如7，3，10）
 *         1.找到要删除的目标结点 targetNode
 *         2.找到目标结点的父节点 parent
 *         3.从目标节点的右子树找到最小结点
 *         4.用一个临时变量，将最小结点保存 temp
 *         5.删除最小结点
 *         6.targetNode.value = temp
 */
public class BinarySortTree_ {
    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]));
        }
        
        //中序遍历二叉排序树
        binarySortTree.infixOrder();//1,2,3,5,7,9,10,12
        
        binarySortTree.delNode(5);
        binarySortTree.delNode(1);        
        binarySortTree.delNode(7);
        System.out.println("删除结点后========================");
        binarySortTree.infixOrder();
    }
}

//创建二叉排序树
class BinarySortTree{
    private Node root;
    
    //查找要删除的结点
    public Node serch(int value) {
        if (root == null) {
            return null;
        }else {
            return root.serch(value);
        }
    }
    
    //查找要删除结点的父节点
    public Node serchParent(int value) {
        if (root == null) {
            return null;
        }else {
            return root.serchParent(value);
        }
    }
    
    //编写方法，传入node结点，返回以node为根节点的最小结点的值,并删除
    public int delRightTreeMin(Node node) {
        Node tempNode = node;
        //循环查找左子节点，找到最小值
        while(tempNode.left != null) {
            tempNode = tempNode.left;
        }//这时tempNode指向了最小结点
        
        //删除最小结点
        delNode(tempNode.value);
        return tempNode.value;
    }
    
    //删除结点
    public void delNode(int value) {
        if (root == null) {
            return;
        }else {
            //1.找到要删除的目标结点 targetNode
            Node targetNode = serch(value);
            //没有找到
            if (targetNode == null) {
                return;
            }
            //如果只有一个结点
            if (root.left == null && root.right == null) {
                root = null;
                return;
            }
            
            //2.找到目标结点的父节点 parent
            Node parent = serchParent(value);
            
            //删除叶子节点
             if (targetNode.left == null && targetNode.right == null) {
                 //确定目标节点是父节点的左子节点还是右子节点
                 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) {
                //从目标节点的右子树找到最小结点,用一个临时变量，将最小结点保存 temp
                int temp = delRightTreeMin(targetNode.right);
                
                targetNode.value = temp;
                
            //删除只有一颗子树的节点
            } else {
                //目标结点的子节点是左子节点
                if (targetNode.left != null) {
                    if (parent != null) {//判断父节点是否为空，可能为根节点
                        //目标结点是父节点的左子节点
                        if (parent.left.value == value) {
                            parent.left = targetNode.left;
                        //目标结点是父节点的右子节点
                        }else {
                            parent.right = targetNode.left;
                        }
                    }else {//父节点为空，让根节点指向目标节点的左子节点
                        root  = targetNode.left;
                    }
                    
                //目标结点的子节点是右子节点
                }else {
                    if (parent != null) {
                        //目标结点是父节点的左子节点
                        if (parent.left.value == value) {
                            parent.left = targetNode.right;
                        //目标结点是父节点的右子节点
                        }else {
                            parent.right = targetNode.right;
                        }
                    }else {
                        root = targetNode.right;
                    }
                }
            }
        }
    }
    
    //添加节点的方法
    public void add(Node node) {
        if (root == null) {
            root = node;
        }else {
            root.add(node);
        }
    }
    
    //中序遍历
    public void infixOrder() {
        if (root == null) {
            System.out.println("树空，无法遍历");
        }else {
            root.infixOrder();
        }
    }
}

//创建Node
class Node{
    int value;
    Node left;
    Node right;
    public Node(int value) {
        this.value = value;
    }
    
    //查找要删除的结点
    public Node serch(int value) {
        if (value == this.value) {
            return this;
        }else if (value < this.value) {//查找值小于当前节点，向左递归
            if (this.left == null) {
                return null;
            }else {
                return this.left.serch(value);
            }
        }else {//查找值不小于当前节点，向右递归
            if (this.right == null) {
                return null;
            }else {
                return this.right.serch(value);
            }
        }
    }
    
    //查找要删除结点的父节点
    public Node serchParent(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.serchParent(value);//向左递归
            //如果查找值大于当前节点值，且当前节点的右子节点不为空
            }else if (value >= this.value && this.right != null) {
                return this.right.serchParent(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) {
            //如果当前左子节点为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 infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }
}