你的位置:首页 > Java教程

[Java教程][javaSE] 数据结构(二叉树


前序遍历:中,左,右

中序遍历:左,中,右

后序遍历:左,右,中

 

二叉树查找

从根节点进行比较,目标比根节点小,指针移动到左边

从根节点进行比较,目标比根节点大,指针移动到右边

 

  /**   * 前序遍历   * @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