Tree - 난이도(하)

[ 문제 ]

완전 이진 트리를 만들고 레벨 전위 중위 후위 사선에 대한 출력을 할 수 있는 프로그램을 만드시오. [10 9 17 11 23 8 66 21 2 33 51 7 28]   그리고 만들어진 트리를 이용하여 레벨, 전위, 중위, 후위, 사선 출력하시오 레벨 10 9 17 11 23 8 66 21 2 33 51 7 28 전위 10 9 11 21 2 23 33 51 17 8 7 28 66 중위 21 11 2 9 33 23 51 10 7 8 28 17 66 후위 21 2 11 33 51 23 9 7 28 8 66 17 10 사선1 10 9 11 21 사선2 10 17 66

 

[ 입 출력 조건 ]

입력 첫 줄에는 Case의 수 n( 1< n <= 50 )  이다  그 다음 줄부터 명령어가 들어 온다. 숫자가 들어오면 이진 트리를 구성하는 노드(양수이며  2< n <=1000) 이고 문자가 들어 오면 출력을 한다.(A레벨 B전위 C중위 D후위 E 사선1 F사선2 ) * 을 만난다면 케이스의 입력이 종료된다.   출력  각 케이스는 Case로 구분하고, 해당 명령어가 입력된다면 명령어를 출력하고 결과 출력을 한다. 각 명령어는 개행 문자로 구분한다.

 

[ 입출력 예 ]

2 10 9 17 A 11 F 23 B C D 8 66 21 2 33 51 7 28 A B C D E F * 10 9 17 1123 8 66 21 2 33 51 7 28 A B C D E F *

Case1 A 10 9 17 F 10 17 B 10 9 11 23 17 C 11 9 23 10 17 D 11 23 9 17 10 A 10 9 17 11 23 8 66 21 2 33 51 7 28 B 10 9 11 21 2 23 33 51 17 8 7 28 66 C 21 11 2 9 33 23 51 10 7 8 28 17 66 D 21 2 11 33 51 23 9 7 28 8 66 17 10 E 10 9 11 21 F 10 17 66 Case2 A 10 9 17 11 23 8 66 21 2 33 51 7 28 B 10 9 11 21 2 23 33 51 17 8 7 28 66 C 21 11 2 9 33 23 51 10 7 8 28 17 66 D 21 2 11 33 51 23 9 7 28 8 66 17 10 E 10 9 11 21 F 10 17 66

 

Self-reflection

배보다 배꼽이 더 컷던 문제...알고리즘은 어렵지 않았지만, 입력 받는게 까다로웠다.

Code

Colored By Color Scripter™

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129

#include <stdio.h> #include <string.h> char arr[100]; int arr_tree[1000];   void preorder(int idx); void inorder(int idx); void postorder(int idx); void showleft(int idx); void showright(int idx);   int main() {     int cnt = 0;     int n = 0;         scanf("%d", &n);     for (int i = 0; i < n; i++)     {         cnt = 0;         for (int j = 0; j < 1000; j++)         {             if (arr_tree[j] == -1)                 break;             arr_tree[j] = -1;         }           printf("Case%d\n", i+1);         while (1)         {             scanf("%s", &arr); // %s로 받으면 스페이스에서 끊어준다.                         if (strcmp(arr, "*") == 0)                 break;             else if (strcmp(arr, "A") < 0) // 숫자             {                 sscanf(arr, "%d", &arr_tree[cnt]);                 cnt++;             }             else if (strcmp(arr, "A") == 0) // 레벨 순회             {                 printf("A ");                 for (int j = 0; j < 1000; j++)                 {                     if (arr_tree[j] == -1)                         break;                     printf("%d ", arr_tree[j]);                 }                 printf("\n");             }             else if (strcmp(arr, "B") == 0)             {                 printf("B ");                 preorder(1);                 printf("\n");             }             else if (strcmp(arr, "C") == 0)             {                 printf("C ");                 inorder(1);                 printf("\n");             }             else if (strcmp(arr, "D") == 0)             {                 printf("D ");                 postorder(1);                 printf("\n");             }             else if (strcmp(arr, "E") == 0)             {                 printf("E ");                 showleft(1);                 printf("\n");             }             else if (strcmp(arr, "F") == 0)             {                 printf("F ");                 showright(1);                 printf("\n");             }         }     }     return 0; }   void preorder(int idx) {     if (arr_tree[idx - 1] == -1)         return;       printf("%d ", arr_tree[idx - 1]);     preorder(2 * idx);     preorder(2 * idx + 1); }   void inorder(int idx) {     if (arr_tree[idx - 1] == -1)         return;       inorder(2 * idx);     printf("%d ", arr_tree[idx - 1]);     inorder(2 * idx + 1); }   void postorder(int idx) {     if (arr_tree[idx - 1] == -1)         return;       postorder(2 * idx);     postorder(2 * idx + 1);     printf("%d ", arr_tree[idx - 1]); }   void showleft(int idx) {     if (arr_tree[idx - 1] == -1)         return;     printf("%d ", arr_tree[idx - 1]);     showleft(2 * idx); }   void showright(int idx) {     if (arr_tree[idx - 1] == -1)         return;     printf("%d ", arr_tree[idx - 1]);     showright(2 * idx + 1); }

SampleData.zip