| Blog信息 |
|
blog名称:
日志总数:1304
评论数量:2242
留言数量:5
访问次数:7607019
建立时间:2006年5月29日 |
| |
|
 [算法]二叉树
软件技术
lhwork 发表于 2006/12/11 11:17:48 |
| 和堆类似，二叉树也是一种很奇特的数据结构。它包含了根节点，节点最多只有一个左右节点。
父节点和左右子节点之间有一定的关系：
1. 父节点比左节点大（小）。
2. 父节点比右节点小（大）。
通过这种特性，二叉树的查找定位非常方便，比数组、链表的查找效率要高很多。在我的机器上，从100万个随机整数中查找一个整数平均需要0.00386毫秒。可见效率确实很高。
不过，二次树有一个致命的缺点：如果插入的数是经过排序的，则会使二次树高度非常大，就等同于线性数组了，从而极大影响了查找和插入的效率。
下面是二叉树的Java实现代码。
package cn.tenyears.demo;
import java.util.Comparator;
/**
* Binary Tree
*
* @author taolue
*
*/
public class BinTree<T> {
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");
}
} |
|
|