#include<iostream>
using namespace std;
typedef class node
{
public :
int data;
node *left;
node *right;
}*BTNode,btnode;
typedef class qnodet
{
public:
BTNode t;
qnodet *next;
}*Qnode,qnode;
void init_LinkStack(Qnode &L);//初始化栈
bool Stack_empty(Qnode &L);//判断栈是否为空
void LinkStack_insert(Qnode &L,BTNode p);//插入
BTNode LinkStack_pop(Qnode &L);//栈弹出
void CreatBTNode(BTNode &L,char *str);//树的创建
void printlist(BTNode );
void mid_printlist(BTNode L);//中序遍历
void pre_printlist(BTNode L);//前序遍历
void last_printlist(BTNode L);//后续遍历(先求逆后续)
void follow_up_printlist(BTNode L);//后续遍历
int main()
{
char str[50]="A(B(D(,G)),C(E,F))";
BTNode p=NULL;
CreatBTNode(p,str);
follow_up_printlist(p);
cout<<endl;
cout<<"前序遍历";
pre_printlist(p);
cout<<"中序遍历";
mid_printlist(p);
cout<<"后续遍历";
last_printlist(p);
return 0;
}
void init_LinkStack(Qnode &L)
{
L=new qnode;
L->next=NULL;
}
bool Stack_empty(Qnode &L)
{
if(L->next==NULL)
{
return true;
}
else
{
return false;
}
}
void LinkStack_insert(Qnode &L,BTNode p)
{
Qnode s=new qnode;
s->t=p;
s->next=L->next;
L->next=s;
}
BTNode LinkStack_pop(Qnode &L)
{
Qnode p=L->next;
if(!Stack_empty(L))
{
L->next=p->next;
p->next=NULL;
return p->t;
}
else
{
return NULL;
}
}
void CreatBTNode(BTNode &L,char *str)
{
Qnode temp_stack;
init_LinkStack(temp_stack);
BTNode p;
int k,i=0;
while(str[i]!='\0')
{
switch(str[i])
{
case '(':
LinkStack_insert(temp_stack,p);
k=1;
break;
case ')':
LinkStack_pop(temp_stack);
break;
case ',':
k=2;
break;
default:
p=new btnode;
p->data=str[i];
p->left=NULL;
p->right=NULL;
if(L==NULL)
{
L=p;
}
else
{
switch(k)
{
case 1:
temp_stack->next->t->left=p;
break;
case 2:
temp_stack->next->t->right=p;
break;
}
}
}
i++;
}
}
void printlist(BTNode L)
{
if(L!=NULL)
{
cout<<char(L->data)<<endl;
printlist(L->left);
printlist(L->right);
}
}
void mid_printlist(BTNode L)//中序遍历
{
BTNode p=L;
Qnode Stack;
init_LinkStack(Stack);
while(p!=NULL||!Stack_empty(Stack))
{
while(p!=NULL)
{
LinkStack_insert(Stack,p);
p=p->left;
}
if(!Stack_empty(Stack))
{
p=LinkStack_pop(Stack);
cout<<char(p->data)<<" ";
p=p->right;
}
}
cout<<endl;
}
void pre_printlist(BTNode L)//前序遍历
{
BTNode p=L;
Qnode Stack;
init_LinkStack(Stack);
while(p!=NULL||!Stack_empty(Stack))
{
while(p!=NULL)
{
LinkStack_insert(Stack,p);
cout<<char(p->data)<<" ";
p=p->left;
}
if(!Stack_empty(Stack))
{
p=LinkStack_pop(Stack);
p=p->right;
}
}
cout<<endl;
}
void last_printlist(BTNode L)//后续遍历(先求逆后续)
{
BTNode p=L;
Qnode Stack;
Qnode temp_Stack;
init_LinkStack(Stack);
init_LinkStack(temp_Stack);
while(p!=NULL||!Stack_empty(Stack))
{
while(p!=NULL)
{
LinkStack_insert(Stack,p);
LinkStack_insert(temp_Stack,p);
p=p->right;
}
if(!Stack_empty(Stack))
{
p=LinkStack_pop(Stack);
p=p->left;
}
}
Qnode q=temp_Stack->next;
while(q!=NULL)
{
cout<<char(q->t->data)<<" ";
q=q->next;
}
cout<<endl;
}
void follow_up_printlist(BTNode L)//后续遍历
{
BTNode p=L;
Qnode Stack;
init_LinkStack(Stack);
/*LinkStack_insert(Stack,p);
p=p->left*/ //如果向先入栈，一定要让p=p->left 否则实际入栈会有多余的
BTNode flag=NULL;
while(!Stack_empty(Stack)||p!=NULL)
{
while(p!=NULL)
{
LinkStack_insert(Stack,p);
p=p->left;
}
if(!Stack_empty(Stack))
{
p=LinkStack_pop(Stack);
if(p->right==NULL||p->right==flag)
{
cout<<char(p->data)<<" ";
flag=p;
p=NULL;
}
else
{
LinkStack_insert(Stack,p);
p=p->right;
}
}
}
}
