[Data Structure] 이진 트리와 전위 순회, 중위 순회, 후위 순회의 개념 및 구현

날짜:


이진 트리, 완전 이진 트리, 포화 이진 트리



컴퓨터 공학과 학생이라면 필수적으로 자료 구조 수업을 듣게 되는데, 이 때 필수적으로 등장하는 개념이 트리이다. 트리는 말 그대로 노드 간의 계층 구조를 나무와 같은 형태로 표현한 것인데, 이 때 한 노드가 자식을 2개 이하로 갖는 것을 이진 트리 (binary tree) 라고 한다. 즉, 자식이 없을 수도 있다는 것이다. 기본적으로 아래 그림과 같은 형태를 이진트리라고 부른다.


맨 위에 있는 노드를 루트 노드 (root node) 라고 부르며, 자식이 없는 노드를 리프 노드 (leaf node) 라고 부른다. 위의 그래프는 리프 노드를 제외한 각 노드가 자식을 2개씩 가지고 있는데, 이와 같이 리프 노드를 제외한 모든 노드가 자식 노드를 2개 가지고 있는 형태를 완전 이진 트리 (complete binary tree) 라고 부른다. 즉, 자식 노드가 빈틈 없이 메꿔져 있는 경우를 말한다. 트리에서 각 층을 레벨 (level) 이라고 표현하는데, 루트 노드는 레벨 0, 그 자식들은 레벨 1, 그 밑은 레벨 2 ... 라는 말이다. 이 때, 아래 그림과 같이 모든 레벨이 꽉 찬 이진 트리를 포화 이진 트리 (full binary tree) 라고 부른다.








이진 트리의 전위 순회, 중위 순회, 후위 순회 탐색

위와 같은 이진 트리를 탐색하는 방법에는 보통 전위 순회, 중위 순회, 후위 순회 이 3가지 방법을 이용한다.  


 1. 전위 순회 (Preorder Traversal) 

탐색 순서 : root -> left -> right

root node -> left node -> right node 순서로 탐색하는 방법이다. 아래 그림을 참고해보자. root 노드 (A 노드) 를 탐색한 후, 왼쪽 노드인 B 노드를 탐색할 때, B 노드에 자식 노드가 존재한다면 A 노드의 오른쪽 노드 (C 노드)를 탐색하기 전에 B 노드의 자식 노드들을 탐색해줘야 한다. 아래 그림에서 B, C, D 가 이루는 그래프도 트리의 형태를 가지고 있는데, 이처럼 큰 트리 내에 종속하는 작은 트리를 서브 트리 (sub tree) 라고 부른다. 즉 A 노드를 탐색하고 A 의 왼쪽 노드 (B 노드) 를 루트 노드로 가지는 서브 트리를 전위 순회를 한 후, A 의 오른쪽 노드로 탐색해야 한다. 쉽게 말해, root -> left (전위 순회를 재귀적으로 수행) -> right (전위 순회를 재귀적으로 수행) 과 같은 탐색을 진행하는 것이다. 따라서 아래 그래프는 A -> B -> C -> D -> E 순서로 탐색하게 된다.






2. 중위 순회 (Inorder Traversal)

탐색 순서 : left -> root -> right

이번에는 left -> root -> right 순서로 탐색하는 방법이다. 순회의 이름은 root를 언제 탐색하느냐에 따라 결정되는데, 전위 순회는 root를 처음에 탐색하기 때문에 (root -> left -> right) preorder, 중위 순회는 root를 중간에 탐색하기 때문에 inorder가 된 것이다. 탐색 방법은 역시 해당 순회를 재귀적으로 적용시켜주면 된다. 다만 "왼쪽 노드" 부터 탐색을 해주기 때문에 가장 왼쪽 노드인 C 노드부터 탐색해주면 된다. 굳이 한국말로 풀이하자면, "A 노드의 왼쪽인 B 노드의 왼쪽인 C 노드" 가 가장 왼쪽 노드가 된다. 재귀를 적용하는 것이기 때문에 이런 결과가 생기는 것이다. 그 후 C -> B (C노드가 속한 서브 트리의 root 노드) -> D (C노드가 속한 서브 트리의 right 노드) 로 탐색하고, 다시 A -> E 순으로 탐색하게 된다.


3. 후위 순회 (Postorder Traversal)

탐색 순서 : left -> right -> root

마지막은 후위 순회이다. 위에서 설명한 내용과 크게 다르지 않다. left node인 B를 탐색하고, (B에 후위 순회를 재귀적으로 적용) E를 탐색한 후에, A를 탐색하면 된다. 역시 root 노드를 가장 마지막에 탐색하기 때문에 후위 순회라는 이름을 가지게 된다.



이진 트리와 트리 순회 구현

트리를 구현하는 방법은 여러가지가 있다. map 자료구조를 이용하여 구현할 수 있고, 단순히 vector나 배열만으로도 구현할 수 있다. 또한 3가지 순회는 모두 재귀적으로 구현된다는 것을 확인했었다. 백준 1991번 : 트리 순회를 보고 구현해보자. 


백준 1991. 트리 순회


문제




풀이

아래 코드를 분석해보자. 일단 부모 노드, 자식 노드 두 쌍을 map에 저장시켜서 트리를 구현했다. (이 때 '.'이면 자식이 하나만 있는 경우이다.) 이진 트리이므로 자식 노드를 pair로 묶어서 map에 key & value 형태로 저장했다. 만약 노드의 값이 int형 값이였다면 vector나 배열로 리스트를 만들어서 표현할 수도 있지만, 여기서 노드는 char 값을 가지기 때문에 map을 이용한 방법이 가장 적절하다.
다음은 순회하는 방법이다. preorder 함수를 보자. 매개변수로 각 node의 값이 들어오는데, 전위 순회는 각 서브 트리의 root 노드부터 탐색하기 때문에 탐색한 root 노드의 값을 먼저 출력한 후, left -> right 노드 순으로 preorder를 재귀적으로 호출해준다. 이 때 left 또는 right가 존재하는지도 체크해주어야 한다. 다른 순회도 마찬가지인데, inorder의 경우 left를 재귀적으로 돌리고 root를 출력하고 right를 재귀 탐색해주고, postorder는 left, right를 차례로 재귀 호출한 후 root를 출력해줬다.
다시 말하지만 트리를 구성하는 방법은 여러가지가 존재하며 순회를 하는 방법도 베이스는 재귀적 표현이지만 여러가지 방법이 나올 수 있다. 따라서 기본적인 아이디어만 잘 체크하고 자신의 코드로 표현해보도록 하자.

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>

using namespace std;

map<char, pair<char, char> > m;

void preorder(char idx){
    cout << idx;
    if(m[idx].first != '.'){
        preorder(m[idx].first);
    }
    if(m[idx].second != '.'){
        preorder(m[idx].second);
    }
}

void inorder(char idx){
    if(m[idx].first != '.'){
        inorder(m[idx].first);
    }
    cout << idx;
    if(m[idx].second != '.'){
        inorder(m[idx].second);
    }
}

void postorder(char idx){
    if(m[idx].first != '.'){
        postorder(m[idx].first);
    }
    if(m[idx].second != '.'){
        postorder(m[idx].second);
    }
    cout << idx;
}

int main(){

    ios::sync_with_stdio(false);
	cin.tie(NULL);
    cout.tie(NULL);

    int N; cin >> N;
    for(int i = 0; i < N; i++){
        char a, b, c; cin >> a >> b >> c;
        m.insert(make_pair(a, make_pair(b, c)));
    }
    preorder('A');
    cout << '\n';
    inorder('A');
    cout << '\n';
    postorder('A');
    return 0;
}




댓글

댓글 쓰기