re: 第一章 UNIX系統(tǒng)概覽 PIGWORLD 2006-01-04 00:48
好的,其實(shí)我unix很菜的,正在學(xué)習(xí)中,以后多幫助啊~~
給你寫了個(gè)后序遍歷的非遞歸實(shí)現(xiàn),直接寫的,沒有驗(yàn)證過,估計(jì)沒有什么大的問題,看看吧
思想是:
先找到最左邊的葉子并把路上遇到的節(jié)點(diǎn)依次壓棧,然后彈出棧頂?shù)脑兀ㄔ撛貫樽钭筮叺娜~子),并判斷(1)它有沒有右節(jié)點(diǎn);(2)右節(jié)點(diǎn)是否被訪問過。如果(1)為有右節(jié)點(diǎn)同時(shí)(2)為沒有訪問過,則先壓入剛才彈出的元素,然后再壓入它的右子樹。否則,就訪問該節(jié)點(diǎn),并設(shè)置pre為改節(jié)點(diǎn)。
void BT_PostOrderNoRec(pTreeT root)
{
stack<pTreeT> s;
s.push(root);
while(root != 0 || !s.isEmpty()) {
//找到最左邊的葉子
while((root = root->left) != 0) {
s.push(root);
}
pTree pre; //記錄前一個(gè)訪問的節(jié)點(diǎn)
root = s.pop(); //彈出棧頂元素
//如果右子樹非空,并且右子樹未訪問過,
//則(在內(nèi)層while循環(huán)中)把右子樹壓棧
if(root->right != 0 && pre != root->right) {
//要把上一句中彈出的元素重新壓棧
s.push(root);
root = root->right;
s.push(root);
}
//否則
else {
彈出棧頂節(jié)點(diǎn),訪問它并設(shè)置pre為該節(jié)點(diǎn)
root = pre = s.pop();
visit(root);
//使root為0以免進(jìn)入內(nèi)層循環(huán)
root = 0;
}
}