백준알고리즘 1991번, 트리 사용하기

그래프와 트리쪽 알고리즘이 약해서 요즘 이 파트를 공부하고있습니다. 2진 트리의 원소를 입력받아 순회 종류별로 출력해주는 문제입니다. 재귀적으로 깔끔하게 푸는 것이 중요하겠죠!

 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


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


using namespace std;


class BTreeNode {
public:
 char elem;
 int lindex;
 int rindex;
 BTreeNode()
 {
  BTreeNode(0, 0, 0);
 }

 BTreeNode(char c, int n1, int n2):elem(c),lindex(n1),rindex(n2)
 {
 }
};

void Preorder(BTreeNode node);

void Inorder(BTreeNode node);

void Postorder(BTreeNode node);

BTreeNode bt[26];

int main(void) {
 memset(bt, 0, sizeof bt);
 int t;
 char c1, c2, c3;

#ifndef ONLINE_JUDGE
 freopen("input.txt", "r", stdin);
 freopen("output.txt", "w", stdout);
#endif

 scanf("%d\n", &t);
 for (int i = 0; i < t; i++) {
   scanf("%c %c %c\n", &c1, &c2, &c3);
   bt[c1-'A'].elem = c1; bt[c1 - 'A'].lindex = c2 - 'A'; bt[c1 - 'A'].rindex = c3 - 'A';
   if (c2 == '.')
    bt[c1 - 'A'].lindex = -1;
   if (c3 == '.')
    bt[c1 - 'A'].rindex = -1;
 }

 Preorder(bt[0]);
 puts("");
 Inorder(bt[0]);
 puts("");
 Postorder(bt[0]);
 
#ifndef ONLINE_JUDGE
 fclose(stdin);
 fclose(stdout);
#endif

 return 0;
 
}

void Preorder(BTreeNode node) {
 printf("%c", node.elem); 
 if (node.lindex != -1)
  Preorder(bt[node.lindex]);
 if (node.rindex != -1)
  Preorder(bt[node.rindex]);
}

void Inorder(BTreeNode node) {
 if (node.lindex != -1)
  Inorder(bt[node.lindex]);
 printf("%c", node.elem);
 if (node.rindex != -1)
  Inorder(bt[node.rindex]);
}

void Postorder(BTreeNode node) {
 if (node.lindex != -1)
  Postorder(bt[node.lindex]);
 if (node.rindex != -1)
  Postorder(bt[node.rindex]);
 printf("%c", node.elem);
}

Contents