트리 순회(Tree traversal) - 후위, 전위, 중위

트리 구조에서 각각의 노드를 정확히 한 번만, 체계적이 방법으로 방문하는 과정을 트리 순회라고 합니다.

일단 설명을 위해, 공통적으로 사용할 하나의 예시 그림을 제시하겠습니다.

 

 

후위 순회 (postorder traversal)

자식 노드들을 먼저 방문하고, 본인 노드를 방문하는 방식입니다. (자식 노드들은 보통 왼쪽 -> 오른쪽 순서)

//pseudo code
postorder( node )
    if (node.visited == false)
        postorder( node->left )
        postorder( node->right )
        node.visited = true

 

 직접 코드로 구현해보겠습니다. 

void postOrder(int here){
    if(visited[here] == 0){
        if(adj[here].size() == 1) postOrder(adj[here][0]);
        if(adj[here].size() == 2){
            postOrder(adj[here][0]);
            postOrder(adj[here][1]);
        }
        visited[here] = 1;
        cout << here << ' ';
    }
}

 

전위 순회 (preorder traversal)

본인 노드를 먼저 방문하고, 자식 노드들을 방문하는 방식입니다. (DFS의 방식입니다) 

preorder( node )
    if (node.visited == false)
        node.visited = true
        preorder( node->left )
        preorder( node->right )

 

직접 코드로 구현해보겠습니다.

void preOrder(int here){
    if(visited[here] == 0){
        visited[here] = 1;
        cout << here << ' ';
        if(adj[here].size() == 1) preOrder(adj[here][0]);
        if(adj[here].size() == 2){
            preOrder(adj[here][0]);
            preOrder(adj[here][1]);
        }
    }
}

 

중위 순회 (inorder traversal)

왼쪽 자식 노드 → 본인 노드 →  오른쪽 자신 노드 순서대로 방문하는 방식입니다.

inorder( node )
    if (node.visited == false)
        inorder( node->left )
        node.visited = true
        inorder( node->right )

 

직접 코드로 구현해보겠습니다. 

void inOrder(int here){
    if(visited[here] == 0){
        if(adj[here].size() == 1){
            inOrder(adj[here][0]);
            visited[here] = 1;
            cout << here << ' ';
        }else if(adj[here].size() == 2){
            inOrder(adj[here][0]);
            visited[here] = 1;
            cout << here << ' ';
            inOrder(adj[here][1]);
        }else{
            visited[here] = 1;
            cout << here << ' ';
        }
    }
}

 

 

---

 

main에서 위의 3가지 함수들은 다음과 같이 활용하면 됩니다.

#include <bits/stdc++.h>
using namespace std;
vector<int> adj[1004];
int visited[1004];

int main(){
    adj[1].push_back(2);
    adj[1].push_back(3);
    adj[2].push_back(4);
    adj[2].push_back(5);
    int root = 1;
    cout << "\n 트리순회 : postOrder \n";
    postOrder(root); memset(visited, 0, sizeof(visited));
    cout << "\n 트리순회 : preOrder \n";
    preOrder(root); memset(visited, 0, sizeof(visited));
    cout << "\n 트리순회 : inOrder \n";
    inOrder(root);
    return 0;
}

 

사실 아까 트리 순회 함수들을 구현할 때 visited 배열은 왜 필요한지 의문이 들었을 수 있습니다.

이번에 제시된 그래프의 경우 단방향 간선이라 visited 배열이 무의미하긴 하지만, 평소에는 자주 쓰이기도 해서

수도코드에 넣어뒀고, 이에 따라 visited 배열도 구현해놓은 것이니 참고부탁드립니다.

 

---

여기까지 하면서, 트리 순회 방식들(3가지)와 DFS, BFS에 대해 배웠는데 이를 그림으로 표현하면 다음과 같습니다.

 

참고로, 숫자는 방문한 순서를 의미합니다!