[Algorithm] 트리순회 (Tree Traversal)

1. 트리순회(Tree Traversal)란?

트리 순회(Tree traversal)는 트리 구조에서 각각의 노드를 정확히 한 번만, 체계적인 방법으로 방문하는 과정을 말합니다.
트리 순회는 노드를 방문하는 순서에 따라 후위순회, 전위순회, 중위순회, 레벨순회로 구분해 볼 수 있습니다.
(보통 설명할 때는 이진트리를 기반으로 설명하지만 다른 모든 트리에서 일반화를 시킬 수 있습니다)

1. 후위순회(Postorder Traversal)

후위순회(postorder traversal)는 자식들 노드를 먼저 방문하고 자신의 노드를 방문하는 것을 말합니다.
post : ~이후의를 뜻하는 접두사

[수도코드]

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

방문한다? = visited 배열을을 체크하는 것으로 생각해주세요.

2. 전위순회 (Preorder Traversal)

전위순회(preorder traversal)는 먼저 자신의 노드를 방문하고 그 다음 노드들을 방문하는 것을 말합니다. 전위순회는 깊이 우선 탐색(DFS)의 탐색 방법입니다.
pre : ~이전의를 뜻하는 접두사

[수도코드]

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

3. 중위순회 (Inorder Traversal)

중위순회(inorder traversal)는 왼쪽 노드를 먼저 방문하고, 그 다음 자신의 노드를 방문한 후, 오른쪽 노드를 방문하는 순서를 말합니다.
in: 안에 넣다.

[수도코드]

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

4. 레벨순회 (Level-order Traversal)

레벨순회(level-order traversal)는 트리의 깊이(depth)에 따라 같은 레벨(level)에 있는 노드들을 차례대로 방문하는 방법입니다.
즉, 루트에서 시작하여 각 레벨의 노드를 좌에서 우로 방문합니다. 레벨 순회는 너비 우선 탐색(BFS)의 탐색 방법과 동일합니다.

이 방법은 주로 큐(queue)를 사용하여 구현됩니다. 현재 노드를 큐에 넣고, 그 다음 노드를 큐에서 꺼내어 자식 노드들을 다시 큐에 추가하는 방식으로 진행됩니다.

[수도코드]

level_order( root )
    큐 queue 를 초기화한다.
    queue.push( root )
    
    while queue is not empty:
        node = queue.pop()
        node.visited = true
        
        if node.left exists:
            queue.push( node.left )
        
        if node.right exists:
            queue.push( node.right )

---

2. 트리순회 (1~3) 코드 구현

C++

#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 << "\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;
}
/*
 트리순회 : postOrder
4 5 2 3 1
 트리순회 : preOrder
1 2 4 5 3
 트리순회 : inOrder
4 2 5 1 3
*/

Python

class Tree:
    def __init__(self):
        self.adj = [[] for _ in range(1004)]
        self.visited = [0] * 1004

    def post_order(self, here):
        if self.visited[here] == 0:
            if len(self.adj[here]) == 1:
                self.post_order(self.adj[here][0])
            elif len(self.adj[here]) == 2:
                self.post_order(self.adj[here][0])
                self.post_order(self.adj[here][1])
            self.visited[here] = 1
            print(here, end=' ')

    def pre_order(self, here):
        if self.visited[here] == 0:
            self.visited[here] = 1
            print(here, end=' ')
            if len(self.adj[here]) == 1:
                self.pre_order(self.adj[here][0])
            elif len(self.adj[here]) == 2:
                self.pre_order(self.adj[here][0])
                self.pre_order(self.adj[here][1])

    def in_order(self, here):
        if self.visited[here] == 0:
            if len(self.adj[here]) == 1:
                self.in_order(self.adj[here][0])
                self.visited[here] = 1
                print(here, end=' ')
            elif len(self.adj[here]) == 2:
                self.in_order(self.adj[here][0])
                self.visited[here] = 1
                print(here, end=' ')
                self.in_order(self.adj[here][1])
            else:
                self.visited[here] = 1
                print(here, end=' ')

    def reset_visited(self):
        self.visited = [0] * 1004


if __name__ == "__main__":
    tree = Tree()
    tree.adj[1].extend([2, 3])
    tree.adj[2].extend([4, 5])

    root = 1
    print("\n트리순회 : postOrder")
    tree.post_order(root)
    tree.reset_visited()

    print("\n트리순회 : preOrder")
    tree.pre_order(root)
    tree.reset_visited()

    print("\n트리순회 : inOrder")
    tree.in_order(root)