[자료구조] ep7+) 이진 트리 구현 및 탐색

이번 문제에서는 트리가 고정되지 않고 트리의 모양이 입력으로 주어진다.

 

1. 트리 만들기 (구현)

◦ 트리는 연결이진트리로 구현하며 각 노드에 저장되는 정보는 아래와 같다.

◦ 선위순회 순서로 각 노드에 대한 정보가 주어지면, 루트노드부터 확장해 가는 방식으로 트리를 구성할 수 있다.
- 노드 번호는 유일한 양의 정수며, 노드 번호에 특별한 순서는 없다.

- 각 노드에 대한 정보는 괄호에 싸인 세 개의 정수, 즉 (x y z)로 표현된다.

- 여기서 x는 해당 노드의 번호, y는 x의 왼쪽 자식 노드의 번호, z는 x의 오른쪽 자식 노드의 번호를 나타낸다. 해당 자식이 없는 경우에는 번호 0이 주어진다.

 

 

 

2. 트리 탐색

◦ 트리 탐색은 루트노드에서 시작하여 자식 링크를 따라 내려가면서 진행된다.

- 탐색 도중 만나는 노드에서 어느 자식을 따라 내려가는지 정보가 주어지면 탐색 중 방문되는 노드 번호들이 유일하게 결정된다.

예) 탐색 정보가 RLL로 주어질 경우(단, L은 왼쪽 자식, R은 오른쪽 자식을 의미)

탐색 중 방문하는 노드 번호를 순서대로 적으면 5 9 7 12가 된다. (아래 그림 참조)

RLL

 

 

 

문제) 위에서 설명한 방식대로, 트리 정보와 탐색 정보가 주어졌을 때 트리를 생성하고 탐색 도중 방문하는 노드 번호를 차례로 출력하는 프로그램을 작성하시오.

모든 노드마다 자신의 위치를 가리키는 포인터변수를 만들어 사용하면 안 됨.

- 오직 루트노드에 대해서만 허용. 즉, 트리는 루트노드를 통해서만 접근 가능.

 

입력 상세:

ㅇ트리 정보

- 첫 째 줄에 노드의 개수 n이 주어진다.

- 다음 n개의 줄에, 선위순회 순서로 노드의 정보가 주어진다(위 설명 참조).

ㅇ탐색 정보 (트리 정보가 모두 주어진 후)

-  탐색 횟수 s가 주어진다.

-  다음 s개의 줄에, 탐색 정보가 주어진다(각 탐색은 루트노드에서 새로 시작).

-  하나의 탐색 정보는 공백 없이,L과 R로 구성된 문자열(최대 길이 100)로 주어진다.

-  유효하지 않은 탐색 정보는 주어지지 않는다. 예를 들어, 위 트리에서 RRR과 같은 탐색 정보는 유효하지 않다. 두 번 오른쪽 자식을 따라 내려가면 노드 10인데, 노드 10의 오른쪽 자식은 정의되지 않았기 때문이다.

 

출력 상세:

탐색 시 방문하는 노드 번호를 순서대로 출력한다(한 줄에 한 번의 탐색 결과를 출력).

 

test case

 

 

 

 

(전체 코드)

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

typedef struct NODE {
    int data;
    struct NODE* left;
    struct NODE* right;
} NODE;

NODE* createNode(int data);
void insertNode(NODE* root, int parent, int lChild, int rChild);
NODE* buildTree(int n, int nodes[][3]);
void searchTree(NODE* root, char* path);

int main() {
    int n;
    scanf("%d", &n);
    int nodes[n][3]; // 2차원 배열을 이용
    for (int i = 0; i < n; i++) {
        scanf("%d %d %d", &nodes[i][0], &nodes[i][1], &nodes[i][2]);  // 각 노드의 정보 입력
    }
    NODE* root = buildTree(n, nodes);

    int s;
    char path[101] = {0};
    scanf("%d", &s);
    for (int i = 0; i < s; i++) {
        scanf("%s", path);
        searchTree(root, path);  // 탐색 및 출력
    }

    free(root);
    return 0;
}

NODE* createNode(int data) {
    NODE* newNode = (NODE*)malloc(1 * sizeof(NODE));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 노드를 트리에 삽입하는 함수
void insertNode(NODE* root, int parent, int lChild, int rChild) {
    if (root == NULL) return;

    if (root->data == parent) {
        if (lChild != 0)
            root->left = createNode(lChild);
        if (rChild != 0) 
            root->right = createNode(rChild);
    } 
    else if (root->data != parent) { // 재귀호출
        if (root->left != NULL) 
            insertNode(root->left, parent, lChild, rChild);
        if (root->right != NULL) 
            insertNode(root->right, parent, lChild, rChild);
    }
}

NODE* buildTree(int n, int nodes[][3]) {
    NODE* root = createNode(nodes[0][0]);
    for (int i = 0; i < n; i++) {
        insertNode(root, nodes[i][0], nodes[i][1], nodes[i][2]);
    }
    return root;
}

void searchTree(NODE* root, char* path) {
    NODE* curNode = root;
    printf(" %d", curNode->data);

    int pathLen = strlen(path);
    for (int i = 0; i < pathLen; i++) {
        if (path[i] == 'L') 
            curNode = curNode->left;
        else if (path[i] == 'R') 
            curNode = curNode->right;

        if (curNode != NULL) 
            printf(" %d", curNode->data);
        else
            break;
    }
    printf("\n");
}

/*
9
5 3 9
3 8 15
8 0 2
2 0 0
15 0 0
9 7 10
7 12 0
12 0 0
10 0 0
3
RLL
LL
LR
*/

 

 

 

 

 

 

참고 및 출처: 데이터 구조 원리와 응용(국형준교수님)