public class BSTNode<T extends Comparable<T>> {
T key; // 关键字(键值)
BSTNode<T> left; // 左孩子
BSTNode<T> right; // 右孩子
BSTNode<T> parent; // 父结点
public BSTNode(T key, BSTNode<T> parent, BSTNode<T> left, BSTNode<T> right) {
this.key = key;
this.parent = parent;
this.left = left;
this.right = right;
}
public T getKey() {
return key;
}
public String toString() {
return "key:" + key;
}
}
层次遍历的算法参考自【编程之美】，源代码中使用了stl的vector实现动态扩展属性，在java里面List的特点很符合要求，故将此处改为ArrayList。
BSTree.java
private void levelOrder(BSTNode<T> tree){
if(tree==null){
return;
}
ArrayList<BSTNode<T>> list = new ArrayList<BSTNode<T>>();//使用了List的动态扩展
list.add(tree);
int cur = 0;
int last = 1;
//cur小于list.size()时，说明当前层尚未被访问.因此，依次访问cur到last直接的所有节点
//并依次将被访问节点的左右子节点压入list
//cur==last，说明该层已被访问完，此时数组中还有未被访问到的节点，
while(cur < list.size()){
last = list.size();//记录了当前层最后一个节点的位置。
while(cur < last){
//当当前节点序号小于list中最后一个节点序号时，就输出当前的节点，并把左右节点插入到list中
System.out.print(list.get(cur)+" ");
if(list.get(cur).left != null){
list.add(list.get(cur).left);
}
if(list.get(cur).right != null){
list.add(list.get(cur).right);
}
cur++;//当前节点遍历完，沿list顺序后移。
}
System.out.println();
}
}
public void levelOrder(){
levelOrder(mRoot);
}
public class BSTreeTest {
public static void main(String[] args) {
BSTree<Integer> test = new BSTree<Integer>();
test.insert(7);
test.insert(4);
test.insert(5);
test.insert(6);
test.insert(12);
test.insert(10);
test.insert(8);
test.insert(9);
test.insert(11);
test.print();
System.out.println("层次遍历");
test.levelOrder();
}