[数据结构与算法]二叉排序树的增加、删除、查找的实现&前中后序遍历的栈和递归实现

代码实现

import java.util.ArrayList;
import java.util.List;

public class MyBSTree <T extends Comparable<T>>{
    //定义二叉搜索树的根节点
    private Node root;
    private int size;

    //对二叉搜索树的添加方法：在二叉搜索树种添加一个结点/值
    public boolean add(T value){
        //这里不允许往二叉树中存储null值 无法比较大小
        if (value == null) throw new IllegalArgumentException("parame is null");

        //这里判断添加的时候树是否为空
        if (isEmpty()){
            //如果原树为空，新元素作为根节点
            root = new Node(value);
            size++;
            return true;
        }
        //原树不空 找一个存储位置，按照大小向左右方向上查找比较
        Node mid = root;//当前遍历节点
        Node midF = null;//保存遍历节点的父节点
        int com = 0;

        while (mid != null){
            com = value.compareTo(mid.value);
            midF = mid;
            if (com > 0){
                //说明value比mid大 应该添加到mid的右边
                mid = mid.right;
            }else if (com < 0){
                mid = mid.left;
            }else{
                //如果两值相等的话说明要添加的这个元素已经在树上了 以下讨论几个方法
                // 拉链法
                // 计数法
                // 修正的BSTree
                return false;
            }
        }
        //midF就是要添加位置的父节点
        if (com > 0){
            //最后一次比较，value大
            midF.right = new Node(value);
        }else{
            //最后一次比较，value小
            midF.left = new Node(value);
        }
        size++;
        return true;
    }

    /**
     * 对二叉搜索树的删除方法：在二叉搜索树种删除一个结点/值
     * @return
     */
    public boolean remove(T value){
        //不允许在二叉树中出现null值 无法删除
        if (value == null) throw new IllegalArgumentException("parame is null");

        //二叉搜索树不能是空树
        if (isEmpty()) throw new RuntimeException("tree is empty");
        //查找要删除节点
        Node mid = root;//遍历节点（用于查找要删除的结点）
        Node midF = null;//遍历结点的父节点

        while (mid != null){
            int com = value.compareTo(mid.value);
            if (com == 0){
                //mid就是要删除的元素
                break;//如果找到了就直接跳出循环
            }else if (com > 0){
                //value 比较大, 如果这个value存在在二叉搜索树, 应该在此时mid的right方向
                midF = mid;//记录父结点位置
                mid = mid.right;// 子结点右转
            }else {
                // value 比较小, 如果这个value存在在二叉搜索树, 应该在此时mid的left方向
                midF = mid;// 记录父结点位置
                mid = mid.left;// 子结点左转
            }
        }
        // 上述循环有两个跳出条件
        // mid == null  --> 没有找到, 这个树上没有存储这个元素
        // 否则就是找到了

        if (mid == null)return false;

        // mid就是找到的要删除结点位置
        // midF 就是找到的要删除结点的父位置

        // 先处理删除双分支情况 --> 替换
        if (mid.left != null && mid.right != null){
            // mid 的left 和right 都是不是 null
            // mid 是一个双分支结点: 先替换再删除
            // 替换: (左子树最大值, 右子树最小值) 右子树的最小值
            Node min = mid.right;
            Node minF = mid;
            while (min.left != null){
                // mid 的left 还有结点, min不是最小, 接着向left移动找最小
                minF = min;
                min = min.left;
            }
            // min就是mid 的right子树最小值
            // minF 就是最小值的父结点
            //替换值
            mid.value = min.value;
            // 把要删除结点的引用, 指向这个已经完成替换的结点
            mid = min;
            midF = minF;
        }
        // 再处理删除叶子或者单分支(双份支替换之后的叶子和单分支)

        // 拿到要删除结点的孩子
        // (如果是个单分支,拿到那个不为null的孩子)
        // (如果本来就是叶子, 拿到null)
        Node ch = mid.left != null ? mid.left:mid.right;
        //TODO:特殊情况: 如果这个树的根节点是个单分支, 而且要删除的结点也是这个根节点
        if (midF == null){
            root = ch;
            size--;
            return true;
        }
        if (midF.left == mid){
            // 删除的是midF 的left
            midF.left = ch;
        }else {
            // 删除的是midF 的right
            midF.right = ch;
        }

        size--;
        return true;
    }

    /**
     * 对二叉搜索树的查找方法：在二叉搜索树中查找某个值是否存在
     * @return
     */
    public boolean contains(T value){
        //不允许输入null
        if(value == null) throw  new IllegalArgumentException("parame is null");
        //判断二叉搜索树是否为空 若为空肯定没有这个元素
        if (isEmpty()) return  false;

        //若二叉搜索树不空
        Node mid = root;//定义一个遍历结点, 遍历
        while (mid != null){
            int com = value.compareTo(mid.value);

            if (com == 0){
                // mid就是要查找的值
                return true;
            }else if (com > 0){
                // value更大, 如果value在树中存在, 那么在mid的right
                mid = mid.right;
            }else {
                // value更小, 如果value在树中存在, 那么在mid的left
                mid = mid.left;
            }
        }
        //没找到, mid == null
        return false;
    }

    public boolean isEmpty(){return size == 0;}
    public int size(){return size;}

    // --------------------------------------------------
    // --------------------------------------------------
    // --------------------------------------------------
    // --------------------------------------------------
    // --------------------------------------------------
    // --------------------------------------------------
    // --------------------------------------------------

    // 前序: 栈, 递归
    //用栈实现前序遍历
    public List<T> preOrder(){
        MyArrayStack<Node> stack = new MyArrayStack<>();
        ArrayList<T> list = new ArrayList<>();
        if (root == null)return list;
        //把根节点放入栈中
        stack.push(root);
        while (!stack.isEmpty()){
            Node mid = stack.pop();
            list.add(mid.value);
            if (mid.right != null)
                stack.push(mid.right);
            if (mid.left != null)
                stack.push(mid.left);
        }
        return list;
    }
    //使用递归实现前序遍历
    public void preOrder2(Node root, ArrayList<T> list){
        //递归出口
    if (root == null)return;
        //遍历根
        list.add(root.value);
        //遍历左子树
        preOrder2(root.left,list);
        //遍历右子树
        preOrder2(root.right,list);
    }


    // 中序: 栈, 递归
    // 用栈实现中序遍历
    public List<T> inOrder(){
        MyArrayStack<Node> stack = new MyArrayStack<>();
        ArrayList<T> list = new ArrayList<>();

        //定义一个标记结点
        Node mid = root;
        // 循环: 栈不为空 或者 标记结点不是null
        while (!stack.isEmpty() || mid != null){
            // 小循环: mid left序列统统入栈
            while (mid!=null){
                stack.push(mid);
                mid = mid.left;
            }
            // 出栈遍历
            Node pop = stack.pop();
            list.add(pop.value);

            // 标记结点指向出栈结点的right
            mid = pop.right;
        }
        return list;
    }
    public List<T> inOrder2(){
        ArrayList<T> list = new ArrayList<>();
        inOrder2(root , list);
        return list;
    }
    // 递归核心思想:  大问题转化成小问题
    // 不要上来就想出口是什么, 也不要一开始就想怎么触发这个递归
    // 问题的共性 --- 最重要,
    // 比如这个中序遍历, 如果给我一个结点,  遍历左子树, 遍历根 遍历右子树

    // 递归实现中序遍历
    private void inOrder2(Node root,ArrayList<T> list){
        //出口
        if (root == null)return;
        // 遍历左子树
        inOrder2(root.left,list);
        // 遍历根
        list.add(root.value);
        // 遍历右子树
        inOrder2(root.right,list);
    }

    //后序：用栈，递归实现
    // 用栈实现后序遍历
    public List<T> posrOrder(){
        MyArrayStack<Node> stack = new MyArrayStack<>();
        ArrayList<T> list = new ArrayList<>();

        //根节点入栈
        stack.push(root);
        //循环 栈不为空
        while (!stack.isEmpty()){
            Node pop = stack.pop();//出栈元素
            list.add(0, pop.value);//逆序遍历——头插法

            if (pop.left != null)stack.push(pop.left);
            if (pop.right != null) stack.push(pop.right);
        }
        return list;
    }

    //使用递归逆序
    public List<T> posrOrder2(){
        ArrayList<T> list = new ArrayList<>();
        posrOrder2(root,list);
        return list;
    }

    private void posrOrder2(Node root, ArrayList<T> list) {
        //出口
        if (root == null)return;

        //遍历左子树
        posrOrder2(root.left,list);
        // 遍历右子树
        posrOrder2(root.right,list);
        // 遍历根
        list.add(root.value);
    }

    //层级遍历 使用队列
    public List<T> leOrder(){
        MyArrayQueue<Node> queue = new MyArrayQueue<>();
        ArrayList<T> list = new ArrayList<>();
        // 根节点入队列
        queue.offer(root);

        //循环 队列不空
        while (!queue.isEmpty()){
            //出队列一个元素遍历
            Node poll = queue.poll();
            list.add(poll.value);

            // 出队列结点的左右子结点入队列
            if (poll.left != null)queue.offer(poll.left);
            if (poll.right != null)queue.offer(poll.right);
        }
        return list;
    }

    // 建树操作: 后序+中序
    public void buildTreeByPostAndInOrder(List<T> postOrder, List<T> inOrder){
        // 递归方法
        root = buildTreeByPostAndInOrder2(postOrder, inOrder);
        size = inOrder.size();
    }


    //后序: [-2, -1, 0, 1, 6, 7, 5, 13, 11, 20, 15, 10]
    //中序: [-2, -1, 0, 1, 5, 6, 7, 10, 11, 13, 15, 20]
    private Node buildTreeByPostAndInOrder2(List<T> postOrder, List<T> inOrder) {
        // 出口
        if (postOrder.size() == 0)return null;
        if (postOrder.size() == 1){
            return new Node(postOrder.get(0));
        }


        // 获得根节点的值, 后序的最后一个元素
        T rootValue = postOrder.get(postOrder.size() - 1);

        // 创建根节点
        Node node = new Node(rootValue);

        // 获取根节点在中序中的位置
        int index = inOrder.indexOf(rootValue);

        //后序: [-2, -1, 0, 1, 6, 7, 5, 13, 11, 20, 15, 10]  左 右  根
        //中序: [-2, -1, 0, 1, 5, 6, 7, 10, 11, 13, 15, 20]  左 根 右
        //                            index

        // 左子树left:
        //      中序: inOrder ->  0 - index-1
        //      后序: postOrder-> 0 - index-1

        // 右子树right:
        //      中序: inOrder ->  index+1 - size-1
        //      后序: postOrder-> index - size-2

        List<T> leftInOder  = inOrder.subList(0, index);
        List<T> leftPostOder  = postOrder.subList(0, index);

        List<T> rightInOder  = inOrder.subList(index+1, inOrder.size());
        List<T> rightPostOder  = postOrder.subList(index, inOrder.size() - 1);

        // 递归去构建node 的left子树和right子树
        node.left = buildTreeByPostAndInOrder2(leftPostOder, leftInOder);
        node.right = buildTreeByPostAndInOrder2(rightPostOder, rightInOder);


        return node;
    }


    // 建树操作: 前序+中序
    // 建树操作: 前序+中序
    public void buildTreeByPreAndInOrder(List<T> preOrder, List<T> inOrder){
        // 递归方法
        root = buildTreeByPreAndInOrder2(preOrder, inOrder);
        size = inOrder.size();
    }


    private Node buildTreeByPreAndInOrder2(List<T> preOrder, List<T> inOrder) {
        // 出口
        if (preOrder.size() == 0)return null;
        if (preOrder.size() == 1){
            return new Node(preOrder.get(0));
        }


        // 获得根节点的值, 后序的最后一个元素
        T rootValue = preOrder.get(preOrder.size() - 1);

        // 创建根节点
        Node node = new Node(rootValue);

        // 获取根节点在中序中的位置
        int index = inOrder.indexOf(rootValue);

        List<T> leftInOder  = inOrder.subList(0, index);
        List<T> leftpreOder  = preOrder.subList(0, index);

        List<T> rightInOder  = inOrder.subList(index+1, inOrder.size());
        List<T> rightpreOder  = preOrder.subList(index, inOrder.size() - 1);

        // 递归去构建node 的left子树和right子树
        node.left = buildTreeByPreAndInOrder2(leftpreOder, leftInOder);
        node.right = buildTreeByPreAndInOrder2(rightpreOder, rightInOder);

        return node;
    }




    //-----------------------------------------------
    class Node{
        T value;
        Node left;
        Node right;
        public Node(T value){this.value = value;}

    }
}