UVa122 Trees on the level
2428 단어 두 갈래 나무
생각: BFS.사실 이 문제를 푸는 것은 수조를 시험적으로 이용하여 동적 트리 구조를 저장하기 위해서이다.
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <cstdlib>
#include <string>
#include <memory.h>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <ctype.h>
#define INF 1000000010
#define ll long long
#define max3(a,b,c) max(a,max(b,c))
#define MAXN 1000
using namespace std;
char str[32];
int node[1024];
int l[1024];
int r[1024];
int last;
int cur;
bool ok;
void addnode (char* pos,int n){
for(int i=0;;i++){
if(pos[i]==')'){
if(node[cur]!=-1)ok=false;
node[cur]=n;
//cout<<n<<" "<<cur<<endl;
break;
}
if(pos[i]=='L'){
if(l[cur]==-1){
last++;
l[cur]=last;
cur=last;
}else{
cur=l[cur];
}
}
if(pos[i]=='R'){
if(r[cur]==-1){
last++;
r[cur]=last;
cur=last;
}else{
cur=r[cur];
}
}
}
}
int main(){
while(cin>>str){
if(strlen(str)==2)continue;
memset(l,-1,sizeof(l));
memset(r,-1,sizeof(r));
memset(node,-1,sizeof(node));
last=0;
cur=0;
ok=true;
int k=strchr(str,',')-str;
int t=0;
for(int i=1;i<k;i++){
t*=10;
t+=str[i]-'0';
}
addnode(strchr(str,',')+1,t);
while(true){
cin>>str;
if(strlen(str)==2)break;
cur=0;
int k=strchr(str,',')-str;
int t=0;
for(int i=1;i<k;i++){
t*=10;
t+=str[i]-'0';
}
addnode(strchr(str,',')+1,t);
}
vector<int> ans;
queue<int> que;
que.push(0);
while(!que.empty()){
int cur=que.front(); que.pop();
ans.push_back(node[cur]);
if(node[cur]==-1)ok=false;
if(l[cur]!=-1){
que.push(l[cur]);
}
if(r[cur]!=-1){
que.push(r[cur]);
}
}
if(ok){
int siz=ans.size();
for(int i=0;i<siz;i++){
printf("%d",ans[i]);
if(i!=siz-1)printf(" ");
}
cout<<endl;
}else{
cout<<"not complete"<<endl;
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
java 데이터 구조 2차원 트리의 실현 코드일.두 갈래 트리 인터페이스 2 노드 클래스 3. 두 갈래 나무 구현 이 글을 통해 여러분께 도움이 되었으면 좋겠습니다. 본 사이트에 대한 지지에 감사드립니다!...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.