遞歸算法和非遞歸算法本質(zhì)是一樣的。
遍歷時從根節(jié)點開始訪問，訪問左子樹，關鍵是把樹的訪問順序搞清楚。
當遍歷完以后又是根節(jié)點。
遞歸函數(shù)實際上就是棧的操作。
所謂的先根就是先visit完根節(jié)點，然后再遍歷左子樹，遍歷右子樹。
template <class T>
void recpretraverse(struct node<T>*&Tree)
{
if(Tree == NULL) return;
visitnode(Tree);
recpretraverse(Tree->left);
recpretraverse(Tree->right);
}
對應的非遞歸算法就是彈出項，看如果是樹，如果右子樹存在則壓入右子樹，左子樹存在則壓入左子樹，最后壓入節(jié)點（tag域變化）。
看如果是節(jié)點，則訪問節(jié)點。
可以看出需要一個tag域來表示彈出節(jié)點還是樹。但是前序和中序可以通過別的實現(xiàn)辦法避免tag實現(xiàn)。
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;
}
}
}