二叉排序树（BST查找、插入、删除、遍历）——基于树的查找（一）

二叉排序树

二叉排序树（Binary Search Tree，BST）：又称二叉查找树，是一种高效的数据结构。

定义

二叉排序树或者是一棵空树，或者是具有如下特性的二叉树：

1. 若左子树不空，则左子树上所有结点的值均小于或等于根结点的值；
2. 若右子树不空，则右子树上所有结点的值均大于或等于根结点的值；

3. 左、右子树也分别为二叉排序树

   如下便是一棵二叉排序树
   

   根据定义，再根据二叉树中序遍历的定义（首先中序遍历二叉树的左子树，在访问二叉树的根结点，最后中序遍历二叉树的右子树），可以得到二叉排序树的重要特性：对一棵二叉排序树进行中序遍历，可以得到一个递增的有序序列。当然，如果将定义稍作修改也可得到一个递减的有序序列，这也是二叉排序树得名的缘由。

二叉排序树的相关操作（查找、插入、遍历、删除）

（1）定义数据类型

首先，定义一个二叉排序树的结点数据类型Node

public class Node {
    private int value;//结点值
    protected Node leftChild;//左孩子结点
    protected Node rightChild;//右孩子结点

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

    public void setValue(int value) {
        this.value = value;
    }

    public int getValue() {
        return value;
    }
}

（2）二叉排序树的查找

由于二叉排序树可以看成是一个有序表，所以在二叉排序树上进行查找类似于折半查找，即逐步缩小查找范围的过程。具体步骤为：

1. 若查找的关键字等于根结点的关键字，查找成功；
2. 若查找的关键字小于根结点的关键字，递归查找左子树；
3. 若查找的关键字大于根结点的关键字，递归查找右子树。
4. 若子树为空，则查找不成功。

代码实现：

    //递归实现二叉排序树查找
    public Node searchBSTByRecursion(Node root, int value) {
        if(root == null) {
            return null;
        }

        if(root.getValue() == value) {//步骤1
            return root;
        } else if(value < root.getValue()) {//步骤2
            return searchBST(root.leftChild, value);
        } else if(value > root.getValue()) {//步骤3
            return searchBST(root.rightChild, value);
        }

        return null;//如果没找到，就返回null
    }

    //非递归实现二叉排序树查找
    public Node searchBST(Node root, int value) {
        Node temp = root;
        while(temp != null) {
            if(temp.getValue() == value) {
                return temp;
            }
            if(value < temp.getValue()) {
                temp = temp.leftChild;
            } else {
                temp = temp.rightChild;
            }
        }

        return null;
    }

（3）二叉排序树的插入

首先查找待插入的记录是否在树中，如果存在，则不允许插入重复关键字；如果直到找到叶子结点仍没有发现重复关键字，则把待插结点作为新的叶子结点插入。
具体步骤为：

1. 若二叉排序树为空树，则新插入的结点为新的根结点；
2. 否则，新插入的结点必为一个新的叶子结点，其插入位置由查找不成功的位置确定。

代码实现：

    //递归实现二叉排序树的插入
    public void insertBST(Node root, int value) {
        if(root == null) {
            root = new Node(value);
            root.leftChild = null;
            root.rightChild = null;
        }

        if(value > root.getValue()) {
            if(root.rightChild == null) {
                root.rightChild = new Node(value);
            } else {
                insertBST(root.rightChild, value);
            }
        } else {
            if(root.leftChild == null) {
                root.leftChild = new Node(value);
            } else {
                insertBST(root.leftChild, value);
            }
        }
    }

（4）二叉排序树的遍历

一般而言，二叉树的遍历方式：

1. DLR：先序遍历；
2. LDR：中序遍历；
3. LRD：后续遍历。

代码实现（递归实现）：

//先序遍历
    public void preOrder(Node root) {
        if(root != null) {
            System.out.print(root.getValue() + " ");
            preOrder(root.leftChild);
            preOrder(root.rightChild);
        }
    }

    //中序遍历
    public void inOrder(Node root) {
        if(root != null) {
            inOrder(root.leftChild);
            System.out.print(root.getValue() + " ");
            inOrder(root.rightChild);
        }

    //后序遍历
    public void postOrder(Node root) {
        if(root != null) {
            postOrder(root.leftChild);
            postOrder(root.rightChild);
            System.out.print(root.getValue() + " ");
        }
    }

（5）二叉排序树的删除

由于二叉排序树要求关键字之间满足一定的大小关系，这就使得从树中删除一个结点的算法相对复杂。
具体步骤：

1. 首先在二叉排序树中查找待删结点，如果不存在则不作任何操作；
2. 否则，分以下三种情况进行讨论：
   （1）待删结点是叶子结点；
   （2）待删结点只有左子树或只有右子树；
   （3）待删结点既有左子树，也有右子树。

分情况来看：
先看第（1）中情况。删除叶子结点。

可以看出，此种情况只需要将待删结点的父结点的相应孩子引用置为null。
再来看第（2）种情况。

1. 只有左子树。
   

2. 只有右子树。
   

   可以看出，此种情况只需将待删结点的父结点的相应孩子引用置为该孩子对应的左子树或右子树。
   最后来看第三种情况。
   利用二叉排序树的中序遍历结果为有序序列，找到替换待删结点的位置，其实就是待删结点的直接前驱或直接后继结点。
   （1）首先确定替换待删结点的位置：
   以待删结点为划分，其左子树就是它的前驱结点，左子树的最右下角的结点即为待删结点的直接前驱结点；其右子树就是它的后继结点，右子树的最左下角的结点即为待删结点的直接后继结点。
   （2）删除替换结点：
   仔细分析，替换结点的删除就是刚刚讨论的前两种情况。替换结点或者恰好就是个叶子结点，或者就是只带了左子树或右子树的情况。如图。
   
   综合以上三种情况，二叉排序树的删除算法代码实现：

//二叉排序树的删除
    public Node deleteBST(Node root, int value) {
        Node cur = root;    //当前结点
        Node parent = null; //待删结点的父结点
        Node delNode = null;    //在后面用来引用待删结点
        Node temp = null;       //作为一个局域内的根结点

        //查找待删结点p和待删结点的父结点f
        while(cur != null) {
            if(value == cur.getValue()) {
                break;
            }
            parent = cur;
            if(value > cur.getValue()) {
                cur = cur.rightChild;
            } else {
                cur = cur.leftChild;
            }
        }

        //当前结点为null，即没有找到待删结点。  此时cur指向待删结点
        if(cur == null) {
            return null;
        }
        //待删结点只有右子树
        if(cur.leftChild == null) {
            //待删结点的父结点为null，即待删结点为根结点
            if(parent == null) {
                //根结点为待删结点的右子树
                root = cur.rightChild;
            } else if(parent.leftChild == cur) {    //待删结点为父结点的左子树
                //把待删结点的右子树作为待删结点父结点的左子树
                parent.leftChild = cur.rightChild;
            } else {                        //待删结点为父结点的右子树
                parent.rightChild = cur.rightChild;
            }
        } else {//待删结点有左子树，要找左子树的最右下角的结点
            temp = cur;
            delNode = cur.leftChild;    //此时s指向待删结点
            while(delNode.rightChild != null) {//查找待删结点的最右下角结点
                temp = delNode;
                delNode = delNode.rightChild;
            }
            if(temp == cur) {//即，待删结点没有右子树，把左子树向上移动
                temp.leftChild = delNode.leftChild;
            } else {//即，待删结点有右子树
                temp.rightChild = delNode.leftChild;
            }
            cur.setValue(delNode.getValue());
        }

        return root;
    }

（6）二叉排序树的性能分析

二叉排序树的查找最差的情况与顺序查找相同，ASL=(n+1)/2，如图；最好的情况与折半查找相同，ASL可以达到对数级logn（以2为底），如图所示。

对于二叉排序树的插入和删除来说，只需修改某些结点的引用，不需要大量移动其他记录，动态查找的效率很高。

基于树的查找第二篇：平衡二叉树
基于树的查找第三篇：红黑树

参考资料：《数据结构与算法》 王曙燕 主编 王春梅 副主编 人民邮电出版社