UVA-122(Trees on the level)

Trees on the level
제목 링크:
https://vjudge.net/problem/UVA-122
제목:
입력 () 이 끝 날 때 까지 트 리 를 만 들 고 트 리 가 완전 한 지 판단 할 수 있 도록 (...) 트 리 를 만 들 수 있 습 니 다. 노드 가 할당 되 지 않 거나 할당 되 지 않 으 면 계층 별로 출력 트 리 를 옮 겨 다 닙 니 다. 그렇지 않 으 면 not complete 를 출력 합 니 다.
코드:
#include 
#include 
#include 
#include 
#include 
#include 
#include 
const int maxn=10010;
using namespace std;
typedef struct node
{
    int data;
    struct node *lchild;
    struct node *rchild;
};

bool judge(node *b)
{
    queue  q;
    while(!q.empty()) q.pop();
    q.push(b);
    while(!q.empty())
    {
        node *u = q.front();
        q.pop();
        if(u->data < 0) return false;
        if(u->lchild != NULL)q.push(u->lchild);
        if(u->rchild != NULL)q.push(u->rchild);
    }
    return true;
}
void LevelOrder(node *b)
{
    node *p;
    queue  q;
    while(!q.empty())q.pop();
    q.push(b);
    while(!q.empty())
    {
        p = q.front();
        q.pop();
        if(p->data == b->data) printf("%d",p->data);
        else printf(" %d",p->data);
        if(p->lchild!=NULL) q.push(p->lchild);
        if(p->rchild!=NULL) q.push(p->rchild);
    }
    printf("
"); } void Destroy(node *&b) { node *p; queue q; while(!q.empty())q.pop(); q.push(b); while(!q.empty()) { p = q.front(); q.pop(); if(p->lchild!=NULL) q.push(p->lchild); if(p->rchild!=NULL) q.push(p->rchild); free(p); } } int main() { // freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); node *root; root = (node *)malloc(sizeof(node)); root->lchild = NULL; root->rchild = NULL; root->data = -1; char s[maxn],number[maxn]; int i,flag=0; node *p,*b; while(scanf("%s",s)!=EOF) { // printf("%s
",s); if(strcmp(s,"()")!=0) { int j=0; for(i=1; ilchild==NULL) { b = (node *)malloc(sizeof(node)); p->lchild = b; b->data = -1; b->lchild = NULL; b->rchild = NULL; p=b; } else p = p->lchild; } else if(s[i]=='R') { if(p->rchild==NULL) { b = (node *)malloc(sizeof(node)); p->rchild = b; b->data = -1; b->lchild = NULL; b->rchild = NULL; p=b; } else p = p->rchild; } i++; } if(p->data<0) p->data = atoi(number); else flag=1; } else { if(judge(root)&&flag!=1) { LevelOrder(root); Destroy(root); root = (node *)malloc(sizeof(node)); root->lchild = NULL; root->rchild = NULL; root->data = -1; flag=0; } else { printf("not complete
"); Destroy(root); root = (node *)malloc(sizeof(node)); root->lchild = NULL; root->rchild = NULL; root->data = -1; flag=0; } } } return 0; } // not complete

좋은 웹페이지 즐겨찾기