通过二叉查找树实现排序的例程

/**
* 无论排序的对象是什么,都要实现Comparable接口
*
* @param <T>
*/
public class BinaryNode<T extends Comparable<T>> {
private static int index = 0; // 排序下标
private static int len = 0; // 最大数组长度
private T t; // 根节点
private BinaryNode<T> left; // 左侧叶子节点
private BinaryNode<T> right; // 右侧叶子节点 public BinaryNode(T t) {
len++;
this.t = t;
} /**
* 往一颗书中插入值,在本质上都通过根节点一层层的判断。
* 如果根节点不存在则新建节点
* 如果根节点存在则判断应该在左侧还是在右侧插入,通常是左小右大
*
* @param t
*/
public void insert(T t) {
if (this.t.compareTo(t) > 0) {
if (this.left == null) {
BinaryNode<T> node = new BinaryNode<T>(t);
this.left = node;
} else {
this.left.insert(t);
}
} else {
if (this.right == null) {
BinaryNode<T> node = new BinaryNode<T>(t);
this.right = node;
} else {
this.right.insert(t);
}
}
} /**
* 调用私有方法
*
* @return
*/
public Comparable<?>[] order() {
Comparable<?>[] os = new Comparable[len];
order(this, os);
return os;
} /**
* 利用中序遍历查找整颗树
*
* @param bn
* @param os
*/
private void order(BinaryNode<T> bn, Comparable<?>[] os) {
if (bn.left == null) {
os[index++] = bn.t;
} else {
order(bn.left, os);
os[index++] = bn.t;
}
if (bn.right == null) {
return;
} else {
order(bn.right, os);
}
} }
05-04 04:49