二叉树非递归后序遍历

其他遍历见：http://www.cnblogs.com/jiu0821/p/4120017.html

算法：

1.指针指向当前树（子树）根节点
2.指针移动到左孩子，直到左孩子为空
3.指针移动到右孩子，直到右孩子为空
4.访问当前节点
5.指针移动到双亲节点，如果双亲为空，则结束；否则：
    （1）如果从左指针回退回来，如果右孩子不空，则指针移动到右孩子，转到第1步继续；否则转第4步继续；
    （2）如果从右指针回退回来，则转第4步继续；

代码：

 1 #include <fstream>
 2 #include <iostream>
 3 #include <cstdio>
 4 
 5 using namespace std;
 6 
 7 struct node
 8 {
 9     char c;
10     struct node *lch,*rch,*parent;
11     void get_c()
12     {
13         putchar(c);
14     }
15 };
16 
17 node* set_tree();
18 void post2order(node* tree);
19 
20 int main(){
21     //freopen("E:\input.in","r",stdin);
22     //freopen("E:\output.out","w",stdout);
23     node* tree=set_tree();
24     printf("后序遍历：");
25     post2order(tree);
26     puts("");
27     return 0;
28 }
29 node* set_tree()
30 {
31     node* p,*s;
32     node* gen=new node;
33     gen->c='A';
34     gen->parent=NULL;
35 
36     gen->lch=new node;
37     p=gen->lch;
38     p->parent=gen;
39     p->c='B';
40     p->rch=NULL;
41     p->lch=new node;
42     s=p;
43     p=p->lch;
44     p->parent=s;
45     p->c='D';
46     p->lch=NULL;
47     p->rch=new node;
48     s=p;
49     p=p->rch;
50     p->parent=s;
51     p->c='G';
52     p->lch=NULL;
53     p->rch=NULL;
54 
55     gen->rch=new node;
56     p=gen->rch;
57     p->parent=gen;
58     p->c='C';
59     p->lch=new node;
60     s=p->lch;
61     s->parent=p;
62     s->c='E';
63     s->lch=NULL;
64     s->rch=NULL;
65     p->rch=new node;
66     s=p->rch;
67     s->parent=p;
68     s->c='F';
69     s->lch=NULL;
70     s->rch=NULL;
71 
72     return gen;
73 }
74 void post2order(node *tree){
75     node* p,*s;
76     p=tree;
77     t1:
78     while(p->lch!=NULL) p=p->lch;
79     while(p->rch!=NULL) p=p->rch;
80     t2:p->get_c();
81     if(p->parent==NULL) return;
82     else{
83         s=p;
84         p=p->parent;
85         if(s==p->lch&&p->rch!=NULL){
86             p=p->rch;
87             goto t1;
88         }else
89             goto t2;
90     }
91 }