二叉樹的幾種遞歸和非遞歸式遍歷：
#include <fstream>
#include <iostream>
using namespace std;
/*
後序遍歷的非遞歸實現是三種遍歷方式中最難的一種。因為在後序遍歷中，要保證左孩子和右孩子都已被訪問並且左孩子在右孩子
前訪問才能訪問根結點，這就為流程的控制帶來了難題。下面介紹兩種思路。
第一種思路：對於任一結點P，將其入棧，然後沿其左子樹一直往下搜索，直到搜索到沒有左孩子的結點，此時該結點出現在棧頂，
但是此時不能將其出棧並訪問，因此其右孩子還為被訪問。所以接下來按照相同的規則對其右子樹進行相同的處理，當訪問完其右孩子
時，該結點又出現在棧頂，此時可以將其出棧並訪問。這樣就保證了正確的訪問順序。可以看出，在這個過程中，每個結點都兩次出現
在棧頂，只有在第二次出現在棧頂時，才能訪問它。因此需要多設置一個變量標識該結點是否是第一次出現在棧頂。
第二種思路：要保證根結點在左孩子和右孩子訪問之後才能訪問，因此對於任一結點P，先將其入棧。如果P不存在左孩子和右孩子，
則可以直接訪問它；或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被訪問過了，則同樣可以直接訪問該結點。若非上述兩種
情況，則將P的右孩子和左孩子依次入棧，這樣就保證了每次取棧頂元素的時候，左孩子在右孩子前面被訪問，左孩子和右孩子都在根結
點前面被訪問。
*/
#define queue_len 100
struct node
{
char c;
struct node *lch,*rch;
bool flag;
node():flag(0){}
void get_c()
{
printf("%c",c);
}
};
node* set_tree();//建樹
void pre_order(node* tree);//先序遍歷
void in_order(node* tree);//中序遍歷
void post_order(node* tree);//後序遍歷
void level_order(node* tree);//層次遍歷
void nr_pre_order(node* tree);//非遞歸先序遍歷
void nr_in_order(node* tree);//非遞歸中序遍歷
void nr_post_order_1(node* tree);//非遞歸後序遍歷
void nr_post_order_2(node* tree);//非遞歸後序遍歷
int main()
{
//freopen("D:\\input.in","r",stdin);
//freopen("D:\\output.out","w",stdout);
node* tree=set_tree();
printf("先序遍歷：");
pre_order(tree);
puts("");
printf("中序遍歷：");
in_order(tree);
puts("");
printf("後序遍歷：");
post_order(tree);
puts("");
printf("層次遍歷：");
level_order(tree);
puts("");
printf("先序遍歷：");
nr_pre_order(tree);
puts("");
printf("中序遍歷：");
nr_in_order(tree);
puts("");
printf("後序遍歷：");
nr_post_order_1(tree);
puts("");
printf("後序遍歷：");
nr_post_order_2(tree);
puts("");
return 0;
}
node* set_tree()
{
node* p,*s;
node* gen=new node;
gen->c='A';
gen->lch=new node;
p=gen->lch;
p->c='B';
p->rch=NULL;
p->lch=new node;
p=p->lch;
p->c='D';
p->lch=NULL;
p->rch=new node;
p=p->rch;
p->c='G';
p->lch=NULL;
p->rch=NULL;
gen->rch=new node;
p=gen->rch;
p->c='C';
p->lch=new node;
s=p->lch;
s->c='E';
s->lch=NULL;
s->rch=NULL;
p->rch=new node;
s=p->rch;
s->c='F';
s->lch=NULL;
s->rch=NULL;
return gen;
}
void pre_order(node* tree)
{
if(tree!=NULL)
{
tree->get_c();
pre_order(tree->lch);
pre_order(tree->rch);
}
}
void in_order(node* tree)
{
if(tree!=NULL)
{
in_order(tree->lch);
tree->get_c();
in_order(tree->rch);
}
}
void post_order(node* tree)
{
if(tree!=NULL)
{
post_order(tree->lch);
post_order(tree->rch);
tree->get_c();
}
}
void level_order(node* tree)
{
node* queue_1[queue_len];
int front,rear;
if(tree==NULL) return;
front=-1;
rear=0;
queue_1[rear]=tree;
while(front!=rear)
{
front++;
queue_1[front]->get_c();
if(queue_1[front]->lch!=NULL)
{
rear++;
queue_1[rear]=queue_1[front]->lch;
}
if(queue_1[front]->rch!=NULL)
{
rear++;
queue_1[rear]=queue_1[front]->rch;
}
}
}
void nr_pre_order(node* tree)
{
node* stack_1[queue_len];
int top=-1;
if(tree==NULL) return;
node* p=tree;
while(p!=NULL||top!=-1)
{
while(p!=NULL)
{
p->get_c();
stack_1[++top]=p;
p=p->lch;
}
if(top==-1) return;
p=stack_1[top--]->rch;
}
}
void nr_in_order(node* tree)
{
node* stack_1[queue_len];
int top=-1;
if(tree==NULL) return;
node* p=tree;
while(p!=NULL||top!=-1)
{
while(p!=NULL)
{
stack_1[++top]=p;
p=p->lch;
}
if(top==-1) return;
stack_1[top]->get_c();
p=stack_1[top--]->rch;
}
}
void nr_post_order_1(node* tree)
{
node* stack_1[queue_len];
int top=-1;
if(tree==NULL) return;
node* p=tree;
while(p!=NULL||top!=-1)
{
while(p!=NULL)
{
stack_1[++top]=p;
p=p->lch;
}
if(top==-1) return;
p=stack_1[top];
if(p->flag==0) {p->flag=1;p=p->rch;}
else { p->get_c(),top--;p=NULL;}
}
}
void nr_post_order_2(node* tree)
{
node* stack_1[queue_len];
int top=0;
if(tree==NULL) return;
node* p=tree;
while(top!=-1)
{
p=stack_1[top];
if((p->lch==NULL||p->lch->flag==0)&&(p->rch==NULL||p->rch->flag==0))
{
p->get_c();
p->flag=0;
top--;
}
else
{
if(p->rch!=NULL)
{
stack_1[++top]=p->rch;
}
if(p->lch!=NULL)
{
stack_1[++top]=p->lch;
}
}
}
}
