查找二叉樹首先也是個二叉樹，符合二叉樹的一切特點。
原文地址:http://blog.csdn.net/qq_25806863/article/details/74638590
簡單介紹
但是查找二叉樹要求對樹中的每個節(jié)點，這個節(jié)點的左子樹中所有的值要小于自己丧失，右子樹中所有的值要大于自己腿堤。
下面是兩個的區(qū)別：
查找二叉樹：
查找二叉樹
不是查找二叉樹：
不是查找二叉樹
簡單實現(xiàn)
主要是查詢，插入和刪除的方法
public class MySearchTree<E extends Comparable<E>> {
private BinaryNode<E> root;
public MySearchTree() {
root = null;
}
public void makeEmpty() {
root = null;
}
public boolean isEmpty() {
return root == null;
}
public boolean contains(E x) {
return contains(x, root);
}
public E findMin() {
return findMin(root).element;
}
public E findMax() {
return findMax(root).element;
}
public void insert(E x) {
root = insert(x, root);
}
public void remove(E x) {
remove(x, root);
}
public void printTree() {
printTree(root);
}
/**
* 如果這個樹上的值就是要查找的x厅克，返回true
* 如果樹為空，說明不存在這個值橙依，返回false
* 如果x小于這個樹上的值证舟，就在這個樹的左子樹上遞歸查找
* 如果x大于這個樹上的值，就在這個樹的右子樹上遞歸查找
*/
private boolean contains(E x, BinaryNode<E> tree) {
if (tree == null) {
return false;
}
int compareResult = x.compareTo(tree.element);
if (compareResult < 0) {
return contains(x, tree.left);
} else if (compareResult > 0) {
return contains(x, tree.right);
} else {
return true;
}
}
/**
* 只要有左子樹就一直往左找窗骑，左子樹為空說明這個就是最小值
*/
private BinaryNode<E> findMin(BinaryNode<E> tree) {
if (tree == null) {
return null;
} else if (tree.left == null) {
return tree;
} else {
return findMin(tree.left);
}
}
/**
* 只要有右子樹就一直往左找女责，右子樹為空說明這個就是最大值
*/
private BinaryNode<E> findMax(BinaryNode<E> tree) {
if (tree == null) {
return null;
} else if (tree.right == null) {
return tree;
} else {
return findMax(tree.right);
}
}
/**
* 如果要插入的樹是null，說明這個就是要插入的值該放的位置创译，new一個子樹抵知，綁定到對應(yīng)的父親上
* 如果樹不為null，說明這個樹上有值软族，拿x和這個值進(jìn)行比較
* 如果兩個值相等刷喜，說明已經(jīng)有這個值了，可以進(jìn)行一些處理
* 如果x小于樹上的值立砸，就往該樹的左子樹上遞歸插入
* 如果x大于樹上的值掖疮，就往該樹的右子樹上遞歸插入
*/
private BinaryNode<E> insert(E x, BinaryNode<E> tree) {
if (tree == null) {
return new BinaryNode<E>(x, null, null);
}
int compareResult = x.compareTo(tree.element);
if (compareResult < 0) {
tree.left= insert(x, tree.left);
} else if (compareResult > 0) {
tree.right = insert(x, tree.right);
} else {
//說明已經(jīng)有這個值了。
System.out.println("已經(jīng)有這個值了");
}
return tree;
}
/**
* 比較x和樹的值
* 如果x小于樹的值颗祝，在樹的左子樹中遞歸刪除
* 如果x大于樹的值浊闪，在樹的右子樹中遞歸刪除
* 如果x等于樹的值，那么這個值就是要刪除的值螺戳。
* 因為刪除一個值就要對樹進(jìn)行重新排列搁宾，所以這個位置上不能空。
* 如果這個樹只有一個子樹倔幼，那么就直接把這個子樹放在這個位置上
* 如果這個樹有兩個子樹盖腿，那么需要找到右子樹的最小值，將這個最小值賦值在要刪除的位置上凤藏，
* 然后遞歸調(diào)用從右子樹中刪除剛剛找到的這個最小值
*/
private BinaryNode<E> remove(E x, BinaryNode<E> tree) {
if (tree == null) {
//沒有這個樹
return tree;
}
int compareResult = x.compareTo(tree.element);
if (compareResult < 0) {
tree.left = remove(x, tree.left);
} else if (compareResult > 0) {
tree.right = remove(x, tree.right);
} else if (tree.left != null && tree.right != null) {
tree.element = findMin(tree.right).element;
tree.right = remove(tree.element, tree.right);
} else {
tree = (tree.left != null) ? tree.left : tree.right;
}
return tree;
}
private void printTree(BinaryNode<E> tree) {
if (tree == null) {
return;
}
System.out.print(tree.element+" ");
printTree(tree.left);
printTree(tree.right);
}
public static class BinaryNode<E> {
E element;
BinaryNode<E> left;
BinaryNode<E> right;
public BinaryNode(E element) {
this(element, null, null);
}
public BinaryNode(E element, BinaryNode<E> left, BinaryNode<E> right) {
this.element = element;
this.left = left;
this.right = right;
}
}
}
實現(xiàn)的缺點
在代碼中奸忽，注意remove方法中的一段代碼：
else if (tree.left != null && tree.right != null) {
tree.element = findMin(tree.right).element;
tree.right = remove(tree.element, tree.right);
這里對刪除的處理是，找到右子樹中的最小值揖庄，把這個最小值放在當(dāng)前節(jié)點上栗菜，然后從右子樹中刪除這個值。
而在insert的時候蹄梢，是根據(jù)比較而隨機(jī)的插入在左右子樹上的疙筹。
所以如果交叉調(diào)用insert和remove很多次的話富俄，這個二叉樹會變得很不平衡，即左右子樹的高度差很大而咆。
這種平衡的查找二叉樹叫平衡查找樹霍比。
一個最古老的平衡查找樹是AVL樹。
參考《數(shù)據(jù)結(jié)構(gòu)與算法分析java版》
