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