紫书上的原题 正好学数据结构拿出来做一下
不知道为什么bfs的队列一定要数组模拟……
还可以练习一下sscanf……
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<string.h>
#include<string>
#include<map>
#include<set>
#include<vector>
#include<queue>
#define M(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
queue<int>ans;
struct Binary_Tree //二叉树
{
int value;
Binary_Tree *lchild,*rchild;
Binary_Tree()
{
value=;
lchild=rchild=NULL;
}
};
bool add(Binary_Tree *&Root,char *s,int value){ //向二叉树中加入点
if(Root==NULL)
Root=new Binary_Tree();
if(*s=='\0')
{
if(Root->value!=)
{
return false;
}
Root->value=value;
return true;
}
if(*s=='L') //寻找路径
{
return add(Root->lchild,s+,value);
}
else if(*s=='R')
{
return add(Root->rchild,s+,value);
}
return false;
}
void Delete(Binary_Tree *Root) //删除二叉树
{
if(Root==NULL) return ;
Delete(Root->lchild);
Delete(Root->rchild);
delete Root;
}
bool bfs(Binary_Tree *Root) //层次遍历
{
Binary_Tree *q[]; //数组模拟队列
int front=;
int rear=;
q[]=Root;
while (front<rear)
{
Binary_Tree *temp=q[front++];
if(!temp->value) //没有值就返回false
{
return false;
}
ans.push(temp->value); //当前节点入ans队
if(temp->lchild) //左孩子入队
{
q[rear++]=temp->lchild;
}
if(temp->rchild) //右孩子入队
{
q[rear++]=temp->rchild;
}
}
return true;
}
int main(){
Binary_Tree *Root=NULL;
char s[];
bool no=false;
while(true)
{
no=false;
Delete(Root);
Root=NULL; //二叉树初始化
while(true)
{
if(scanf("%s",s)==EOF) //读入
{
return ;
}
if(strcmp(s,"()")==)
{
break;
}
int val;
char loc[];
strcpy(loc,"");
sscanf(&s[],"%d",&val);
char *start=strchr(s,',')+;
sscanf(start,"%[A-Z]",&loc);
if(!add(Root,loc,val))
{
no=true;
}
}
if(no)
{
puts("not complete");
}
else
{
if(!bfs(Root))
puts("not complete");
else
{
while(!ans.empty())
{
int ll=ans.front();
ans.pop();
printf("%d%c",ll,ans.empty()?'\n':' ');
}
}
}
}
return ;
}
/* (11,LL) (7,LLL) (8,R)
(5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()
(3,L) (4,R) () */