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