[백준] 1991번_알고리즘_트리 순회

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

1991번: 트리 순회

문제

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal) 한 결과를 출력하는 프로그램을 작성하시오.

예를 들어 위와 같은 이진 트리가 입력되면,

전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)

중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)

후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)

가 된다.

입력

첫째 줄에는 이진 트리의 노드의 개수 N(1≤ N ≤26)이 주어진다. 둘째 줄부터 N 개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는.으로 표현된다.

출력

첫째 줄에는 이진 트리의 노드의 개수 N(1≤ N ≤26)이 주어진다. 둘째 줄부터 N 개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는.으로 표현된다.

---

트리

트리는 말 그대로 나무를 거꾸로 세워놓은 것처럼 생긴 그래프다.

믿기지 않겠지만, 나무를 거꾸로 세워놓은 듯한 그림을 그려봤다.

​

- 트리의 조건

1. 모든 노드들이 연결되어 있어야 한다.

2. 사이클(순환)을 가지지 않아야 한다.

3. 루트라는 특별한 노드가 한 개 존재해야 하고, 루트 노드로부터 다른 어떠한 노드로 갈 때, 그 경로가 유일해야 한다.

트리 용어

루트 노드 : 가장 놓은 곳에 위치한 노드를 루트(root) 노드라고 한다.

서브 트리 : 루트 노드를 제외한 어떤 노드를 루트 노드로 하여 만들어지는 트리를 말한다. 위 그림에서 루트 노드가 없어졌다고 생각해 보면, 2와 3번이 루트 노드가 되어 또 다른 트리를 구성한다. 이 트리를 서브 트리라고 한다.

차수 : 어떤 노드의 서브 트리의 개수를 말하는데, 2번 노드의 차수는 2이다. 마찬가지로, 4번 노드의 차수는 2이다.

자식 노드 : 어떤 노드의 서브 트리의 루트 노드들을 말한다. 2번 노드의 자식 노드는 4와 5번 노드이다.

부모 노드 : 자식 노드의 반대로, 4번 노드의 부모 노드는 2번 노드이고, 12번 노드의 부모 노드는 6번 노드이다.

형제 노드 : 동일한 부모를 가지는 노드로, 4와 5번 노드는 형제이고, 12와 13번 노드도 형제이다.

잎 노드(단말 노드) : 차수가 0인 노드로, 자식 노드가 없는 노드이다. 8, 9, 10, 11, 12, 13, 14, 15번 노드들이 잎 노드다.

비단말 노드 : 잎 노드와 반대로 자식 노드가 1개 이상인 노드로 위 그림에서는 잎 노드를 제외한 모든 노드들이 비단말 노드이다.

이진 트리

이진 트리는 트리의 조건을 만족하면서, 루트와 최대 2개의 서브 트리로 이루어진다.

즉, 어떤 노드의 자식 노드가 3개일 수 없다. 하지만 자식 노드가 0개, 1개, 2개인 건 가능하다.

이진 트리는 루트와 왼쪽 서브 트리, 오른쪽 서브 트리로 구성된다. 물론 자식 노드가 0개면 왼쪽 서브 트리와 오른쪽 서브 트리가 존재하지 않을 수도 있다.

​

이진 트리 순회 방법에는 3가지 방법이 있다.

- 전위 순회(preorder)

- 중위 순회(inorder)

- 후위 순회(postorder)

전위 순회

루트 노드를 방문하고, 그다음 왼쪽 서브 트리, 그다음 오른쪽 서브 트리를 방문한다.

위에 있던 뒤집어진 나무 그림에서 전위 순회를 이용하면,

1, 2, 4, 8, 9, 5, 10, 11, 3, 6, 12, 13, 7, 14, 15 번 순서로 모든 노드를 방문한다.

중위 순회

왼쪽 서브 트리를 방문하고, 그다음 루트 노드, 그다음 오른쪽 서브 트리를 방문한다.

위에 있던 뒤집어진 나무 그림에서 중위 순회를 이용하면,

8, 4, 9, 2, 10, 5, 11, 1, 12, 6, 13, 3, 14, 7, 15 번 순서로 모든 노드를 방문한다.

후위 순회

왼쪽 서브 트리를 방문하고, 그다음 오른쪽 서브 트리, 그다음 루트 노드를 방문한다.

위에 있던 뒤집어진 나무 그림에서 후위 순회를 이용하면,

8, 9, 4, 10, 11, 5, 2, 12, 13, 6, 14, 15, 7, 3, 1 번 순서로 모든 노드를 방문한다.

---

코드 설명

1. 구조체

​

typedef struct node* TreeNode;

typedef struct node {

char data;

TreeNode left, right;

}node;

​

구조체는 사용자가 직접 만드는 데이터 타입이다. 기본 데이터 타입에는 int, float 등이 있다.

이미 존재하는 데이터 타입들을 필요에 따라 구성하는 것이다.

나는 node라는 데이터 타입을 만들었다.

​

2. 전위 순회

​

void preorder(TreeNode ptr) {

if (ptr != NULL) {

cout << ptr->data;

preorder(ptr->left);

preorder(ptr->right);

}

}

​

NULL은 비어있음을 의미하는데,

방문한 노드가 비어있지 않다면, if 문을 실행한다.

전위 순회는 루트 노드, 왼쪽 서브 트리, 오른쪽 서브 트리 순서로 방문을 한다.

루트 노드를 방문하면 현재 노드를 출력하면 된다.

위에서 만든 구조체에서 data를 출력한다.

그다음 다시 재귀적으로 preorder 함수를 호출하여 모든 노드를 방문하게 된다.

​

3. 구조체 선언

​

node nodes[27];

​

1번에서는 구조체를 만들었을 뿐이지 호출은 하지 않았다.

이 구조체를 사용하기 위해서는 꼭 선언을 해야 한다.

선언한 후로 구조체가 메모리에 잡히게 된다.

​

4.

​

for (int i = 0; i < n; i++) {

cin >> a >> b >> c;

nodes[a - 'A'].data = a;

if (b == '.') nodes[a - 'A'].left = NULL;

else nodes[a - 'A'].left = &nodes[b - 'A'];

if (c == '.') nodes[a - 'A'].right = NULL;

else nodes[a - 'A'].right = &nodes[c - 'A'];

}

​

아래 내용을 사용자에게 입력받은 개수 n 만큼 반복한다.

'A'부터 'Z'까지의 문자를 입력받는다.

처음 입력받은 값을 변수 a, b, c에 차례로 담는다.

nodes[a-'A']에서 a-'A'를 하는 이유는 다음과 같다.

a는 입력받은 값을 담고 있는 변수이다.

만약 'A'를 입력받으면 'A'-'A'를 해서 0이 된다.

그러면 nodes의 0번 index에 방문한다.

만약 'B'를 입력받으면 'B'-'A'를 해서 1이 되어 nodes의 1번 index에 방문하게 된다.

node 구조체에서

.data는 현재 노드를 출력한다.

.left는 왼쪽 서브 트리를 방문한다.

.right는 오른쪽 서브 트리를 방문한다.

만약 사용자가 .을 입력한다면 자식 노드가 없다는 뜻이므로, nodes의 해당 index에 NULL 값을 넣는다.

​

5. 방문 순서 출력

​

preorder(&nodes[0]);

​

nodes의 0번 index부터 시작하여 전위 순회 방문 순서를 출력하게 된다.

코드

#include <iostream>
using namespace std;

typedef struct node* TreeNode;
typedef struct node {
    char data;
    TreeNode left, right;
}node;

void preorder(TreeNode ptr) {
    if (ptr != NULL) {
        cout << ptr->data;
        preorder(ptr->left);
        preorder(ptr->right);
    }
}

void inorder(TreeNode ptr) {
    if (ptr != NULL) {
        inorder(ptr->left);
        cout << ptr->data;
        inorder(ptr->right);
    }
}

void postorder(TreeNode ptr) {
    if (ptr != NULL) {
        postorder(ptr->left);
        postorder(ptr->right);
        cout << ptr->data;
    }
}

int main() {
    node nodes[27];
    int n;
    char a, b, c;

    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> a >> b >> c;
        nodes[a - 'A'].data = a;
        if (b == '.') nodes[a - 'A'].left = NULL;
        else nodes[a - 'A'].left = &nodes[b - 'A'];
        if (c == '.') nodes[a - 'A'].right = NULL;
        else nodes[a - 'A'].right = &nodes[c - 'A'];
    }

    preorder(&nodes[0]);
    cout << endl;
    inorder(&nodes[0]);
    cout << endl;
    postorder(&nodes[0]);
    
    return 0;
}

 

​

​