[자료구조] Family tree 구현하기

컨닝 방지를 위해 과제 제출 기한이 모두 끝난 후에 공개 포스팅으로 전환할 생각이다. 

이 과제의 마감일은 (지연 제출 마감일까지 포함한 날짜이다) 5/21이다.

 

<문제>

 

실세계의 family tree를 구성하는 부모와 자식 관계를 입력받아 이를 binary tree에 저장하고 출력하는
프로그램을 아래와 같이 작성하시오.
(a) 프로그램 실행이 시작되면 명령어 prompt “>>” 를 출력하고 데이터가 입력되기를 기다린다.
(b) 입력 데이터의 형식은 xFy 또는 xMy 이고 enter 키를 눌러서 입력을 완료한다. 각각 x의 아버지는
y, x의 어머니는 y임을 의미한다. 사람의 이름 (즉, x, y 등)은 영어 소문자 1 char라고 가정한다. 동명
이인은 없다고 가정한다. 부모를 나타내는 F와 M은 대문자 1 char로 쓴다.
(c) 실세계의 부모 자식 관계는 수업시간에 공부한 교재의 linked representation을 사용하여 binary
tree로 표현한다. 노드구조는 <lchild, data, rchild>로 한다. 이때, lchild는 아버지 노드를 가리키는
link, rchild는 어머니 노드를 가리키는 link, data는 이름을 저장한다.
Note: 실세계의 아버지는 binary tree 표현에서는 왼쪽 자식노드에 저장되고, 어머니는 오른쪽 자식노
드에 저장된다. binary tree의 노드구조를 정의할 때, 필드명을 <father, name, mother>로 해도 된다.
(d) 입력된 데이터는 binary tree에 반영하여 binary tree를 확장해 나간다. 명령어 prompt “>>”에
$$$를 입력하면 프로그램을 종료한다.
(e) binary tree는 1개만 사용한다. 오류 또는 모순이 있거나 복수개의 binary tree를 동시에 필요로 하
는 데이터의 입력 수순은 없다고 가정한다.
(f) binary tree 내에서 노드의 탐색은 수업시간에 공부한 교재의 binary tree traversal 중
level-order traversal을 이용한다.
(g) 각 입력 데이터의 내용을 binary tree에 반영하여 저장한 후, 변경된 binary tree의 노드들을
level-order traversal로 출력한다.

 

문제는 다음과 같다.

 

<코드>

 

#define MAX_QUEUE_SIZE 1000
#include <stdio.h>
#include <stdlib.h>

typedef struct node* treePointer;

typedef struct node {
    char data;
    treePointer lchild, rchild;
} tree;

treePointer root = NULL;


int front = -1, rear = -1;
treePointer queue[MAX_QUEUE_SIZE];

void addq(treePointer ptr) {
    rear = rear + 1 % MAX_QUEUE_SIZE;
    if (front == rear) printf("This queue is full");
    queue[rear] = ptr;
}

treePointer deleteq() {
    if (front != rear) {
        front = (front + 1) % MAX_QUEUE_SIZE;
        return queue[front];
    }
    else {
        return NULL;
    }
}

treePointer isNodeExist(char one, char two) {
    treePointer temp = malloc(sizeof(tree));
    temp->data = one;
    temp->lchild = NULL, temp->rchild = NULL;
    treePointer ptr = root;
    front = 0, rear = 0;
    if (!ptr) {
        root = temp;
        return temp;
    }
    addq(ptr);
    for (;;) {
        ptr = deleteq();
        if (ptr) {
            if (ptr->data == one || ptr->data == two) {
                return ptr;
            }
            if (ptr->lchild) addq(ptr->lchild);
            if (ptr->rchild) addq(ptr->rchild);
        }
        else break;
    }
}


void insertTree(char* input) {
    int isRoot = 0;
    treePointer temp = isNodeExist(input[0], input[2]);
    if (temp == root) isRoot = 1;
    treePointer newNode = malloc(sizeof(tree));
    newNode->data = ' ';
    newNode->lchild = NULL; newNode->rchild = NULL;
    if (input[1] == 'M') {
        if (temp->data == input[0]) {
            newNode->data = input[2];
            newNode->rchild = temp->rchild;
            temp->rchild = newNode;
        }
        else {
            newNode->data = input[0];
            newNode->rchild = temp;
            if (isRoot) root = newNode;
        }

    }
    else if (input[1] == 'F') {
        if (temp->data == input[0]) {
            newNode->data = input[2];
            newNode->lchild = temp->lchild;
            temp->lchild = newNode;
        }
        else {
            newNode->data = input[0];
            newNode->lchild = temp;
            if (isRoot) root = newNode;
        }
    }
}

void levelOrder(treePointer ptr) {
    front = 0, rear = 0;
    if (!ptr) return;
    addq(ptr);
    for (;;) {
        ptr = deleteq();
        if (ptr) {
            printf("%c", ptr->data);
            if (ptr->lchild) addq(ptr->lchild);
            if (ptr->rchild) addq(ptr->rchild);
        }
        else break;
    }
}


int  main()
{
    char input[4];
    while (1) {
        printf(">> ");
        scanf_s("%s", input, (unsigned)_countof(input));
        if (input[0] == '$' && input[1] == '$' && input[2] == '$') break;
        else {
            insertTree(input);
            levelOrder(root);
            printf("\n");
        }
    }

    return 0;
}

 

<예제 결과>

 

이런 식으로 출력이 된다.

 

이 과제를 하면서 헤맸던 부분은 아이러니하게도 다른 부분도 아니고 malloc 할당 부분이었다. 

교재에 나와있는 것처럼 malloc(sizeof(treePointer))로 했는데 계속 오류가 떠서 미칠 지경이었다.

거짓말 안 하고 다른 코드 짜는 시간 보다 malloc 오류 고민하는 시간이 더 길었다.

malloc(sizeof(tree))로 고치니 아주 잘 돌아갔다. 도움 주신 ㄱㅈㅎ님께 감사를 표합니다.

안에 data와 lchild, rchild의 값이 들어가야 하기 때문에 tree로 초기화하는 것이 맞는 표현이다. 

 

두 번째로 신경쓴 부분은 위의 예시에서도 보이듯이 pFa였다. 

a가 root 노드인데 새로운 p노드가 root가 되어야 하기 때문에 어떻게 구현할 지 고민했었다. 

해결한 방법은 어차피 root 노드가 되려면 3번째의 값이 root여야 하기 때문에 if문으로 input[2]의 값이 tree에 존재할 경우 해당 값이 root이면 root에 새롭게 추가된 Node를 대입하는 식으로 해결하였다. 

 

나머지는 설명에 나온 그대로 적으면 된다. 

3시간 정도 걸렸는데, 1시간 반 동안은 오류 고민했으니 실질적인 코드 작성 시간은 1시간 반이었다. 

확실히 그림과 글을 적어 놓고 구현 사항을 고민한 다음 코드를 짜면 시간이 덜 오래 걸리는 것 같다. 

모두 그림을 그린 후에 코딩하자.