一、定义
二叉查找树（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;
}
--未完待续--
