本文共 1520 字,大约阅读时间需要 5 分钟。
Alternative Solution:
An alternative solution is to use two stacks. Try to work it out on a piece of paper. I think it is quite magical and beautiful. You will think that it works magically, but in fact it is doing a reversed pre-order traversal. That is, the order of traversal is a node, then its right child followed by its left child. This yields post-order traversal in reversed order. Using a second stack, we could reverse it back to the correct order.Here is how it works:
void PostOreder_NoReccursive(Bitree *T){ stacks1, s2; Bitree *curr; //指向当前要检查的节点 s1.push(T); while (!s1.empty()) { curr = s1.top(); s1.pop(); s2.push(curr); if (curr->pLeft) s1.push(curr->pLeft); if (curr->pRight) s1.push(curr->pRight); } while (!s2.empty()) { printf("%c ", s2.top()->iValue); s2.pop(); }}
转载地址:http://ebkqi.baihongyu.com/