給你寫了個(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;
}
}