后序的递归算法。
template <class T>
void recposttraverse(struct node<T>* Tree)
{
if(Tree == NULL) return;
recposttraverse(Tree->left);
recposttraverse(Tree->right);
visitnode(Tree);
}
后序的非递归算法要加入tag的实现。
template <class T>
void posttraverse(struct node<T>*tree)
{
if(tree == NULL) return;
MyStack<struct node<T> *> treestack;
treestack.init(20);
treestack.push(tree);
struct node<T>* Item;
while(treestack.gettop()!=0)
{
Item = treestack.pop();
if(Item&&Item->flag)//true is tree
{
Item->flag = false;
treestack.push(Item);
if(Item->right)
treestack.push(Item->right);
if(Item->left)
treestack.push(Item->left);
}
else
{
visitnode(Item);
}
}
}