[8] 트리 ⑥ 응용 (1) : 연결리스트를 이용한 트리 구현

트리 1주차: 이진 트리 삽입과 탐색

[연결리스트를 이용한 이진 트리]

• 이진트리의 노드에 저장되는 정보
  - data: 노드에 저장되는 값 (아래 문제에서 폴더의 용량) - left: 좌측 child 노드를 가리키는 링크
  - right: 우측 child 노드를 가리키는 링크
• 이진 트리를 이용한 폴더 구조 표현
  - 이진트리는 최대 2개의 자식 노드를 갖음.
  - 컴퓨터의 폴더 구조가 이진 트리 형태로 구성되어 있다고 가정함.
• - 각각의 노드는 폴더 이름과 용량을 나타내며, 아래 트리에서 폴던 F1에는 20M 가 저장되 어 있음을 의미함.

[ 문제 1 ] 위 트리를 연결리스트를 이용해서 구현하고, 주어진 노드에 대해 자신과 왼쪽 자식, 우측 자식의 용량을 순서대로 출력하시오.

※ 참고사항: 실습 및 테스트 용이성을 위해 본 문제에서는 고정된 트리를 사용하지만, 일반적으로 동적으로 삽입, 삭제 가능한 트리를 사용함

도움말:

• 루트노드 삽입 함수를 만들어 사용하며, data(폴더 용량), left (왼쪽 자식 링크), right (오른쪽 자식 링크) 를 인수로 받음.
• 모든 노드는 아래 그림과 같이 자신의 위치를 가리키는 포인터변수를 만들어 사용함.

트리 구조

• 단말 노드부터 생성하고, 부모노드를 붙여가는 방식으로 트리를 구성함.
  - 예를 들어, F7과 F8을 생성하고, 이를 이용해 F6 생성하여 F6, F7, F8로 구성된 트리 생성 - 비슷한 방법으로 트리를 확장해 나감
• 출력:
• 자식 및 노드 존재 여부에 따라 출력 내용이 달라짐
  - 한쪽 자식만 존재하는 경우, 자신과 해당 자식 노드의 용량 2개 값만 출력 - 자식 노드가 없는 경우, 자신의 용량 1개 값만 출력
  - 존재하지 않는 노드번호가 입력되는 경우 –1을 출력

코드 풀이

이진 트리와 노드 생성 알고리즘 해석

1. 노드 구조체 정의

이 구조체는 노드의 데이터를 저장하고, 왼쪽 자식 노드와 오른쪽 자식 노드를 가리키는 포인터를 포함합니다.

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

typedef int element;

// 노드 구조체 정의
typedef struct TreeNode {
    element data;               // 노드의 데이터
    struct TreeNode* left;     // 왼쪽 자식 노드를 가리키는 포인터
    struct TreeNode* right;    // 오른쪽 자식 노드를 가리키는 포인터
} TreeNode;

2. 노드 생성 함수

노드를 생성하는 함수는 다음과 같습니다. 이 함수는 주어진 데이터를 저장하는 노드를 동적으로 할당하고, 왼쪽과 오른쪽 자식 노드 포인터를 설정합니다.

노드 생성 함수는 다음과 같은 동작을 수행합니다:

 

• 동적으로 메모리를 할당하여 새로운 노드를 생성합니다.
• 노드의 데이터를 설정합니다.
• 왼쪽 및 오른쪽 자식 노드를 설정합니다.
• 생성된 노드를 반환합니다.

TreeNode* makeNode(element data, TreeNode *left, TreeNode *right) {
    TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
    if (node == NULL) {
        fprintf(stderr, "메모리 할당 실패\n");
        exit(1);
    }
    node->data = data;
    node->left = left;
    node->right = right;
    return node;
}

3. 노드의 데이터와 자식을 반환하는 함수

세 가지 함수는 각각 노드의 데이터를 반환하고, 왼쪽 자식과 오른쪽 자식을 반환합니다.

 

• elementNode 함수는 주어진 노드의 데이터를 반환합니다.
• leftChild 함수는 주어진 노드의 왼쪽 자식을 반환합니다.
• rightChild 함수는 주어진 노드의 오른쪽 자식을 반환합니다.

element elementNode(TreeNode* v) {return v->data;}
TreeNode* leftChild(TreeNode* v) {return v->left;}
TreeNode* rightChild(TreeNode* v) {return v->right;}

 

4. 트리 구조 생성 및 노드 출력

메인 함수에서는 이진 트리를 구성하고, 입력된 번호에 따라 특정 노드와 그 자식 노드의 데이터를 출력합니다. 이 과정은 다음과 같습니다:

 

1. 여러 개의 노드를 생성하고 트리 구조를 구성합니다.
2. 사용자가 입력한 번호에 따라 특정 노드를 선택합니다.
3. 선택된 노드와 그 자식 노드의 데이터를 출력합니다.

int main() {
    TreeNode *n8 = makeNode(80, NULL, NULL);
    TreeNode *n7 = makeNode(130, NULL, NULL);
    TreeNode *n6 = makeNode(120, n7, n8);
    TreeNode *n5 = makeNode(90, NULL, NULL);
    TreeNode *n4 = makeNode(70, NULL, NULL);
    TreeNode *n3 = makeNode(50, NULL, n6);
    TreeNode *n2 = makeNode(30, n4, n5);
    TreeNode *n1 = makeNode(20, n2, n3);

    TreeNode *tmp;
    int n;
    scanf("%d", &n);

    switch (n) {
        case 1: tmp = n1; break;
        case 2: tmp = n2; break;
        case 3: tmp = n3; break;
        case 4: tmp = n4; break;
        case 5: tmp = n5; break;
        case 6: tmp = n6; break;
        case 7: tmp = n7; break;
        case 8: tmp = n8; break;
        default: printf("-1"); exit(1);
    }

    printf("%d ", elementNode(tmp));
    if (leftChild(tmp) != NULL) printf("%d ", elementNode(leftChild(tmp)));
    if (rightChild(tmp) != NULL) printf("%d ", elementNode(rightChild(tmp)));
}

전체 코드 설명

이 프로그램은 이진 트리의 각 노드를 생성하고, 트리 구조를 구성한 다음, 사용자가 입력한 번호에 따라 특정 노드와 그 자식 노드의 데이터를 출력합니다.

1. makeNode 함수는 새로운 노드를 동적으로 생성하고 초기화합니다.
2. elementNode, leftChild, rightChild 함수는 각각 노드의 데이터와 자식 노드를 반환합니다.
3. 메인 함수에서는 트리를 구성하고, 사용자의 입력에 따라 특정 노드와 그 자식 노드의 데이터를 출력합니다.

전체 코드

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

typedef int element;

// 노드 구조체 정의
typedef struct TreeNode {
    element data;               // 노드의 데이터
    struct TreeNode* left;     // 왼쪽 자식 노드를 가리키는 포인터
    struct TreeNode* right;    // 오른쪽 자식 노드를 가리키는 포인터
} TreeNode;

// 노드 생성 함수
TreeNode* makeNode(element data, TreeNode *left, TreeNode *right) {
    TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
    if (node == NULL) {
        fprintf(stderr, "메모리 할당 실패\n");
        exit(1);
    }
    node->data = data; // 데이터 저장

    node->left = left; // 왼쪽 노드 생성
    node->right = right;//오른쪽 노드 생성

    return node; //반환
}

element elementNode(TreeNode* v) {return v->data;}// 노드의 요소를 반환
TreeNode* leftChild(TreeNode* v) {return v->left;}// 노드 v의 왼쪽 자식을 반환
TreeNode* rightChild(TreeNode* v) {return v->right;}// 노드 v의 오른쪽 자식을 반환

int main(){
    //조건에 따른 트리 노드 생성
    TreeNode *n8 = makeNode(80,NULL,NULL);
    TreeNode *n7 = makeNode(130,NULL,NULL);
    TreeNode *n6 = makeNode(120,n7,n8);
    TreeNode *n5 = makeNode(90,NULL,NULL);
    TreeNode *n4 = makeNode(70,NULL,NULL);
    TreeNode *n3 = makeNode(50,NULL,n6);
    TreeNode *n2 = makeNode(30,n4,n5);
    TreeNode *n1 = makeNode(20,n2,n3);

    TreeNode *tmp; // 입력된 값에 따른 노드를 저장할 임의의 노드 변수

    int n; scanf("%d",&n);//입력받기
    switch (n)// // 입력된 번호에 따라 tmp가 가리킬 노드를 결정
    {
        case 1: tmp = n1;break;
        case 2: tmp = n2;break;
        case 3: tmp = n3;break;
        case 4: tmp = n4;break;
        case 5: tmp = n5;break;
        case 6: tmp = n6;break;
        case 7: tmp = n7;break;
        case 8: tmp = n8;break;

        default: printf("-1"); exit(1); // 유효하지 않은 입력 시 프로그램 종료
    }
    printf("%d ",elementNode(tmp));//현재 노드 출력
    if(leftChild(tmp)!=NULL) printf("%d ",elementNode(leftChild(tmp)));// 왼쪽 자식이 존재하면 왼쪽 자식의 데이터 출력
    if(rightChild(tmp)!=NULL) printf("%d ",elementNode(rightChild(tmp))); //오른쪽 자식이 존재하면 오른쪽 자식의 데이터 출력

}