二叉树的后续遍历算法实现

 1 // 递归算法
 2 template <class T>
 3 void postOrder(void (*visit)(BinTreeNode<T>* t), BinTreeNode<T>* root)
 4 {
 5     if (root != NULL) {
 6         postOrder(visit, root->leftChild);
 7         postOrder(visit, root->rightChild);
 8         visit(root);
 9     }
10 }

 1 /*
 2 非递归算法1.
 3 
 4     非递归算法，使用节点的右指针来做判别标志该节点是否是第一次访问，从根节点开始压入所有最左边节点进入堆栈，因为被压入堆栈的过程决定了，当前节点的左子结点已经被访问过了，所以只需判断右子节点。如果右子节点为空可以认为已经访问过了，如果非空，则修改指向右子节点的指针为空，作为已经访问过的标志。
 5 
 6 */
 7 template <class T>
 8 void postOrder(void(*visit)(BinTreeNode<T>* t), stack<BinTreeNode<T>*> s)
 9 {
10     BinTreeNode<T>* p = root;
11     s.push(NULL);
12     bool flag = true;
13     do {
14         while (p != NULL) {
15             s.push(p);
16             p = p->leftChild;
17         }
18         while (flag) {
19             if (! s.isEmpty()) {
20                 s.pop(p);
21                 if (p->rightChild == NULL) visit(p);
22                 else {  // 右子节点非空，且未访问过
23                     flag = false;
24                         s.push(p); // 右子节点压回堆栈
25                     BinTreeNode<T>* tmp = p->rightChild;
26                     p->rightChild = NULL;
27                         p = tmp;
28                 }
29             }
30         }
31     } while (! s.isEmpty());
32 }

 1 /*
 2 非递归算法2
 3 
 4 要保证根节点在左孩子和右孩子都访问之后才能访问，因此对任一节点P，先将其入栈，如果P没有子女，则可以直接访问它，如果有子女，且其左右孩子都已经访问过了，也可以访问P节点。否则，需要将P的右孩子和左孩子先后入栈，这样保证出栈顺序是先左孩子后右孩子。
 5 
 6 acknowledgement: http://www.cnblogs.com/dolphin0520/archive/2011/08/25/2153720.html
 7 */
 8 
 9 
10 
11 template <class T>
12 void postOrder(void(*visit)(BinTreeNode<T>* t), stack<BinTreeNode<T>*> s)
13 {
14     BinTreeNode<T>* cur = NULL;
15     BinTreeNode<T>* pre = NULL;
16     s.push(root);
17     while (! s.isEmpty()) {
18         cur = s.getTop();
19         if ((cur->leftChild == NULL && cur->rightChild == NULL) || (pre != NULL && (pre = cur->leftChild || pre = cur->rightChild))) {
20             s.pop(cur);
21             visit(cur);
22             pre = cur;
23         } else {
24             if (cur->rightChild != NULL) s.push(cur->rightChild);
25             if (cur->leftChild != NULL) s.push(cur->leftChild);
26         }
27     }
28 }

 1 /*
 2 非递归算法3
 3 构建一个新的struct，加入一个变量visit标示该节点是否被访问过
 4 */
 5 
 6 template <class T>
 7 struct newNode {
 8     BinTreeNode<T>* ptr;
 9     int visit;
10     newNode(BinTreeNode<T>* p) : ptr(p), visit(0) {}
11 }
12 
13 template <class T>
14 void postOrder(void (visit*)(BinTreeNode<T>* t), stack<newNode<T>*> s) 
15 {
16     BinTreeNode<T>* p = root;
17     newNode* np = NULL;
18     do {
19         while (p != NULL) {
20             np = newNode(p);
21             s.push(np);
22             p = p->leftChild;
23         }
24         bool flag = true;
25         while (flag) {
26             s.pop(np);
27             if (np->ptr->rightChild == NULL || np->visit == 1) {
28                 visit(np->ptr);
29             } else {
30                 s.push(np);
31                 flag = false;
32                 np->visit = 1;
33                 p = np->ptr->rightChild;
34             }
35         }
36     } while (! s.isEmpty());
37 }