public class BSTree>{private BSTNodemRoot;/*** 定义二叉树
*
*@authortaoshihan
*@param
**/
public class BSTNode>{publicT key;publicBSTNode parent, left, right;publicBSTNode(T key, BSTNode parent, BSTNode left, BSTNode right) {this.key =key;this.parent =parent;this.left =left;this.right =right;
}
}public voidinsert(BSTree bsTree, BSTNode bstNode) {
BSTNode parent= null;
BSTNode x=bsTree.mRoot;//查找bstNode的插入位置，x的指针指对
while (x != null) {
parent= x;//把x的位置作为节点的父类
int flag =bstNode.key.compareTo(x.key);if (flag < 0) {
x=x.left;
}else{
x=x.right;
}
}//插入
bstNode.parent =parent;if(parent==null){
bsTree.mRoot=bstNode;
}else{int flag =bstNode.key.compareTo(parent.key);if (flag < 0) {
parent.left=bstNode;
}else{
parent.right=bstNode;
}
}
}/*** 插入根节点
*
*@paramkey*/
public voidinsert(T key) {
BSTNode z = new BSTNode(key, null, null, null);//如果新建结点失败，则返回。
if (z != null)
insert(this, z);
}/** 打印"二叉查找树"
*
* key -- 节点的键值
* direction -- 0，表示该节点是根节点;
* -1，表示该节点是它的父结点的左孩子;
* 1，表示该节点是它的父结点的右孩子。*/
private void print(BSTNode tree, T key, intdirection) {if(tree != null) {if(direction==0) //tree是根节点
System.out.printf("%2d is root\n", tree.key);else //tree是分支节点
System.out.printf("%2d is %2d's %6s child\n", tree.key, key, direction==1?"right" : "left");
print(tree.left, tree.key,-1);
print(tree.right,tree.key,1);
}
}public void print(BSTreetree) {if (tree.mRoot != null){
print(tree.mRoot, tree.mRoot.key,0);
}
}/***@paramargs*/
public static voidmain(String[] args) {
BSTree tree= newBSTree();
tree.insert(3);
tree.insert(1);
tree.insert(2);
tree.insert(5);
tree.insert(4);
tree.insert(6);
tree.print(tree);
}
}