一、定義
二叉查找樹(shù)（Binary Search Tree）茉继，又被成為二叉搜索樹(shù)咧叭，是一種特殊的二叉樹(shù)。
二烁竭、特點(diǎn)
1菲茬、若任意節(jié)點(diǎn)的左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值派撕；
2婉弹、若任意節(jié)點(diǎn)的右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值终吼；
3镀赌、任意節(jié)點(diǎn)的左、右子樹(shù)也分別為二叉查找樹(shù)际跪；
4商佛、沒(méi)有鍵值相等的節(jié)點(diǎn)。
三姆打、二叉樹(shù)舉例
四良姆、二叉查找樹(shù)的實(shí)現(xiàn)
1、節(jié)點(diǎn)類的定義
二叉樹(shù)每個(gè)節(jié)點(diǎn)都有三個(gè)必要的屬性幔戏，左子樹(shù)節(jié)點(diǎn)玛追，右子樹(shù)節(jié)點(diǎn)，父親節(jié)點(diǎn)闲延。這里key定義為節(jié)點(diǎn)的值痊剖，同時(shí)確定節(jié)點(diǎn)在樹(shù)中的位置伯复。
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、二叉樹(shù)類的定義
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是二叉樹(shù)邢笙，它提供了二叉樹(shù)的根節(jié)點(diǎn)root屬性及節(jié)點(diǎn)數(shù)屬性（其他深度等屬性省略）啸如；root是TNode類型，而TNode是二叉查找樹(shù)的節(jié)點(diǎn)氮惯，它是BinarySearchTree的內(nèi)部類叮雳。
3、構(gòu)建一顆二叉查找樹(shù)實(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)所對(duì)應(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)的左子樹(shù)當(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)的左子樹(shù)
size++;
} else {//待插入節(jié)點(diǎn)值比父親節(jié)點(diǎn)值大
parentNode.right=inNode;//將待插入節(jié)點(diǎn)設(shè)置為父親節(jié)點(diǎn)的右子樹(shù)
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ǎn)單，分兩步杨箭；第一步：找到父親節(jié)點(diǎn)寞焙；第二步，比較待插入節(jié)點(diǎn)值和父親節(jié)點(diǎn)值互婿，如果比父親節(jié)點(diǎn)值小捣郊，則被設(shè)置為父親節(jié)點(diǎn)的左子樹(shù)，反之設(shè)置為父親節(jié)點(diǎn)的右子樹(shù)慈参。
4呛牲、二叉查找樹(shù)遍歷實(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);
}
單元測(cè)試實(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();
}
}
控制臺(tái)打印結(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)建過(guò)程如下圖：
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;
}
--未完待續(xù)--
