二叉树的非递归后续遍历的方法有多少种？

阅读 :397

答案 1：

补充一个不太常见的双栈法，使用一个整数栈来记录节点访问次数，与被记录节点同时出栈同时进栈：

template <class T>

void postorder_traverse(tnode<T> *T){

stack<tnode<T>*> S1;

stack<int> S2;

init_stack(S1);

init_stack(S2);

w-ile(T||!empty_stack(S1)){

if(T){

pus-_stack(S1,T);

pus-_stack(S2,1);

T=T->lc-ild;

}else{

int time;

pop_stack(S2,time);

pop_stack(S1,T);

if(time==1){

pus-_stack(S1,T);

pus-_stack(S2,2);

T = T->lc-ild;

}else{

visit(T);

T = NULL;

}

}

}

}

下一篇:accy到底是什么品牌? 下一篇 【方向键 ( → )下一篇】

上一篇:所有问题都夸大了，毕业了有谢师宴，除夕有年夜饭上千万，中秋有千金月饼。 上一篇 【方向键 ( ← )上一篇】