C++ Algorithm/백준 알고리즘 문제 풀이

트리 사용하기

3영2 2019. 4. 29. 12:51
반응형

트리 순회 개념 

출처 - 위키백과 :https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EC%88%9C%ED%9A%8C

-전위 순회

전위 순회(preorder)는 다음과 같은 방법으로 진행한다.

  1. 노드를 방문한다.
  2. 왼쪽 서브 트리를 전위 순회한다.
  3. 오른쪽 서브 트리를 전위 순회한다.

전위 순회는 깊이 우선 순회(depth-first traversal)라고도 한다.

-중위 순회

중위 순회(Inorder)은 다음의 순서로 진행된다.

  1. 왼쪽 서브 트리를 중위 순회한다.
  2. 노드를 방문한다.
  3. 오른쪽 서브 트리를 중위 순회한다.

중위 순회는 대칭 순회(symmetric)라고도 한다.

-후위 순회

후위 순회(postorder)는 다음과 같은 방법으로 진행한다.

  1. 왼쪽 서브 트리를 후위 순회한다.
  2. 오른쪽 서브 트리를 후위 순회한다.
  3. 노드를 방문한다.

-레벨 순서 순회

레벨 순서 순회(level-order)는 모든 노드를 낮은 레벨부터 차례대로 순회한다. 레벨 순서 순회는 너비 우선 순회(breadth-first traversal)라고도 한다.

  • 전위 순회: F, B, A, D, C, E, G, I, H (root, left, right)
  • 중위 순회: A, B, C, D, E, F, G, H, I (left, root, right)
  • 후위 순회: A, C, E, D, B, H, I, G, F (left, right, root)
  • 레벨 순서 순회: F, B, G, A, D, I, C, E, H

1991번 문제 : 트리 순회

https://www.acmicpc.net/problem/1991


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
#include <iostream>
#include <string>
using namespace std;
 
string resultA, resultB, resultC;
 
class TreeNode
{
public:
    char value;
    TreeNode *right = NULL;
    TreeNode *left = NULL;
 
    TreeNode()
    {
        value = ' ';
        right = NULL;
        left = NULL;
    }
 
    void SetNode(char v, TreeNode *l, TreeNode *r)
    {
        value = v;
        right = r;
        left = l;
    }
 
 
    void PreorderTraversal(TreeNode *n)
    {
        if (n != NULL)
        {
            resultA += n->value;
            PreorderTraversal(n->left);
            PreorderTraversal(n->right);
        }
 
    }
 
    void InorderTraversal(TreeNode *n)
    {
        if (n != NULL)
        {
            InorderTraversal(n->left);
            resultB += n->value;
            InorderTraversal(n->right);
        }
    }
 
    void PostorderTraversal(TreeNode *n)
    {
        if (n != NULL)
        {
            PostorderTraversal(n->left);
            PostorderTraversal(n->right);
            resultC += n->value;
        }
    }
};
 
TreeNode* node = new TreeNode[27];
 
int main()
{
    int num;
    cin >> num;
 
    while (num > 0)
    {
        char v, l, r;
        cin >> v >> l >> r;
 
        if(l != '.' && r!= '.')
            node[(int)(v - 'A')].SetNode(v, &node[(int)(l - 'A')], &node[(int)(r - 'A')]);
 
        if (l != '.' && r == '.')
            node[(int)(v - 'A')].SetNode(v, &node[(int)(l - 'A')], NULL);
 
        if (l == '.' && r != '.')
            node[(int)(v - 'A')].SetNode(v, NULL, &node[(int)(r - 'A')]);
 
        if (l == '.' && r == '.')
            node[(int)(v - 'A')].SetNode(v, NULL, NULL);
 
        num--;
    }
 
    TreeNode *startNode = &node[0];
    startNode->PreorderTraversal(startNode);
    cout << resultA << endl;
    startNode->InorderTraversal(startNode);
    cout << resultB << endl;
    startNode->PostorderTraversal(startNode);
    cout << resultC << endl;
 
    delete[] node;
 
    return 0;
}
cs


반응형
저작자표시