和堆類(lèi)似，二叉樹(shù)也是一種很奇特的數(shù)據(jù)結(jié)構(gòu)。它包含了根節(jié)點(diǎn)，節(jié)點(diǎn)最多只有一個(gè)左右節(jié)點(diǎn)。
父節(jié)點(diǎn)和左右子節(jié)點(diǎn)之間有一定的關(guān)系：
1. 父節(jié)點(diǎn)比左節(jié)點(diǎn)大（?。?br />
2. 父節(jié)點(diǎn)比右節(jié)點(diǎn)?。ù螅?。
通過(guò)這種特性，二叉樹(shù)的查找定位非常方便，比數(shù)組、鏈表的查找效率要高很多。在我的機(jī)器上，從100萬(wàn)個(gè)隨機(jī)整數(shù)中查找一個(gè)整數(shù)平均需要0.00386毫秒?？梢?jiàn)效率確實(shí)很高。
不過(guò)，二次樹(shù)有一個(gè)致命的缺點(diǎn)：如果插入的數(shù)是經(jīng)過(guò)排序的，則會(huì)使二次樹(shù)高度非常大，就等同于線性數(shù)組了，從而極大影響了查找和插入的效率。
下面是二叉樹(shù)的Java實(shí)現(xiàn)代碼。
package cn.tenyears.demo;
import java.util.Comparator;
/**
* Binary Tree
*
* @author taolue
*
*/
public class BinTree<T> {
/**
* 樹(shù)節(jié)點(diǎn)
*/
public class Node {
private T data;
private Node left;
private Node right;
public void setData(T data) {
this.data = data;
}
public void setLeft(Node left) {
this.left = left;
}
public void setRight(Node right) {
this.right = right;
}
public Node getLeft() {
return this.left;
}
public Node getRight() {
return this.right;
}
public T getData() {
return this.data;
}
public Node(T data, Node l, Node r) {
this.data = data;
this.left = l;
this.right = r;
}
}
class ParentAndChild {
public Node parent = null;
public Node child = null;
public ParentAndChild(Node p, Node c) {
this.parent = p;
this.child = c;
}
}
private Comparator<T> comparator = null;;
public final ParentAndChild NONE_PC = new ParentAndChild(null, null);
private Node root = null;
private int treeSize = 0;
public BinTree(Comparator<T> comparator) {
this.comparator = comparator;
}
public Node search(T data) {
return searchPC(data).child;
}
public void insert(T data) {
Node temp = root;
Node parent = null;
int equal = 0;
while (temp != null) {
parent = temp;
equal = comparator.compare(data, temp.getData());
if (equal < 0)
temp = temp.getLeft();
else
temp = temp.getRight();
}
Node one = new Node(data, null, null);
if (parent == null)
root = one;
else if (comparator.compare(data, parent.getData()) < 0)
parent.setLeft(one);
else
parent.setRight(one);
this.treeSize++;
}
public boolean delete(T data) {
Node deleted = null;
Node parent = null;
Node right = null;
ParentAndChild pc = this.searchPC(data);
deleted = pc.child;
parent = pc.parent;
if (deleted == null)
return false;
if (deleted.getRight() == null)
right = deleted.getLeft();
else if (deleted.getLeft() == null)
right = deleted.getRight();
else {
Node parent1 = deleted;
right = deleted.getLeft();
while (right.getRight() != null) {
parent1 = right;
right = right.getRight();
}
if (parent1 == deleted)
right.setRight(deleted.getRight());
else {
parent1.setRight(right.getLeft());
right.setLeft(deleted.getLeft());
right.setRight(deleted.getRight());
}
}
if (parent == null)
root = right;
else if (comparator.compare(deleted.getData(), parent.getData()) < 0)
parent.setLeft(right);
else
parent.setRight(right);
this.treeSize--;
return true;
}
public int getSize() {
return this.treeSize;
}
private ParentAndChild searchPC(T data) {
Node temp = root;
Node parent = null;
int equal = 0;
while (temp != null) {
equal = comparator.compare(data, temp.getData());
if (equal == 0)
break;
else {
parent = temp;
if (equal < 0)
temp = parent.getLeft();
else
temp = parent.getRight();
}
}
if (temp != null)
return new ParentAndChild(parent, temp);
return this.NONE_PC;
}
public static void main(String[] args) {
Comparator<Integer> com = new Comparator<Integer>() {
public int compare(Integer o1, Integer o2) {
return o1.compareTo(o2);
}
};
BinTree<Integer> tree = new BinTree<Integer>(com);
int size = 1000000;
Integer[] a = new Integer[size];
for (int i = 0; i < size; i++) {
a[i] = Integer.valueOf((int) Math.round(Math.random() * size));
tree.insert(a[i]);
}
long start = System.currentTimeMillis();
// find
for (int i = 0; i < size; i++) {
if (tree.search(a[i]) == null)
System.out.println("Error: Find None.");
}
long end = System.currentTimeMillis();
System.out.println("Last(AVG): " + (end - start) * 1.0f / size + " ms");
}
}