二叉查找树

引言

我们知道，在查找算法中，性能最好的就是二分查找了，但是二分查找要求数列有序，这样我们每次进行查找时必须对数列进行排序，然后进行查找。所以二分查找适合数据元素很少增减的情况，如果数列经常变动，则不适合采用二分查找。

下面来看看什么是二叉查找树。

二叉查找树的概念

二叉查找树或是棵空树，或者满足一下特性

1.如果它的左子树不为空，那么它的左子树上的任意节点的值都小于根节点的值。

2.如果它的右子树不为空，那么它的右子树上的任意节点的值都大于根节点的值。

3.同样，它的左子树和右子树也都是二叉查找树

很容易发现，这是一个递归的定义，实际上这棵树与递归是分不开的。这里我给出一个二叉查找树的例子

二叉查找树的相关操作

二叉查找树的查找

对于二叉查找树，我们仍然使用二叉树的节点来表示。我们来看看这棵二叉查找树如何查找元素。

因为二叉查找树的特性，如果我们想知道一个元素k是否存在，则只需要进行递归比较

1.先比较根节点，如果相等，则结束；如果为空，则说明无法找到，查找结束。

2.如果k比根节点大，则在这个节点的右子树中查找

3.如果k比根节点小，则在这个节点的左子树种查找

我们根据上面的思路，很容易能写出二叉查找树的实现代码

package cn.csu;


public class BinarySearchTree {
    private BinaryTreeNode root;
    public BinarySearchTree(BinaryTreeNode root){
        this.root = root;
    }

    public BinaryTreeNode search(int data) {
        return search(root,data);
    }
    private BinaryTreeNode search(BinaryTreeNode node,int data){
        if(node == null){
            return null;
        }else if(node.getData() == data){
            return node;
        }else if(data > node.getData()){
            return search(node.getRightNode(),data);
        }else{
            return search(node.getLeftNode(),data);
        }
    }
}

从以上的代码看，查找时非常简单的。

二叉查找树的插入操作

其实二叉查找树的插入操作也很简单，同样按照二叉查找树的查找来看，如果能找到这个元素的值，则直接忽略，因为树中已经有这个元素，如果没有这个值，那么把这个值放到最终查找的位置上就好了。

我们来看代码：

/**
     *
     * @param data
     */
    public void insert(int data){
        if (root == null){
            root = new BinaryTreeNode();
            root.setData(data);
        }else{
            searchAndInsert(root,null,data);
        }
    }

    /**
     * 递归查找二叉查找树（如果没有找到，则新建一个最终位置的节点）
     * @param parent
     * @param node
     * @param data
     * @return
     */
    public BinaryTreeNode searchAndInsert(BinaryTreeNode parent,BinaryTreeNode node,int data){
        if(node == null){
            node = new BinaryTreeNode();
            node.setData(data);
            if(data > parent.getData()){
                parent.setRightNode(node);
            }else{
                parent.setLeftNode(node);
            }
            return node;
        }else if(node.getData() == data){
            return node;
        }else if(data > node.getData()){
            return searchAndInsert(node,node.getRightNode(),data);
        }else{
            return searchAndInsert(node,node.getLeftNode(),data);
        }
    }

二叉查找树的删除操作

二叉查找树的删除操作相对比插入操作复杂一些，如果删除的节点刚好是个叶子结点，则可以直接删除，如果删除的节点有子节点，那就比较麻烦，如果删除的节点只有左子树或者右子树，则直接把孩子节点上移并放到删除的节点的位置就好了，相对比较简单。但是如果删除的节点的左右子树都不为空，那情况就更复杂一些。但是不论操作复杂，还是有办法处理的

对于删除的节点的左右子树都不为空的情况，我们需要从这两棵子树中的一个节点中选出一个节点作为新的根节点，来代替删除的节点，这个节点需要比左边子树的所有元素大，要比右边的子树的所有的节点小，这时怎么选择呢？

首先，这个节点要比所有左子树的节点的值大，那么直接从右子树中选择就可以了，在右子树中必须选择一个最小的，其实这个节点就是右子树中的最左边的节点，或者左子树中最右边的节点，这里约定用右子树中的最左边的节点。

为了方便理解这中情况，我这里给出一个实例

删除前的二叉查找树

删除后的二叉查找树

下面我们来看删除操作的代码：

/**
     * 二叉查找树删除节点
     * @param data
     */
    public void delete(int data){
        if(data == root.getData()){
            root = null;
            return;
        }
        //查找父节点
        BinaryTreeNode parent =searchParent(data);
        if(parent == null){
            return;
        }
        //查找
        BinaryTreeNode node = search(parent,data);
        //如果要删除的节点是叶子节点
        if(node.getLeftNode() != null && parent.getRightNode() != null){
            //如果是叶子节点则直接删除
            if(parent.getLeftNode() != null && parent.getLeftNode().getData() == data){
                parent.setLeftNode(null);
            }else{
                parent.setRightNode(null);
            }
        }else if(node.getLeftNode() != null && node.getRightNode() == null){
            //如果要删除的节点左子树不为空而右子树为空
            if(parent.getLeftNode()!= null && parent.getLeftNode().getData() ==data){
                parent.setLeftNode(node.getLeftNode());
            }else{
                parent.setRightNode(node.getLeftNode());
            }
        }else if(node.getLeftNode() == null && parent.getRightNode() != null){//要删除的节点只有右子树而没有左子树
            if(parent.getLeftNode() !=null && node.getLeftNode().getData()==data){
                parent.setLeftNode(node.getRightNode());
            }else{
                parent.setRightNode(node.getRightNode());
            }
        }else{
            //左右子树都不为空
            //1.查找右子树中最左子节点
            BinaryTreeNode deleteNode = node;//要删除的节点
            BinaryTreeNode temp = node.getRightNode();//要删除元素的右子树树根
            if(temp.getLeftNode() == null){
                //如果右子树没有左孩子，直接上移
                temp.setLeftNode(deleteNode.getLeftNode());
            }else{
                while (temp.getLeftNode() != null){
                    node = temp;
                    temp = temp.getLeftNode();
                }
                //2.继承节点原右子树上移
                node.setLeftNode(temp.getRightNode());
                //3.继承节点就位
                temp.setLeftNode(deleteNode.getLeftNode());
                temp.setRightNode(deleteNode.getRightNode());
            }
            //4.更新父节点为删除节点的原父节点
            if(parent.getLeftNode() != null && parent.getLeftNode().getData()==data){
                parent.setLeftNode(temp);
            }else{
                parent.setRightNode(temp);
            }

        }

    }

    /**
     * 二叉查找树查找父节点
     * @param data
     * @return
     */
    public BinaryTreeNode searchParent(int data){
        return searchParent(root,null,data);
    }

    /**
     * 递归二叉查找树
     * @param parent
     * @param node
     * @param data
     * @return
     */
    public BinaryTreeNode searchParent(BinaryTreeNode parent,BinaryTreeNode node,int data){
        if(node == null){
            return null;
        }else if(node.getData() == data){
            return parent;
        }else if(data > node.getData()){
            return searchParent(node,node.getRightNode(),data);
        }else{
            return searchParent(node,node.getLeftNode(),data);
        }
    }

总结：二叉查找树操作中，最复杂的还是二叉查找树的删除操作，它要考虑三种情况：即要删除节点只有左子树、只有右子树以及左右子树都不为空。而二叉树的查找和插入还是比较简单的，最主要的思想还是利用好递归的思想完成这些操作。