1 #include <fstream>  2 #include <iostream>  3   4 using namespace std;  5   6 /*  7     后序遍历的非递归实现是三种遍历方式中最难的一种。因为在后序遍历中，要保证左孩子和右孩子都已被访问并且左孩子在右孩子  8 前访问才能访问根结点，这就为流程的控制带来了难题。下面介绍两种思路。  9     第一种思路：对于任一结点P，将其入栈，然后沿其左子树一直往下搜索，直到搜索到没有左孩子的结点，此时该结点出现在栈顶， 10 但是此时不能将其出栈并访问，因此其右孩子还为被访问。所以接下来按照相同的规则对其右子树进行相同的处理，当访问完其右孩子 11 时，该结点又出现在栈顶，此时可以将其出栈并访问。这样就保证了正确的访问顺序。可以看出，在这个过程中，每个结点都两次出现 12 在栈顶，只有在第二次出现在栈顶时，才能访问它。因此需要多设置一个变量标识该结点是否是第一次出现在栈顶。 13     第二种思路：要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子， 14 则可以直接访问它；或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。若非上述两种 15 情况，则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结 16 点前面被访问。 17 */ 18  19 #define queue_len 100 20  21 struct node 22 { 23     char c; 24     struct node *lch,*rch; 25     bool flag; 26     node():flag(0){} 27     void get_c() 28     { 29         printf("%c",c); 30     } 31 }; 32  33 node* set_tree();//建树 34 void pre_order(node* tree);//先序遍历 35 void in_order(node* tree);//中序遍历 36 void post_order(node* tree);//后序遍历 37 void level_order(node* tree);//层次遍历 38 void nr_pre_order(node* tree);//非递归先序遍历 39 void nr_in_order(node* tree);//非递归中序遍历 40 void nr_post_order_1(node* tree);//非递归后序遍历 41 void nr_post_order_2(node* tree);//非递归后序遍历 42  43 int main() 44 { 45     //freopen("D:\\input.in","r",stdin); 46     //freopen("D:\\output.out","w",stdout); 47     node* tree=set_tree(); 48     printf("先序遍历："); 49     pre_order(tree); 50     puts(""); 51     printf("中序遍历："); 52     in_order(tree); 53     puts(""); 54     printf("后序遍历："); 55     post_order(tree); 56     puts(""); 57     printf("层次遍历："); 58     level_order(tree); 59     puts(""); 60     printf("先序遍历："); 61     nr_pre_order(tree); 62     puts(""); 63     printf("中序遍历："); 64     nr_in_order(tree); 65     puts(""); 66     printf("后序遍历："); 67     nr_post_order_1(tree); 68     puts(""); 69     printf("后序遍历："); 70     nr_post_order_2(tree); 71     puts(""); 72     return 0; 73 } 74 node* set_tree() 75 { 76     node* p,*s; 77     node* gen=new node; 78     gen->c=‘A‘; 79  80     gen->lch=new node; 81     p=gen->lch; 82     p->c=‘B‘; 83     p->rch=NULL; 84     p->lch=new node; 85     p=p->lch; 86     p->c=‘D‘; 87     p->lch=NULL; 88     p->rch=new node; 89     p=p->rch; 90     p->c=‘G‘; 91     p->lch=NULL; 92     p->rch=NULL; 93  94     gen->rch=new node; 95     p=gen->rch; 96     p->c=‘C‘; 97     p->lch=new node; 98     s=p->lch; 99     s->c=‘E‘;100     s->lch=NULL;101     s->rch=NULL;102     p->rch=new node;103     s=p->rch;104     s->c=‘F‘;105     s->lch=NULL;106     s->rch=NULL;107 108     return gen;109 }110 void pre_order(node* tree)111 {112     if(tree!=NULL)113     {114         tree->get_c();115         pre_order(tree->lch);116         pre_order(tree->rch);117     }118 }119 void in_order(node* tree)120 {121     if(tree!=NULL)122     {123         in_order(tree->lch);124         tree->get_c();125         in_order(tree->rch);126     }127 }128 void post_order(node* tree)129 {130     if(tree!=NULL)131     {132         post_order(tree->lch);133         post_order(tree->rch);134         tree->get_c();135     }136 }137 void level_order(node* tree)138 {139     node* queue_1[queue_len];140     int front,rear;141 142     if(tree==NULL)  return;143     front=-1;144     rear=0;145     queue_1[rear]=tree;146     while(front!=rear)147     {148         front++;149         queue_1[front]->get_c();150 151         if(queue_1[front]->lch!=NULL)152         {153             rear++;154             queue_1[rear]=queue_1[front]->lch;155         }156         if(queue_1[front]->rch!=NULL)157         {158             rear++;159             queue_1[rear]=queue_1[front]->rch;160         }161     }162 }163 void nr_pre_order(node* tree)164 {165     node* stack_1[queue_len];166     int top=-1;167 168     if(tree==NULL)  return;169     node* p=tree;170     while(p!=NULL||top!=-1)171     {172         while(p!=NULL)173         {174             p->get_c();175             stack_1[++top]=p;176             p=p->lch;177         }178         if(top==-1) return;179         p=stack_1[top--]->rch;180     }181 }182 void nr_in_order(node* tree)183 {184     node* stack_1[queue_len];185     int top=-1;186 187     if(tree==NULL)  return;188     node* p=tree;189     while(p!=NULL||top!=-1)190     {191         while(p!=NULL)192         {193             stack_1[++top]=p;194             p=p->lch;195         }196         if(top==-1) return;197         stack_1[top]->get_c();198         p=stack_1[top--]->rch;199     }200 }201 void nr_post_order_1(node* tree)202 {203     node* stack_1[queue_len];204     int top=-1;205 206     if(tree==NULL)  return;207     node* p=tree;208     while(p!=NULL||top!=-1)209     {210         while(p!=NULL)211         {212             stack_1[++top]=p;213             p=p->lch;214         }215         if(top==-1) return;216         p=stack_1[top];217         if(p->flag==0)  {p->flag=1;p=p->rch;}218         else   { p->get_c(),top--;p=NULL;}219     }220 }221 void nr_post_order_2(node* tree)222 {223     node* stack_1[queue_len];224     int top=0;225 226     if(tree==NULL)  return;227     node* p=tree;228     while(top!=-1)229     {230         p=stack_1[top];231         if((p->lch==NULL||p->lch->flag==0)&&(p->rch==NULL||p->rch->flag==0))232         {233             p->get_c();234             p->flag=0;235             top--;236         }237         else238         {239             if(p->rch!=NULL)240             {241                 stack_1[++top]=p->rch;242             }243             if(p->lch!=NULL)244             {245                 stack_1[++top]=p->lch;246             }247         }248     }249 }