数据结构（六）二分搜索树(Binary Search Tree)

数据结构（一）数组实现一个简单的ArrayList
数据结构（二）链表实现LinkedList
数据结构（三）用两种方式简单实现栈
数据结构（四）栈和队列的简单应用
数据结构（五）用两种方式简单实现队列
数据结构（六）二分搜索树(Binary Search Tree)（上）
数据结构（六）二分搜索树(Binary Search Tree)（下）
数据结构（七）两种方式实现set

今天这篇文章是接上次的文章，二分搜索树还有几个方法没有分析完。简单回顾一下，昨天我们分析了添加操作，是否包含操作，最小值，最大值，以及删除最大值最小值操作。今天我们分析一下删除操作，以及他的几个遍历方法：前序遍历，中序遍历以及后续遍历。

• preOrder

// 二分搜索树的前序遍历
    public void preOrder(){
        preOrder(root);
    }

    // 前序遍历以node为根的二分搜索树, 递归算法
    private void preOrder(Node node){
        if(node == null)
            return;
        System.out.println(node.e);
        preOrder(node.left);
        preOrder(node.right);
    }

这里我们同样用递归实现前序遍历。先找到结束的条件就是当前节点为空就结束了。前序遍历就是先打印当前节点，然后再打印左子树然后是右子树。这样前序遍历就完成。

前序遍历顺序

大家可以看一下上边这个图。这里就是前序遍历的顺序图。下边这个图是她的打印结果。

preoderPrint

• inOrder 好了看完了前序遍历我们来看一下中序遍历其实和前序遍历一样

   // 二分搜索树的中序遍历
    public void inOrder(){
        inOrder(root);
    }

    // 中序遍历以node为根的二分搜索树, 递归算法
    private void inOrder(Node node){

        if(node == null)
            return;

        inOrder(node.left);
        System.out.println(node.e);
        inOrder(node.right);
    }

这里唯一一点不同的是 先打印左子树，然后是根节点，然后是右子树。下边是她的打印结果。

InorderPrint

大家有没有发现一个好玩的地方，对没错他是按从小到大的顺序排序好的。所以二分搜索树的一个特性就是中序遍历是从小到大的排序好的。

• postOrder
  后续遍历跟之前的前序、中序遍历一样我想大家都可以自己写出代码,这里我们就不过多的解释。

         postOrder(node.left);
         postOrder(node.right);
         System.out.println(node.e);

• remove

//删除以node为根的二分搜索树中元素为e的节点，递归算法
    //返回删除节点后二分搜索树的根
    private Node remove(Node node, E e) {
        if (node == null)
            return null;
        if (e.compareTo(node.e) < 0) {
            node.left = remove(node.left, e);
            return node;
        } else if (e.compareTo(node.e) > 0) {
            node.right = remove(node.right, e);
            return node;
        } else {// e == node.e
            if (node.left == null) {
                Node right = node.right;
                node.right = null;
                size--;
                return right;
            }

            if (node.right == null) {
                Node left = node.left;
                node.left = null;
                size--;
                return left;
            }

            Node successor = mininum(node.right);
            successor.right = removeMin(node.right);
            successor.left = node.left;
            node.left = node.right = null;
            return successor;

        }
    }

删除方法这个比较复杂了，这里也是递归的方式实现。写一个以node为根的节点的方法。如果这个节点为空就返回空，如果传入的元素比当前节点的的元素小，那么就去他的左子树去找；如果传入的元素比当前节点的元素大那么就去他的右子树去找。如果传入的元素等于当前节点那么又有三种情况：如果左子树是空的，那么直接删除这个节点，然后把他的右子树返回就可以了；如果这个节点的右子树为空那么就删除这个节点，然后把它的左子树返回就可以了；如果删除的这个节点左右子树都不为空，那么就吧右子树的最小值放到这个节点上就可以了，当然也可以把左子树的最大值放到这个节点上，这样还满足这是一棵二分搜索树。具体的替换绿色的小球表示要替换旁边红色的小球，红色小球是要被替换的小球。

删除

到这里二分搜索书的基本方法都介绍完了。希望大家可以明白，有什么不明白的可以评论里说。