学步园

      当进行插入，删除和查找操作中，二叉查找树的性能比迄今为止所研究的任何一种数据结构都好。

1. 二叉查找树：是一棵二叉树，它可以为空，也可以不为空，有如下的性质：

     1）. 每个元素都有关键字，并且关键字是唯一的。

      2） 非空左子树的关键字值一定小于其子树根结点的关键字值。

     3） 非空右子树的关键字值一定大于其子树根结点的关键字值。

     4）左，右子树仍然是二叉查找树。

   简言之就是左孩子要小于父亲，右孩子要大于父亲。示例如下：

下面以上图为例，说明对二叉查找树的各种操作；

2. 二叉查找树的查找

package com.lyj.binary_search_tree;

public class BStree {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // 初始化结点
        BTNode n1 = new BTNode(8);
        BTNode n2 = new BTNode(3);
        BTNode n3 = new BTNode(10);
        BTNode n4 = new BTNode(1);
        BTNode n5 = new BTNode(6);
        BTNode n6 = new BTNode(14);
        BTNode n7 = new BTNode(4);
        BTNode n8 = new BTNode(7);
        BTNode n9 = new BTNode(13);

        // n1的左右子树，后面同理
        n1.setLeftChild(n2);
        n1.setRightChild(n3);

        n2.setLeftChild(n4);
        n2.setRightChild(n5);

        n3.setRightChild(n6);

        n5.setLeftChild(n7);
        n5.setRightChild(n8);

        n6.setLeftChild(n9);

        BTTreeOption btTreeOption = new BTTreeOption();

        // 查找测试
        // BTNode resultNode = btTreeOption.query(n1, 14);
        // System.out.println(resultNode.getValue());

        // 插入测试
        // btTreeOption.insert(n1, 80);
        // BTNode resultNode1 = btTreeOption.query(n1, 14);
        // System.out.println(resultNode1.getRightChild().getValue());
        // btTreeOption.insert(n1, 5);
        // BTNode resultNode2 = btTreeOption.query(n1, 4);
        // System.out.println(resultNode2.getRightChild().getValue());

        // 查找最小元素
        // BTNode minElement = btTreeOption.queryMin(n1);
        // System.out.println(minElement.getValue());

        // 查找最大元素
        // BTNode minElement = btTreeOption.queryMax(n1);
        // System.out.println(minElement.getValue());

        // 删除测试
        // btTreeOption.insert(n1, 80);
        // BTNode resultNode1 = btTreeOption.query(n1, 14);
        // System.out.println(resultNode1.getRightChild().getValue());
        // btTreeOption.delete(n1, 80);
        // System.out.println(resultNode1.getRightChild()== null);
    }
}

/*
 * 结点
 */
class BTNode {
    private int value;
    private BTNode leftChild, rightChild;

    public BTNode() {
        value = 0;
        leftChild = null;
        rightChild = null;
    }

    public BTNode(int value, BTNode leftChild, BTNode rightChild) {
        this.value = value;
        this.leftChild = leftChild;
        this.rightChild = rightChild;
    }

    public BTNode(int value) {
        this(value, null, null);
    }

    public BTNode getLeftChild() {
        return leftChild;
    }

    public void setLeftChild(BTNode leftChild) {
        this.leftChild = leftChild;
    }

    public BTNode getRightChild() {
        return rightChild;
    }

    public void setRightChild(BTNode rightChild) {
        this.rightChild = rightChild;
    }

    public int getValue() {
        return value;
    }

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

/*
 * 二叉查找树的操作
 */
class BTTreeOption {

    // 查找
    public BTNode query(BTNode rootNode, int key) {
        if (rootNode != null) {
            if (key == rootNode.getValue()) {
                return rootNode;
            } else if (key < rootNode.getValue()) {
                // 用于insert操作时返回最后一个结点，在insert中将新结点作为返回结点的左孩子
                if (rootNode.getLeftChild() == null) {
                    return rootNode;
                }
                return query(rootNode.getLeftChild(), key);
            } else {
                // 用于insert操作时返回最后一个结点，在insert中将新结点作为返回结点的右孩子
                if (rootNode.getRightChild() == null) {
                    return rootNode;
                }
                return query(rootNode.getRightChild(), key);
            }
        }
        return null;
    }

    // 插入
    public void insert(BTNode rootNode, int num) {
        BTNode temp = query(rootNode, num);
        if (temp != null) {
            BTNode newNode = new BTNode(num);
            // 选择把这个结点插在最后结点的哪一边
            if (temp.getValue() > num) {
                temp.setLeftChild(newNode);
            } else {
                temp.setRightChild(newNode);
            }
        }
    }

    // 删除
    public BTNode delete(BTNode rootNode, int num) {
        if (rootNode != null) {
            if (num < rootNode.getValue()) {
                rootNode.setLeftChild(delete(rootNode.getLeftChild(), num));
            } else if (num > rootNode.getValue()) {
                rootNode.setRightChild(delete(rootNode.getRightChild(), num));
            } else if ((rootNode.getLeftChild() != null) && (rootNode.getRightChild() != null)) {
                // 用右子树的最小值代替
                BTNode tempNode = queryMax(rootNode.getRightChild());
                rootNode.setValue(tempNode.getValue());
                rootNode.setRightChild(delete(rootNode.getRightChild(), rootNode.getValue()));
            } else {
                // 有0个或1个孩子
                if (rootNode.getLeftChild() == null) {
                    rootNode = rootNode.getRightChild();
                } else if (rootNode.getRightChild() == null) {
                    rootNode = rootNode.getLeftChild();
                }
            }
            return rootNode;
        }

        return null;
    }

    // 查找最小元素 递归实现
    public BTNode queryMin(BTNode rootNode) {
        if (rootNode != null) {
            if (rootNode.getLeftChild() == null) {
                return rootNode;
            } else {
                return queryMin(rootNode.getLeftChild());
            }
        }

        return null;
    }

    // 查找最大元素 非递归实现
    public BTNode queryMax(BTNode rootNode) {
        if (rootNode != null) {
            while (rootNode.getRightChild() != null) {
                rootNode = rootNode.getRightChild();
            }
            return rootNode;
        }

        return null;
    }
}

                                                          插入5和80后的二叉查找树