1. 트리 순회(Tree Traversal)의 개념
-
특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것을 트리 순회하고 한다.
-
트리 구조는 계층적 구조라는 특별한 특징을 가지기 때문에, 모든 노드를 순회하는 방법에는 크게 4가지가 있는데 DFS(Depth-First Search, 깊이 우선 탐색) 탐색 방법에 속하는 전위, 순회, 중위 순회, 후위 순회 3가지가 있고, BFS(Breadth-First Search, 너비 우선 탐색) 탐색 방법에 속하는
2. DFS(Depth-First Search) 탐색 방법
- 깊이를 우선적으로 탐색하는 방법을 Depth-First Search, 깊이 우선 탐색이라고 한다. 한 정점에서 시작해서 다음 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색할 때 사용하며, BFS보다 탐색 시간은 조금 오래 걸릴지라도 모든 노드를 완전히 탐색할 수 있다.
1) 전위 순회(preorder)
-
전위 순회에서 가장 먼저 방문하는 노드는 루트다. 루트에서 시작해 왼쪽의 노드들을 순차적으로 둘러본 뒤, 왼쪽의 노드 탐색이 끝나면 오른쪽 노드를 탐색을 한다.
-
즉, 부모 노드가 제일 먼저 방문되는 순회 방식으로, 전위 순회는 주로 부모 노드가 먼저 생성되어야 하는 트리를 복사할 때 사용하게 된다.
-
전위 순회는 깊이 우선 순회(DFS, Depth-First Search) 방법에 속한다.
전위 순회 과정 (root -> left -> right)
- 루트 노드를 방문한다.
- 왼쪽 서브트리를 전위 순회한다.
- 오른쪽 서브트리를 전위 순회한다.
- 아래 예시의 트리를 전위 순회로 돌 경우 출력값은 F -> B -> A -> D -> C -> E -> G -> I -> H의 순서로 출력된다.
2) 중위 순회(inorder)
-
중위 순회는 루트를 가운데에 두고 순회한다. 제일 왼쪽 끝에 있는 노드부터 순회하기 시작하여, 루트를 기준으로 왼쪽에 있는 노드의 순회가 끝나면 루트를 거쳐 오른쪽에 있는 노드로 이동하여 마저 탐색한다.
-
중간 노드들을 출력하지 않고 바로 제일 왼쪽 끝에 있는 리프노드로 내려가서 출력한 후, 오른쪽 노드가 있는 부모 노드까지 올라와서 부모 노드를 출력하고 다시 제일 왼쪽 끝에 있는 리프 노드로 내려간다.
-
부모 노드가 서브 트리의 방문 중간에 방문되는 순회 방식으로, 중위 순회는 이진 탐색 트리의 오름차순으로 값을 가져올 때 쓰인다.
-
중위 순회는 깊이 우선 순회(DFS, Depth-First Search) 방법에 속한다.
중위 순회 과정 (left -> root -> right)
- 왼쪽 서브 트리를 중위 순회한다.
- 루트 노드를 방문한다.
- 오른쪽 서브트리를 중위 순회한다.
- 아래 예시의 트리를 중위 순회로 돌 경우 출력값은 A -> B -> C -> D -> E -> F -> G -> H -> I의 순서로 출력된다.
3) 후위 순회(postorder)
-
후위 순회는 루트를 가장 마지막에 순회한다. 제일 왼쪽 끝에 있는 노드부터 순회하기 시작하여, 루트를 거치지 않고 오른쪽으로 이동해 순회한 뒤, 제일 마지막에 루트를 방문한다.
-
후위 순회는 트리를 삭제할 때 사용하며, 자식 노드가 먼저 삭제되어야 상위 노드를 삭제할 수 있기 때문이다.
-
후위 순회는 깊이 우선 순회(DFS, Depth-First Search) 방법에 속한다.
후위 순회 과정 (left -> right -> root)
- 왼쪽 서브 트리를 후위 순회한다.
- 오른쪽 서브 트리를 후위 순회한다.
- 루트 노드를 방문한다.
- 아래 예시의 트리를 후위 순회로 돌 경우 출력값은 A -> C -> E -> D -> B -> H -> I -> G -> F의 순서로 출력된다.
3. BFS(Breadth-First Search) 탐색 방법
- 너비를 우선적으로 탐색하는 방법을 Breadth-First Search, 너비 우선 탐색이라고 한다. 주로 두 정점 사이의 최단 경로를 찾을 때 사용하며, 만약 경로를 하나씩 전부 방문한다면, 최악의 경우에는 모든 경로를 다 살펴봐야 한다.
1) 레벨 순서 순회(levelorder)
-
레벨 순서 순회는 모든 노드를 낮은 레벨부터 차례대로 순회한다.
-
레벨 순서 순회는 너비 우선 순회(BFS, Breadth-First Search) 방법에 속한다.
레벨 순서 순회 과정 (Level 1 -> Level 2 -> ... -> Level N)
- 루트 노드를 방문한다.
- Level 1의 형제노드들을 제일 왼쪽의 노드부터 모두 출력한다.
- 각 레벨의 형제노드들을 모두 출력하는 과정을 마지막 레벨까지 진행한다.
- 아래 예시의 트리를 레벨 순서 순회로 돌 경우 출력값은 F -> B -> G -> A -> D -> I -> C -> E -> H의 순서로 출력된다.
