二叉查找树

一、定义

二叉查找树（Binary Search Tree），又被成为二叉搜索树，是一种特殊的二叉树。

二、特点

1、若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2、若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3、任意节点的左、右子树也分别为二叉查找树；
4、没有键值相等的节点。

三、二叉树举例

二叉查找树.png

四、二叉查找树的实现

1、节点类的定义
二叉树每个节点都有三个必要的属性，左子树节点，右子树节点，父亲节点。这里key定义为节点的值，同时确定节点在树中的位置。

public class TNode<T extends Comparable<T>> {
    T key;
    TNode<T> left;
    TNode<T> right;
    TNode<T> parent;
    public TNode(T key, TNode<T> left, TNode<T> right, TNode<T> parent) {
        this.key=key;
        this.left=left;
        this.right=right;
        this.parent=parent;
    }
    public T getKey() {
        return key;
    }
}

2、二叉树类的定义

public class BinarySearchTree<T extends Comparable<T>> {
    private TNode<T> root;
    private int size;
    public class TNode<T extends Comparable<T>> {
        T key;
        TNode<T> left;
        TNode<T> right;
        TNode<T> parent;
        public TNode(T key, TNode<T> left, TNode<T> right, TNode<T> parent) {
            this.key=key;
            this.left=left;
            this.right=right;
            this.parent=parent;
        }
        public T getKey() {
            return key;
        }
    }
    public TNode<T> getRoot() {
        return root;
    }
    public void setRoot(TNode<T> root) {
        this.root=root;
    }
    public int getSize() {
        return size;
    }
    public void setSize(int size) {
        this.size=size;
    }
    ......
}

BinarySearchTree是二叉树，它提供了二叉树的根节点root属性及节点数属性（其他深度等属性省略）；root是TNode类型，而TNode是二叉查找树的节点，它是BinarySearchTree的内部类。
3、构建一颗二叉查找树实现

 private void insert(BinarySearchTree<T> sourceTree, TNode<T> inNode) {
    int cmp;
    TNode<T> parentNode=null;
    TNode<T> currentNode=sourceTree.root;
    // 优先找到待插入的节点所对应的父亲节点
    while(null != currentNode) {
        parentNode=currentNode;
        cmp=inNode.key.compareTo(currentNode.key);// 将待插入节点值和当前节点值进行比较
        if(cmp < 0) {// 如果比当前节点值小
            currentNode=currentNode.left;// 将当前节点的左子树当作下一次要比较的父亲节点
        } else {// 如果比当前节点值小
            currentNode=currentNode.right;
        }
    }
    // 以上找到了父亲节点,再将inNode的父亲节点设置为parentNode
    inNode.parent=parentNode;
    if(null == parentNode) {// 如果parentNode仍然为空,则将inNode设置为root节点
        sourceTree.root=inNode;
    } else {
        cmp=inNode.key.compareTo(parentNode.key);
        if(cmp < 0) { //待插入节点值比父亲节点值小
            parentNode.left=inNode; //将待插入节点设置为父亲节点的左子树
            size++;
        } else {//待插入节点值比父亲节点值大
            parentNode.right=inNode;//将待插入节点设置为父亲节点的右子树
            size++;
        }
    }
}

public void insert(T key) {
    TNode<T> z=new TNode<T>(key, null, null, null);
    // 如果新建结点失败，则返回。
    if(z != null) {
        insert(this, z);
    }
}

插入新的节点其实很简单，分两步；第一步：找到父亲节点；第二步，比较待插入节点值和父亲节点值，如果比父亲节点值小，则被设置为父亲节点的左子树，反之设置为父亲节点的右子树。
4、二叉查找树遍历实现

//前序遍历
private void preOrder(TNode<T> node) {
    if(null != node) {
        System.out.print(node.key + " ");
        preOrder(node.left);
        preOrder(node.right);
    }
}
public void preOrder() {
    preOrder(root);
}
//后序遍历
private void postOrder(TNode<T> node) {
    if(null != node) {
        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node.key + " ");
    }
}
public void postOrder() {
    postOrder(root);
}
//中序遍历
private void inOrder(TNode<T> node) {
    if(null != node) {
        postOrder(node.left);
        System.out.print(node.key + " ");
        postOrder(node.right);
    }
}
public void inOrder() {
    inOrder(root);
}

单元测试实现：

public static void main(String[] args) {
    int[] arr={1, 5, 4, 3, 2, 6};
    int i, ilen;
    BinarySearchTree<Integer> tree=new BinarySearchTree<Integer>();
    System.out.print("依次添加: ");
    ilen=arr.length;
    for(i=0; i < ilen; i++) {
        System.out.print(arr[i] + " ");
        tree.insert(arr[i]);
    }
    System.out.print("\n前序遍历: ");
    tree.preOrder();
    System.out.print("\n中序遍历: ");
    tree.inOrder();
    System.out.print("\n后序遍历: ");
    tree.postOrder();
}
}

控制台打印结果：

依次添加: 1 5 4 3 2 6 
前序遍历: 1 5 4 3 2 6 
中序遍历: 1 2 3 4 6 5 
后序遍历: 2 3 4 6 5 1 

构建过程如下图：

构建流程.jpg
5、元素查找

private TNode<T> search(TNode<T> node, T key) {
    if(null == node) {
        return node;
    }
    int cmp=key.compareTo(node.key);
    if(cmp < 0) {
        return search(node.left, key);
    } else if(cmp > 0) {
        return search(node.right, key);
    }
    return node;
}
public TNode<T> search(T key) {
    return search(root, key);
}

5、查找最大值与最小值

//查询最大值
private TNode<T> max(TNode<T> tree) {
    if(null == tree) {
        return tree;
    }
    while(null != tree.right) {
        tree=tree.right;
    }
    return tree;
}
public T max() {
    TNode<T> node=max(root);
    if(null != node) {
        return node.key;
    }
    return null;
}

//查询最小值
private TNode<T> min(TNode<T> tree) {
    if(null == tree) {
        return tree;
    }
    while(null != tree.left) {
        tree=tree.left;
    }
    return tree;
}
public T min() {
    TNode<T> node=min(root);
    if(null != node) {
        return node.key;
    }
    return null;
}

--未完待续--