[알고리즘 부록] 트리를 순회하는 방법 3가지(프리오더, 인오더, 포스트오더)

트리의 순회 방법

트리를 순회하는 방법은 크게 3가지가 있다. 각각의 방법은 다음과 같다.

• 프리오더(preorder traversal) 또는 전위 순회: root -> 왼쪽 -> 오른쪽 순으로 순회하는 방식
• 인오더(inorder traversal) 또는 중위 순회: 왼쪽 -> root -> 오른쪽 순으로 순회하는 방식
• 포스트오더(postorder traversal) 또는 후위 순회 : 왼쪽 -> 오른쪽 -> root 순으로 순회하는 방식

그림으로 보면 다음과 같다.

동작방식

전위 순회(왼쪽), 중위 순회(가운데), 후위 순회(오른쪽)

 

전위 순회는 처음 마주친 노드를 방문한다는 점이 특징이며, 중위 순회는 왼쪽부터 오른쪽으로 차례대로 방문한다는 점이, 후위 순회는 루트 노드를 가장 늦게 방문한다는 점이 특징이다.

구현 코드

struct node{
    char left;
    char right;
};

map<char, node> tree;

// 프리오더(preorder traversal) 또는 전위 순회
void preorder(char parent){
    if(parent == '.'){
        return;
    }

    cout << parent;
    preorder(tree[parent].left);
    preorder(tree[parent].right);
}

// 인오더(inorder traversal) 또는 중위 순회
void inorder(char parent){

    if(parent == '.'){
        return;
    }
 
    inorder(tree[parent].left);
    cout << parent;
    inorder(tree[parent].right);
}

// 포스트오더(postorder traversal) 또는 후위 순회
void postorder(char parent){

    if(parent == '.'){
        return;
    }
 
    postorder(tree[parent].left);
    postorder(tree[parent].right);
    cout << parent;
}

 

 

참고자료

https://hongku.tistory.com/160