一、定義

二叉查找樹（Binary Search Tree），又被成為二叉搜索樹，是一種特殊的二叉樹。

二、特點(diǎn)

1、若任意節(jié)點(diǎn)的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；
2、若任意節(jié)點(diǎn)的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；
3、任意節(jié)點(diǎn)的左、右子樹也分別為二叉查找樹；
4、沒有鍵值相等的節(jié)點(diǎn)。

三、二叉樹舉例

二叉查找樹.png

四、二叉查找樹的實(shí)現(xiàn)

1、節(jié)點(diǎn)類的定義
二叉樹每個(gè)節(jié)點(diǎn)都有三個(gè)必要的屬性，左子樹節(jié)點(diǎn)，右子樹節(jié)點(diǎn)，父親節(jié)點(diǎn)。這里key定義為節(jié)點(diǎn)的值，同時(shí)確定節(jié)點(diǎn)在樹中的位置。

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是二叉樹，它提供了二叉樹的根節(jié)點(diǎn)root屬性及節(jié)點(diǎn)數(shù)屬性（其他深度等屬性省略）；root是TNode類型，而TNode是二叉查找樹的節(jié)點(diǎn)，它是BinarySearchTree的內(nèi)部類。
3、構(gòu)建一顆二叉查找樹實(shí)現(xiàn)

 private void insert(BinarySearchTree<T> sourceTree, TNode<T> inNode) {
    int cmp;
    TNode<T> parentNode=null;
    TNode<T> currentNode=sourceTree.root;
    // 優(yōu)先找到待插入的節(jié)點(diǎn)所對應(yīng)的父親節(jié)點(diǎn)
    while(null != currentNode) {
        parentNode=currentNode;
        cmp=inNode.key.compareTo(currentNode.key);// 將待插入節(jié)點(diǎn)值和當(dāng)前節(jié)點(diǎn)值進(jìn)行比較
        if(cmp < 0) {// 如果比當(dāng)前節(jié)點(diǎn)值小
            currentNode=currentNode.left;// 將當(dāng)前節(jié)點(diǎn)的左子樹當(dāng)作下一次要比較的父親節(jié)點(diǎn)
        } else {// 如果比當(dāng)前節(jié)點(diǎn)值小
            currentNode=currentNode.right;
        }
    }
    // 以上找到了父親節(jié)點(diǎn),再將inNode的父親節(jié)點(diǎn)設(shè)置為parentNode
    inNode.parent=parentNode;
    if(null == parentNode) {// 如果parentNode仍然為空,則將inNode設(shè)置為root節(jié)點(diǎn)
        sourceTree.root=inNode;
    } else {
        cmp=inNode.key.compareTo(parentNode.key);
        if(cmp < 0) { //待插入節(jié)點(diǎn)值比父親節(jié)點(diǎn)值小
            parentNode.left=inNode; //將待插入節(jié)點(diǎn)設(shè)置為父親節(jié)點(diǎn)的左子樹
            size++;
        } else {//待插入節(jié)點(diǎn)值比父親節(jié)點(diǎn)值大
            parentNode.right=inNode;//將待插入節(jié)點(diǎn)設(shè)置為父親節(jié)點(diǎn)的右子樹
            size++;
        }
    }
}

public void insert(T key) {
    TNode<T> z=new TNode<T>(key, null, null, null);
    // 如果新建結(jié)點(diǎn)失敗，則返回。
    if(z != null) {
        insert(this, z);
    }
}

插入新的節(jié)點(diǎn)其實(shí)很簡單，分兩步；第一步：找到父親節(jié)點(diǎn)；第二步，比較待插入節(jié)點(diǎn)值和父親節(jié)點(diǎn)值，如果比父親節(jié)點(diǎn)值小，則被設(shè)置為父親節(jié)點(diǎn)的左子樹，反之設(shè)置為父親節(jié)點(diǎn)的右子樹。
4、二叉查找樹遍歷實(shí)現(xiàn)

//前序遍歷
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);
}

單元測試實(shí)現(xiàn)：

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();
}
}

控制臺打印結(jié)果：

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

構(gòu)建過程如下圖：

構(gòu)建流程.jpg

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;
}

--未完待續(xù)--