分類(lèi): 百科 常識(shí)詞典 編輯 : 常識(shí) 發(fā)布 : 08-25

閱讀 :441

二叉樹(shù)的非遞歸后續(xù)遍歷的方法有多少種？由于后續(xù)遍歷的特殊性，需要判斷是否是首次返回節(jié)點(diǎn)所以需要一個(gè)記錄節(jié)點(diǎn)訪(fǎng)問(wèn)次數(shù)的變量，后續(xù)遍歷的非遞歸遍歷方法都有哪些。1 個(gè)答案

答案 1：

補(bǔ)充一個(gè)不太常見(jiàn)的雙棧法，使用一個(gè)整數(shù)棧來(lái)記錄節(jié)點(diǎn)訪(fǎng)問(wèn)次數(shù)，與被記錄節(jié)點(diǎn)同時(shí)出棧同時(shí)進(jìn)棧：

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到底是什么品牌? 下一篇 【方向鍵 ( → )下一篇】

上一篇:所有問(wèn)題都夸大了，畢業(yè)了有謝師宴，除夕有年夜飯上千萬(wàn)，中秋有千金月餅。 上一篇 【方向鍵 ( ← )上一篇】