[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