Trees on the level

자서학습노트 제목 전송진 제목: 여러 조의 두 갈래 트리 데이터를 입력하십시오.각 그룹의 데이터는 "()"로 끝나서 반복 노드가 없는 연속적인 두 갈래 트리를 구성할 수 있는지 판단합니다. 1: 바늘 구현, 바늘 훑어보기

#include
#include
#include
#include
#include
using namespace std;
queue<int>w;
struct Node
{
     
	bool vis;Node *left,*right;int v;
	Node():vis(false),left(NULL),right(NULL){
     };
};
Node* root=NULL;
char s[300];bool fail;

void remove_tree(Node* u)
{
     
	if(u==NULL) return;
	remove_tree(u->left);
	remove_tree(u->right);
	delete u;
}

void addnode(int v,char* s)
{
     
	int n=strlen(s)-1;
	Node *u=root;
	for(int i=0;i<n;++i)
	{
     
		if(s[i]=='L')
		{
     
			if(u->left==NULL) u->left=new Node();
			u=u->left;
		}
		else if(s[i]=='R')
		{
     
			if(u->right==NULL) u->right=new Node();
			u=u->right;
		}
	}
	if(u->vis) fail=true;
	u->v=v;
	u->vis=true;
}
bool read()
{
     
	fail=false;
	remove_tree(root);
	root=new Node();
	int v;
	while(1)
	{
     
		if(scanf("%s",s)!=1) return false;
		if(s[0]=='('&&s[1]==')') break;
		sscanf(&s[1],"%d",&v);
		addnode(v,strchr(s,',')+1);
	}
	return true;
}



bool bfs(queue<int>& ans)
{
     
	queue<Node*>q;
	ans=queue<int>();
	q.push(root);
	while(!q.empty())
	{
     
		Node* u=q.front();q.pop();
		if(!u->vis) return false;
		ans.push(u->v);
		if(u->left!=NULL) q.push(u->left);
		if(u->right!=NULL) q.push(u->right);
	}
	return true;
}
int main()
{
     
	while(read())
	{
     
		
		if(fail) printf("not complete
");
		else
		{
     
			//cout<
			if(bfs(w))
			{
     
				while(w.size()!=1)
				{
     
					printf("%d ",w.front());
					w.pop();
				}
				printf("%d
",w.front());
				w.pop();
			}
			else printf("not complete
");
		}
		
	}
}

실현 2: 수조 실현, 수조 반복

#include
#include
#include
#include
#include
using namespace std;
queue<int>w;//  
const int root =1;
int left1[100000],right1[100000],cnt,vis[100000],v[100000];
char s[300];bool fail;

int newnode()
{
     
	++cnt;
	left1[cnt]=right1[cnt]=vis[cnt]=0;
	return cnt;
}

void addnode(int vi,char* s)
{
     
	int n=strlen(s)-1;
	int u=1;
	for(int i=0;i<n;++i)
	{
     
		if(s[i]=='L')
		{
     
			if(!left1[u]) left1[u]=newnode();
			u=left1[u];
		}
		else if(s[i]=='R')
		{
     
			if(!right1[u]) right1[u]=newnode();
			u=right1[u];
		}
	}
	if(vis[u]) fail=true;
	v[u]=vi;
	vis[u]=1;
}


bool read()
{
     
	fail=false;
	cnt=0;
	newnode();
	int v;
	while(1)
	{
     
		if(scanf("%s",s)!=1) return false;
		if(s[0]=='('&&s[1]==')') break;
		sscanf(&s[1],"%d",&v);
		addnode(v,strchr(s,',')+1);
	}
	return true;
}



bool bfs(queue<int>& ans)
{
     
	queue<int>q;
	q.push(1);
	while(!q.empty())
	{
     
		int u=q.front();q.pop();
		if(!vis[u]) return false;
		ans.push(v[u]);
		if(left1[u]) q.push(left1[u]);
		if(right1[u]) q.push(right1[u]);
	}
	return true;
}

int main()
{
     
	while(read())
	{
     
		
		if(fail) printf("not complete
");
		else
		{
     
			if(bfs(w))
			{
     
				while(w.size()!=1)
				{
     
					printf("%d ",w.front());
					w.pop();
				}
				printf("%d
",w.front());
				w.pop();
			}
			else printf("not complete
");
		}
		
	}
}

실현 3: 수조 실현, 바늘 훑어보기

#include
#include
#include
#include
#include
using namespace std;
queue<int>w;
struct Node
{
     
	bool vis;Node *left,*right;int v;
	Node():vis(false),left(NULL),right(NULL){
     };
}a[70000];Node* root=NULL;
char s[300];bool fail;
queue<Node*> freenodes;

void init() //  
{
     
	for(int i=0;i<70000;++i)
	freenodes.push(&a[i]);
}

Node* newnode()
{
     
	Node* u=freenodes.front();
	u->left=u->right=NULL;
	u->vis=false;
	freenodes.pop();
	return u;
}
void remove_tree(Node* u)
{
     
	if(u==NULL) return;
	remove_tree(u->left);
	remove_tree(u->right);
	freenodes.push(u);
}

void addnode(int v,char* s)
{
     
	int n=strlen(s)-1;
	Node *u=root;
	for(int i=0;i<n;++i)
	{
     
		if(s[i]=='L')
		{
     
			if(u->left==NULL) u->left=newnode();
			u=u->left;
		}
		else if(s[i]=='R')
		{
     
			if(u->right==NULL) u->right=newnode();
			u=u->right;
		}
	}
	if(u->vis) fail=true;
	u->v=v;
	u->vis=true;
}
bool read()
{
     
	fail=false;
	remove_tree(root);
	root=newnode();
	int v;
	while(1)
	{
     
		if(scanf("%s",s)!=1) return false;
		if(s[0]=='('&&s[1]==')') break;
		sscanf(&s[1],"%d",&v);
		addnode(v,strchr(s,',')+1);
	}
	return true;
}



bool bfs(queue<int>& ans)
{
     
	queue<Node*>q;
	ans=queue<int>();
	q.push(root);
	while(!q.empty())
	{
     
		Node* u=q.front();q.pop();
		if(!u->vis) return false;
		ans.push(u->v);
		if(u->left!=NULL) q.push(u->left);
		if(u->right!=NULL) q.push(u->right);
	}
	return true;
}
int main()
{
     
	init();
	while(read())
	{
     
		
		if(fail) printf("not complete
");
		else
		{
     
			if(bfs(w))
			{
     
				while(w.size()!=1)
				{
     
					printf("%d ",w.front());
					w.pop();
				}
				printf("%d
",w.front());
				w.pop();
			}
			else printf("not complete
");
		}
		
	}
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

요구사항 정의

요구사항 정의 작성 방법 개요 ・목적 표시되고 있는 텍스트를 가변으로 한다 · 과제 표시된 텍스트가 변경되지 않음 ・해결 표시되고 있는 텍스트가 가변이 된다 사양 · 표시 정의 각 편집 화면 ○○ 표시되고 있는 텍스...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

Trees on the level

좋은 웹페이지 즐겨찾기