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

https://blog.naver.com/jhc9639/222289089015

[알고리즘 강의] 2주차. 그래프이론, 인접행렬, 인접리스트, DFS, BFS, 트리순회

트리 순회(Tree traversal)은 트리 구조에서 각각의 노드를 정확히 한 번만 체계적으로 방문하는 과정

노드를 방문하는 순서에 따라

• 후위 순회 (postorder traversal)
• 전위 순회 ()
• 중위 순회 ()

보통 설명할 때 이진트리 기반으로 설명하지만 다른 모든 트리에서 일반화시킬 수 있다.

*이진트리(binary tree) : 각각의 노드와 자식 노드 수가 2개 이하로 구성되어 있는 트리

---

후위 순회 (postorder traversal)

*post : ~이후

 

자식들 노드를 먼저 방문하고 자신의 노드를 방문하는 것

 

PSEUDO CODE

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

 

---

전위 순회 (preorder traversal)

*pre : ~이전

 

먼저 자신의 노드를 방문하고 그 다음 노드들을  방문하는 것. DFS를 생각하면 됌.

 

PSEUDO CODE

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

 

---

중위 순회(indorder traversal)

왼쪽 노드를  먼저 방문, 그 다음 자신의 노드를 방문하고 그 다음 오른쪽 노드를 방문

 

PSEUDO CODE

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

---

레벨 순회(level traversal)

 

BFS 생각하면 된다.

---

CODE

#include <bits/stdc++.h>
using namespace std;

vector<int> adj[1004];
int visited[1004];

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 << ' ';
    }
}

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]);
        }
    }
}

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 << ' ';
        }
    }
}

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 << "트리순회 : postOrder\n";
    postOrder(root); memset(visited, 0, sizeof(visited));

    cout << "\n트리순회 : preOrder\n";
    preOrder(root); memset(visited, 0, sizeof(visited));

    cout << "\n트리순회 : inOrder\n";
    postOrder(root); memset(visited, 0, sizeof(visited));
}