前序遍历:中,左,右
中序遍历:左,中,右
后序遍历:左,右,中
二叉树查找
从根节点进行比较,目标比根节点小,指针移动到左边
从根节点进行比较,目标比根节点大,指针移动到右边
/**
* 前序遍历
* @param tree
*/
public void preOrder(BSTree tree){
preOrder(tree.mRoot);
}
public void preOrder(BSTNode node){
if(node!=null){
System.out.print(node.key+"");
preOrder(node.left);
preOrder(node.right);
}
}
/**
* 中序遍历
* @param tree
*/
public void midOrder(BSTree tree){
midOrder(tree.mRoot);
}
public void midOrder(BSTNode node){
if(node!=null){
midOrder(node.left);
System.out.print(node.key+"");
midOrder(node.right);
}
}
/**
* 后序遍历
* @param tree
*/
public void postOrder(BSTree tree){
postOrder(tree.mRoot);
}
public void postOrder(BSTNode node){
if(node!=null){
postOrder(node.left);
postOrder(node.right);
System.out.print(node.key+"");
}
}
/**
* 二叉树的查找
* @param tree
* @param key
* @return
*/
public BSTNode<T> search(BSTree<T> tree,T key){
BSTNode<T> mRoot=tree.mRoot;
while(mRoot!=null){
int flag=key.compareTo(mRoot.key);
if(flag<0){
mRoot=mRoot.left;
}else if(flag>0){
mRoot=mRoot.right;
}else{
return mRoot;
}
}
return mRoot;
}
tree.preOrder(tree);//输出 312546
tree.midOrder(tree);//输出 123456
tree.postOrder(tree);//输出 214653
BSTree.BSTNode node=tree.search(tree, 5);
System.out.println(node.left.key);//输出 4