[백준] 5639번 이진 검색 트리 (= binary search tree) - 재우스 프로그래밍 (C 언어)

문제 링크 :www.acmicpc.net/problem/5639

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define DEBUG 1

typedef struct _Node {
    int value;
    bool visit;    //어차피 모든 노드를 탐색하기 때문에 필요없는 멤버 변수임.
    struct _Node *left;
    struct _Node *right;
} Node;

void makeTree(Node *, int);    //input 키값으로 트리 생성
Node *compareLR(Node *, int);    //input 키값을 넣을 위치를 찾기 위해 left, right 자식을 비교해보는 함수
void postOrder(Node *);    //생성된 tree를 후위탐색하는 함수
void initNode(Node *);    //node를 초기화해주는 함수

int main(void)
{
    int inVal = 0;    //입력 받은 트리의 키값
    Node *root = (Node *)malloc(sizeof(Node));
    initNode(root);

    scanf("%d", &(root->value));

    //EOF를 입력받을 때까지의 input 키값들을 트리 생성
    while (scanf("%d", &inVal) != EOF) {
        makeTree(root, inVal);
    }

    postOrder(root);    //생성된 tree를 후위 탐색

    free(root);
    return 0;
}

void makeTree(Node *node, int inVal)
{
    Node *next = (Node *)malloc(sizeof(Node));
    initNode(next);

    //적절한 위치의 tree에 추가될 때까지 반복
    while (node != NULL) {
        node = compareLR(node, inVal);
    }
    return;
}

Node *compareLR(Node *node, int inVal)
{
    //현재 노드보다 작으면 left 이동
    if (inVal < node->value) {
        //left 노드가 없으면 삽입
        if (node->left == NULL) {
            Node *temp = (Node *)malloc(sizeof(Node));
            initNode(temp);
            node->left = temp;
            node->left->value = inVal;

            return NULL;
        }
        //left 노드가 있으면 left 이동
        else {
            return node->left;
        }
    }
    //현재 노드보다 크면 right 이동
    else {
        //right 노드가 없으면 삽입
        if (node->right == NULL) {
            Node *temp = (Node *)malloc(sizeof(Node));
            initNode(temp);
            node->right = temp;
            node->right->value = inVal;

            return NULL;
        }
        //right 노드가 있으면 이동
        else {
            return node->right;
        }
    }
}

void postOrder(Node *node)
{
    //left right를 차례로 탐색하는데 전부 탐색해야 하므로 visit이 필요없음
    /*
        if (node == NULL)
            return;
        postOrder(node->left);
        postOrder(node->right);

    */
    //이렇게 짜도 상관이 없음.
    if (node->left != NULL && node->left->visit == false) {
        postOrder(node->left);
    }
    if (node->right != NULL && node->right->visit == false) {
        postOrder(node->right);
    }

    printf("%d\n", node->value);
    node->visit = true;

    return;
}

void initNode(Node *node)
{
    node->value = 0;
    node->visit = false;
    Node *left = NULL;
    Node *right = NULL;
    return;
}