[백준]_1991번 : 트리 순회(C언어)

1991번: 트리 순회

입력으로 노드들이 부모, 왼쪽 자식, 오른쪽 자식 순서로 주어지고 이렇게 완성된 트리에서 전위 순회, 중위 순회, 후위 순회를 해서 노드에 저장된 값들을 순회별로 출력하면 되는 문제이다.

 

전략

먼저 입력 방식을 정의해 보자. 부모 노드는 반드시 입력되고 존재하지 않는 자식 노드는 '.'으로 대체된다. 즉 일단 크기가 6인(최대 입력이 5개까지인데 크기가 6인 이유는 배열의 마지막에 널 문자('\0')를 저장해야 되기 때문) 배열로 문자열을 받은 다음에 arr [0], arr [2], arr [4]만 뽑아서 사용하면 된다.

 

이제 입력을 받은 순서대로 트리를 완성시켜 주어야 한다. 즉 cur(부모 노드arr[0], 코드에서도 cur이라고 표현하였다) 노드가 기존의 생성된 트리에 존재하는지 안 하는지에 따라 우리의 행동이 달라질 것이다. 다행히도 A가 항상 루트 노드이기 때문에 A 이후에 입력되는 부모 노드들(arr [0]에 위치한 알파벳들)은 반드시 어떤 부모의 자식이다. 아래는 find 함수의 개요이다.

1. cur이 트리에 이미 존재하는 노드다 >>
   노드를 재귀적으로 탐색해서 찾고자 하는 노드를 찾고 그 노드를 반환한다.
2. cur이 트리에 존재하지 않는 노드이다 >>
   이 경우에 해당하는 경우는 단 한번 뿐이다. 바로 첫 번째 입력으로 A ? ? 가 들어올 때이다. 이때는 NULL을 반환하게 된다.

노드를 찾게되면 이제 새로운 노드를 만들어서 data를 입력해 주고 arr [2], arr [4]가 '.'이냐 아니냐에 따라 새로운 노드를 자식에게 할당해 줄지 정하면 된다.

 

코드 >>

#include "stdio.h"
#include "stdlib.h"

typedef struct Node { // 이진 트리의 노드 구조체
    char data;
    struct Node *left;
    struct Node *right;
} Node;

Node *newnode(char data) { // 새로운 노드를 만들고 반환해주는 함수
    Node *new = (Node *) malloc(sizeof(Node));
    new->data = data;
    new->right = new->left = NULL;
    return new;
}

Node *find(Node *cur, char data) { // data값을 갖고 있는 노드를 재귀적으로 찾는 함수
    if (cur != NULL) {
        if (cur->data == data) // data값이 일치하는 노드를 발견한 경우
            return cur;
        Node *tmp = find(cur->left, data);
        if (tmp != NULL)
            return tmp; // 왼쪽 서브 트리에서 발견했으면 tmp의 결과를 반환
        return find(cur->right, data); // 왼쪽 서브트리에서 발견하지 못했으면 오른쪽 서브 트리에서의 탐색 결과를 반환
    }
    return NULL;
}

void insert_node(Node *target, char arr[]) { // target 노드에 arr 정보 대입하기
    target->data = arr[0];
    if (arr[2] != '.') {
        target->left = newnode(arr[2]);
    }
    if (arr[4] != '.') {
        target->right = newnode(arr[4]);
    }
}

void pre(Node *h) { // 전위 순회
    if (h != NULL) {
        printf("%c", h->data);
        pre(h->left);
        pre(h->right);
    }
}

void in(Node *h) { // 중위 순회
    if (h != NULL) {
        in(h->left);
        printf("%c", h->data);
        in(h->right);
    }
}

void post(Node *h) { // 후위 순회
    if (h != NULL) {
        post(h->left);
        post(h->right);
        printf("%c", h->data);
    }
}

void delete_all(Node *h) { // 할당된 메모리 풀어주기
    if (h != NULL) {
        delete_all(h->left);
        delete_all(h->right);
        free(h);
    }
}

int main() {
    Node *H = newnode('A'); // 어차피 입력을 통해 초기화될 값이기 때문에 'A' 대신 아무거나 집어 넣어도 상관 없음
    int cnt;
    scanf("%d", &cnt);
    getchar();
    char arr[6];
    for (int i = 0; i < cnt; ++i) {
        fgets(arr, sizeof(arr), stdin);
        getchar();
        Node *tmp = find(H, arr[0]);
        if (tmp == NULL) {
            insert_node(H, arr);
        } else insert_node(tmp, arr);
    }
    pre(H);
    puts("");
    in(H);
    puts("");
    post(H);
    delete_all(H);
}