michael

遞歸算法和非遞歸算法本質是一樣的。
遍歷時從根節點開始訪問，訪問左子樹，關鍵是把樹的訪問順序搞清楚。
當遍歷完以后又是根節點。

遞歸函數實際上就是棧的操作。
所謂的先根就是先visit完根節點，然后再遍歷左子樹，遍歷右子樹。
 
template <class T>
void recpretraverse(struct node<T>*&Tree)
{
    if(Tree == NULL) return;
    visitnode(Tree);
    recpretraverse(Tree->left);
    recpretraverse(Tree->right);
}

對應的非遞歸算法就是彈出項，看如果是樹，如果右子樹存在則壓入右子樹，左子樹存在則壓入左子樹，最后壓入節點（tag域變化）。
                            看如果是節點，則訪問節點。
可以看出需要一個tag域來表示彈出節點還是樹。但是前序和中序可以通過別的實現辦法避免tag實現。
  template <class T>
void pretraverse(struct node<T>*tree)
{
    if(tree == NULL) return;
    MyStack<struct node<T> *> treestack;
    treestack.init(20);
    while(tree != NULL|| treestack.gettop()!=0)
    {
        if(tree!=NULL)
        {
            treestack.push(tree);
            visitnode(tree);
            tree = tree->left;
        }
        else
        {
            tree = treestack.pop();
            tree = tree->right;

        }
    }

}