输入从根节点开始的路径，输出层次遍历的结果
样例输入
（3，L）
（2，R）
（）
输出：
1 3 2
指针实现
#include<cstdio>
#include<cstring>
#include<string.h>
#include<stdlib.h>
using namespace std;
const int maxn=100;
char s[maxn];
int fail=0;
typedef struct tnode
{
int have_val;
int u;
tnode *right,*left;
}node;
node *root;
int cnt,ans[maxn];
node *newnode()
{
node *r=(node *)malloc(sizeof(node));
r->have_val=0;
r->left=r->right=NULL;
}
void addnode(int u,char *s)
{
int len=strlen(s);
node *r=root;
for(int i=0;i<len-1;i++)
{
if(s[i]=='L')
{
if(r->left==NULL)
r->left=newnode();
r=r->left;
}
else if(s[i]=='R')
{
if(r->right==NULL)
r->right=newnode();
r=r->right;
}
}
if(r->have_val)
fail=1;
r->have_val=1;
r->u=u;
}
int bfs()
{
int rear=1;
int front=0;
node *q[maxn];
q[0]=root;
while(front<rear)
{
node *r;
r=q[front++];
if(r->have_val==0)
return 0;
ans[cnt++]=r->u;
if(r->left!=NULL)
q[rear++]=r->left;
if(r->right!=NULL)
q[rear++]=r->right;
}
return 1;
}
void remove(node *u)
{
if(u==NULL)
return ;
remove(u->left);
remove(u->right);
free(u);
}
int main()
{
fail=0;
remove(root);
root=newnode();
root->have_val=1;
root->u=1;
cnt=0;
while(scanf("%s",s)==1)
{
if(!strcmp(s,"()"))
break;
int v;
sscanf(&s[1],"%d",&v);
addnode(v,strchr(s,',')+1);
}
if(bfs())
{
for(int i=0;i<cnt;i++)
printf("%d ",ans[i]);
printf("
");
}
else printf("the tree is incorrect
");
return 0;
}
数组实现
#include<cstdio>
#include<cstring>
#include<string.h>
using namespace std;
const int maxn=100;
int fail=0;
int left[maxn],right[maxn],ans[maxn],pos[maxn],vis[maxn];
char s[maxn];
const int root=1;
int cnt;
void newtree(){cnt=1;left[root]=right[root]=0;}
int newnode(){int u=++cnt;left[u]=right[u]=0;return u;};
void addnode(int u,char *s)
{
int len=strlen(s);
int r=1;
for(int i=0;i<len-1;i++)
{
if(s[i]=='L')
{
if(left[r]==0)
left[r]=newnode();
r=left[r];
}
else if(s[i]=='R')
{
if(right[r]==0)
right[r]=newnode();
r=right[r];
}
}
if(vis[r])
fail=1;
pos[r]=u;
vis[r]=1;
}
int bfs()
{
int front=0,rear=1;
int r=1;
int q[maxn];
q[0]=1;
cnt=0;
while(front<rear)
{
r=q[front++];
if(!vis[r])
return 0;
ans[cnt++]=pos[r];
if(left[r])
q[rear++]=left[r];
if(right[r])
q[rear++]=right[r];
}
return 1;
}
int main()
{
memset(vis,0,sizeof(vis));
fail=0;
cnt=0;
pos[1]=1;
vis[1]=1;
newtree();
while(scanf("%s",s))
{
if(!strcmp(s,"()"))
break;
int v;
sscanf(&s[1],"%d",&v);
addnode(v,strchr(s,',')+1);
}
if(bfs())
{
for(int i=0;i<cnt;i++)
printf("%d ",ans[i]);
printf("
");
}
else printf("the tree is not correct");
return 0;
}