[8] 트리 ⑦ 응용 (2) : 폴더 용량 출력 프로그램

트리 2주 차: 트리의 순회

[ 문제 1 ] 위 트리에 대해 순회 방법과 폴더 id가 주어지면, 아래의 트리의 루트노드에서 출발하 여 해당 노드를 탐색하여 찾고, 이 노드를 시작점으로 순회하며 각 폴더의 용량을 출력하는 프로그램을 작성하시오.

- 노드 id를 저장하기 위해 노드는 다음과 같은 구조체를 만들어 사용함.

- 지난주 문제의 F1, F2와 같은 노드별 포인터는 사용할 수 없으며, 주어진 노드를 탐색하여 찾아 야 함.

입출력 상세:

◦ 순회 방법 종류 (입력)
- 1: 전위순회, 2: 중위순회, 3: 후위순회

◦ 존재하지 않는 폴더 이름이 입력되는 경우 –1을 출력

이진 트리와 순회 알고리즘 해석

이번 포스팅에서는 이진트리의 노드 생성과 전위, 중위, 후위 순회 알고리즘을 설명합니다. 각 함수와 알고리즘의 동작을 세부적으로 해석하여 이진트리 자료구조와 순회 방법에 대한 이해를 돕겠습니다.

1. 노드 구조체 정의

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

 

노드 구조체의 정의:

 

• element data: 노드의 데이터를 저장

• TreeNode* left: 왼쪽 자식 노드를 가리키는 포인터

• TreeNode* right: 오른쪽 자식 노드를 가리키는 포인터

2. 노드 생성 함수

노드를 생성하는 함수는 다음과 같습니다.

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

 

노드 생성 함수의 동작:

 

1. 동적으로 메모리를 할당하여 새로운 노드를 생성

2. 노드의 데이터를 설정

3. 왼쪽 및 오른쪽 자식 노드를 설정

4. 생성된 노드를 반환

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. 전위 순회 (Pre-order Traversal)

현재 노드를 방문하고, 왼쪽 자식을 순회한 후 오른쪽 자식을 순회합니다.

 

void preOrder(TreeNode* node) {     if (node != NULL) {         printf(" %d", node->data);         preOrder(node->left);         preOrder(node->right);     } }

 

2. 중위 순회 (In-order Traversal)

왼쪽 자식을 순회하고, 현재 노드를 방문한 후 오른쪽 자식을 순회합니다.

 

void inOrder(TreeNode* node) {     if (node != NULL) {         inOrder(node->left);         printf(" %d", node->data);         inOrder(node->right);     } }

 

3. 후위 순회 (Post-order Traversal)

왼쪽 자식을 순회하고, 오른쪽 자식을 순회한 후 현재 노드를 방문합니다.

 

void postOrder(TreeNode* node) {     if (node != NULL) {         postOrder(node->left);         postOrder(node->right);         printf(" %d", node->data);     } }

5. 트리 구조 생성 및 순회 실행

메인 함수에서는 이진트리를 구성하고, 입력된 키에 따라 특정 노드를 전위, 중위, 후위 순회합니다. 이 과정은 다음과 같습니다:

 

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 key, node;
    scanf("%d %d", &key, &node);

    switch (node) {
        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);
    }

    if (key == 1) preOrder(tmp);
    else if (key == 2) inOrder(tmp);
    else if (key == 3) postOrder(tmp);
}
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 key, node;
    scanf("%d %d", &key, &node);

    switch (node) {
        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);
    }

    if (key == 1) preOrder(tmp);
    else if (key == 2) inOrder(tmp);
    else if (key == 3) postOrder(tmp);
}

메인 함수 설명

이 프로그램은 이진 트리를 생성하고 사용자가 입력한 키와 노드 번호에 따라 특정 노드부터 전위, 중위, 후위 순회를 수행합니다.

전체 로직은 다음과 같이 구성됩니다:

 

1. 노드 생성 및 트리 구성:

• 여러 개의 노드를 생성하고 트리 구조를 구성합니다. 트리의 구조는 다음과 같습니다

        20
      /    \
    30      50
   /  \      \
  70   90    120
             /   \
          130   80

• makeNode 함수를 사용하여 노드를 생성하고 각 노드의 데이터를 설정합니다.

 

2. 입력 받기:

scanf 함수를 사용하여 사용자로부터 두 개의 정수 입력을 받습니다. 첫 번째 정수 key는 순회 방법을 나타내고, 두 번째 정수 node는 순회를 시작할 노드의 번호를 나타냅니다.

 

3. 노드 선택:

switch 문을 사용하여 입력된 노드 번호에 따라 tmp 포인터가 가리킬 노드를 결정합니다.

유효한 노드 번호가 입력되지 않으면 프로그램은 -1을 출력하고 종료합니다.

 

4. 순회 수행:

입력된 key 값에 따라 전위, 중위, 후위 순회 함수 중 하나를 호출하여 선택된 노드를 시작으로 순회를 수행합니다.

key가 1이면 전위 순회, 2이면 중위 순회, 3이면 후위 순회를 수행합니다.

예제 실행 과정

1. 노드 생성 및 트리 구성:

 

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);

 

2. 사용자 입력받기:

scanf("% d % d", &key, &node); 예를 들어, 1 3을 입력받는다고 가정합니다.

 

3. 노드 선택:

switch (node) 문에서 node가 3이면 tmp는 n3을 가리키게 됩니다.

 

4. 순회 수행:

key가 1이므로 preOrder(tmp) 함수를 호출합니다. 이는 노드 50부터 시작하여 전위 순회를 수행합니다.

전체 코드 설명

makeNode 함수는 새로운 노드를 동적으로 생성하고 초기화합니다.

elementNode, leftChild, rightChild 함수는 각각 노드의 데이터와 자식 노드를 반환합니다.

순회 함수 (preOrder, inOrder, postOrder)는 각각 전위, 중위, 후위 순회를 수행합니다.

메인 함수에서는 트리를 구성하고, 사용자의 입력에 따라 특정 노드를 순회하여 데이터를 출력합니다.