#include<iostream>
#include<malloc.h>
#include<queue>
#include<list>
using namespace std;
struct node
{
char c;
node *lchild,*rchild;
};
char pre[100],mid[100];
void build(node* &t,int start1,int end1,int start2,int end2)
{
int i=start2;
while(pre[start1]!=mid[i])
i=i+1;
t=(node*)malloc(sizeof(node));
t->c=pre[start1];
if(i==start2)
t->lchild=NULL;
else build(t->lchild,start1+1,start1+i-start2,start2,i-1);
if(i==end2)
t->rchild=NULL;
else build(t->rchild,start1+i-start2+1,end1,i+1,end2);
}
list<node*> que;
void visit(node *t)
{
que.push_back(t);
while(!que.empty())
{
node *temp=que.front();
cout<<temp->c;
if(temp->lchild!=NULL)
que.push_back(temp->lchild);
if(temp->rchild!=NULL)
que.push_back(temp->rchild);
que.pop_front();
}
printf("");
}
void last(node *t)
{
if(t==NULL)
return;
if(t->lchild!=NULL)
last(t->lchild);
if(t->rchild!=NULL)
last(t->rchild);
cout<<t->c;
}
int main()
{
node *tree;
int length;
while(1==1)
{
printf("\n\n输出先序遍历：\n");
cin>>pre;
printf("输出中序遍历：\n");
cin>>mid;
length=strlen(pre);
build(tree,0,length-1,0,length-1);
if(!que.empty())
que.clear();
printf("层次遍历结果：\n");
visit(tree);
}
return 0;
}
|
