이진 트리 순회: 전위, 중위, 후위, 레벨
이진 트리(Binary Tree)를 탐색하는 방법에는 크게 다음의 4가지가 있다.
- 전위순회(Preorder Traversal)
- 중위순회(Inorder Traversal)
- 후위순회(Postorder Traversal)
- 레벨순회(Levelorder Traversal) 또는 BFS(Breadth-First Search; 너비 우선 탐색)
레벨순회(;BFS)를 제외한 나머지 순회방식은 DFS(Depth-First Search; 깊이 우선 탐색)으로 분류할 수 있다.
전위순회(preorder traversal)
전위순회는 루트 노드를 먼저 탐색하고, 자식 노드를 탐색하는 방식이다.
![](https://www.jiwon.me/content/images/2021/11/preorder.png)
void preorder(Node* root) {
if (root == nullptr) return;
cout << root->data << " ";
preorder(root->left);
preorder(root->right);
}
중위순회(inorder traversal)
중위순회는 왼쪽 자식 노드를 탐색하고, 루트 노드를 탐색하고, 오른쪽 자식 노드를 탐색하는 방식이다.
![](https://www.jiwon.me/content/images/2021/11/inorder.png)
void inorder(Node* root) {
if (root == nullptr) return;
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}
후위순회(postorder traversal)
후위순회는 왼쪽 자식 노드를 탐색하고, 오른쪽 자식 노드를 탐색하고, 루트 노드를 탐색하는 방식이다.
![](https://www.jiwon.me/content/images/2021/11/postorder.png)
void postorder(Node* root) {
if (root == nullptr) return;
postorder(root->left);
postorder(root->right);
cout << root->data << " ";
}
레벨순회(levelorder traversal; BFS)
레벨순회는 루트 노드를 먼저 탐색하고, 그 다음 레벨의 노드를 탐색하는 방식이다. queue를 하나 선언해두고, 루트 노드를 넣어준 다음, queue에 넣어준 노드를 하나씩 탐색하면서 자식 노드를 queue에 넣는다. queue가 비어있을 때까지 반복한다.
![](https://www.jiwon.me/content/images/2021/11/levelorder.png)
void levelorder(Node* root) {
if (root == nullptr) return;
queue<Node*> q;
q.enqueue(root);
while (!q.isEmpty()) {
Node* cur = q.dequeue()
cout << cur->data << " ";
if (cur->left != nullptr) q.enqueue(cur->left);
if (cur->right != nullptr) q.enqueue(cur->right);
}
}
레벨순회의 작동 방식
다른 순회 방식은 재귀로 쉽게 구현이 가능하지만, 레벨 순회(;BFS)는 재귀가 아닌 다른 방식으로 구현해야 한다. 일반적으로 Queue를 사용하는데, 예시를 보며 작동 방식을 익혀보자.
A를 루트로 하는 트리가 있으면, A를 queue에 집어 넣는다.
![](https://www.jiwon.me/content/images/2021/11/levelorder_explain_01.png)
queue의 가장 앞에 있는 A를 탐색하고, A의 자식 노드 B, C를 queue에 집어 넣는다.
![](https://www.jiwon.me/content/images/2021/11/levelorder_explain_02.png)
queue의 가장 앞에 있는 B를 탐색하고, B의 자식 노드 D, E를 queue에 집어 넣는다.
![](https://www.jiwon.me/content/images/2021/11/levelorder_explain_03.png)
queue의 가장 앞에 있는 C를 탐색하고, C는 자식 노드가 없으므로 다음으로 넘어간다.
![](https://www.jiwon.me/content/images/2021/11/levelorder_explain_04.png)
queue의 가장 앞에 있는 D를 탐색하고, D는 자식 노드가 없으므로 다음으로 넘어간다.
![](https://www.jiwon.me/content/images/2021/11/levelorder_explain_05.png)
queue의 가장 앞에 있는 E를 탐색하고, E의 자식 노드 F, G를 queue에 집어 넣는다.
![](https://www.jiwon.me/content/images/2021/11/levelorder_explain_06.png)
queue의 가장 앞에 있는 F를 탐색하고, F는 자식 노드가 없으므로 다음으로 넘어간다.
![](https://www.jiwon.me/content/images/2021/11/levelorder_explain_07.png)
queue의 가장 앞에 있는 G를 탐색하고, G는 자식 노드가 없으므로 다음으로 넘어간다.
![](https://www.jiwon.me/content/images/2021/11/levelorder_explain_08.png)
queue가 비었으므로 탐색을 종료한다.
이렇게 탐색을 완료하면 A, B, C, D, E, F, G 순으로 방문하게 된다.