알고리즘 입문 클래식 트리 시리즈 UVO

우선 예제 6.3.3 단계가 두루 훑어본다.
제목 설명:
두 갈래 나무를 입력하십시오. 당신의 임무는 위에서 아래로, 왼쪽에서 오른쪽으로 각 노드의 값을 출력하는 것입니다.각 노드는 루트 노드에서 해당 노드로 이동하는 순서에 따라 제공됩니다(L은 왼쪽, R은 오른쪽).입력에서 각 노드의 왼쪽 괄호 사이에는 공백이 없고 인접한 노드 사이에는 공백으로 구분됩니다.그림과 같이 각 트리의 입력은 한 쌍의 빈 괄호()로 끝납니다.
                                                                                      5
                                                                           4                     8
                                                                    11                   13            4
                                                               7        2                                     1
루트에서 어떤 잎 노드까지의 경로에 있는 결점이 다시 입력되지 않거나 한 번 이상 제시되면 -1을 출력해야 합니다.결점 개수는 256을 초과하지 않는다.
샘플 입력:
(11,LL)(7,LLL)(8,R)(5,)(4,L)(13,RL)(2,LLR)(1,RRR)(4,RR)()
(4,L)(4,R)()
샘플 출력:
5 4 8 11 13 4 7 2 1
-1
책에서 제시한 예제에서 입력한 문자열의 처리를 교묘하게 활용했다. 그러나 나는 이렇게 하면 이 프로그램이 틀렸다고 느꼈다. 이런 결과를 출력하지 못할 것이다. 대신의 지적을 구하고 프로그램의 이런 문장을 본다.

if(scanf("%s",s)!=1)
            return 0;

그의 이 말은 한 줄의 문자열을 입력하고 그렇지 않으면 0으로 되돌아가 종료한다는 뜻이다. 그러나 뒤에서 사용할 때 매번 읽는 것은 하나의 괄호 중의 일부분이라고 설명한다. 예를 들어 테스트 데이터의 "(11, LL)"이다. 그러나 이 말은 매번 괄호 속의 일부분만 읽는 것은 아니겠지.
괄호 안에 있는 부분만 읽는 함수를 구현하려면 다음과 같이 하십시오.
다음은 실행 결과를 되돌려 주지 않는 규칙입니다.

#include <iostream>
#include <cstdio>
#include <string.h>
#include <cstdlib>
using namespace std;
#define Max 300
struct Node
{
    int have_value;
    int date;
    struct Node *left;
    struct Node *right;
};

Node *root;
char s[Max];   // 
int failed;

Node* newnode()   // 
{
    Node* u=(Node *)malloc(sizeof(Node));
    if(u != NULL)
    {
        u->have_value=0;
        u->left = u->right= NULL;
    }
    return u;
}
void addnode(int x,char *s)
{
    Node *v=root;
    for(int i=0;i<strlen(s);i++)
    {
        if(s[i]=='L'){
            if(v->left==NULL) v->left = newnode();     // ！！ 、 、、
            v = v->left;
        }
        if(s[i]=='R'){
            if(v->right==NULL) v->right = newnode();
            v=v->right;
        }
    }
    if(v->have_value) failed=1;
    v->date = x;
    v->have_value = 1;
}
void remove_tree(Node *u)  // 
{
    if(u==NULL) return;
    remove_tree(u->left);
    remove_tree(u->right);
    free(u);
}

int read_input()
{
    failed=0;
    remove_tree(root);
    root=newnode();
    for(;;)
    {
        if(scanf("%s",s)!=1)
            return 0;
        if(!strcmp(s,"()"))
            break;
        int v;
        sscanf(&s[1],"%d",&v);
        addnode(v,strchr(s,',')+1);
    }
    return 1;
}

int n=0,ans[Max];
int Bfs()
{
    Node* q[Max];
    int count=0;
    int front=0,rear=1;
    q[0]=root;
    while(front<rear)
    {
        Node* u=q[count++];
        if(u->have_value==0) return 0;
        ans[n++]=u->date;
        if(u->left!=NULL) q[count++]=u->left;
        if(u->right!=NULL) q[count++]=u->right;
    }
    return 1;
}



int main()
{
    read_input();
    Bfs();
    if(failed==1)
        cout<<"-1"<<endl;
    else
    for(int i=0;i<n;++i)
        cout<<ans[i]<<" ";
    system("pause");
    return 0;
}
/*
(11,LL)(7,LLL)(8,R)(5,)(4,L)(13,RL)(2,LLR)(1,RRR)(4,RR)()
(4,L)(4,R)()
*/