트리의 순회
이 게시글에서 설명하는 트리의 순회는 이진트리를 기준으로 한다. 이진 트리에 대해 모른다면 다음 포스팅을 참고하자.
[자료구조] 트리(Tree)의 개념, 이해, 종류 | 이진 트리, 전 이진 트리, 완전 이진트리, 포화 이진
트리(Tree)의 개념 트리는 노드로 이루어진 자료구조로 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조이다. 트리는 계층적 관계를 표현하는 자료구조이다. 트리는 다음과 같은 특징들을
code-lab1.tistory.com
트리의 순회 중 중위(inorder) 순회, 전위(preorder) 순회, 후위 순회(postorder) 순회에 대해 알아보자.
여기서 설명할 때 L은 Left, V는 Visit, R은 Right를 의미한다. 즉 왼쪽 서브 트리, 노드 방문, 오른쪽 서브 트리를 의미한다.
중위 순회(inorder traversal)
중위 순회는 LVR 탐색이 이루어진다. 즉, 왼쪽 서브 트리-루트 노드-오른쪽 서브 트리 탐색이 재귀적으로 이루어진다. 아래 그림을 보면 이해가 빠를 것이다.
가장 먼저 루트 노드를 기준으로 왼쪽 서브 트리로의 탐색이 시작된다. 즉, 왼쪽 서브 트리에서 또다시 중위 순회가 재귀적으로 이루어진다.
B노드가 루트 노드인 것처럼 되고, 왼쪽 서브 트리인 A노드로의 중위 탐색이 진행된다. 이후 A노드는 왼쪽 서브 트리(Left)가 없으므로 해당 노드를 방문(Visit) 하게 된다.
출력 : A
B가 루트 노드인 것처럼 될 때 , 왼쪽 서브 트리의 탐색을 마쳤으니, 루트 노드인 B의 방문(Visit)이 진행된다.
출력 : A B
이후 B의 오른쪽 서브 트리로의 중위 탐색이 다시 진행된다. 이때는 D노드가 마치 루트 노드인 것처럼 된다.
D가 루트 노드일 때, 왼쪽 서브 트리인 C노드로의 중위 탐색이 진행된다. 이후 C노드는 왼쪽 서브 트리(Left)가 없으므로 해당 노드를 방문(Visit) 하게 된다.
출력 : A B C
이후 루트 노드인 D노드를 방문하게 된다.
출력 : A B C D
D 노드가 루트 노드 일 때 , 오른쪽 서브 트리인 E노드로의 중위 탐색이 진행되고, 왼쪽 서브 트리가 없으므로 바로 E노드를 방문한다.
출력 : A B C D E
F 노드가 루트 노드일 때 왼쪽 서브 트리의 탐색이 모두 완료되었으니, 루트 노드인 F를 방문한다.
출력 : A B C D E F
이후 오른쪽 서브 트리에서 중위 탐색이 진행된다. 이때 G노드가 루트 노드처럼 된다.
G노드가 루트노드 일 때, 왼쪽 서브 트리가 없으므로 루트 노드인 G노드를 방문한다.
출력 : A B C D E F G
이후 오른쪽 서브 트리로 다시 중위 탐색이 진행된다. 이때 I 노드가 루트 노드인 것처럼 된다.
이후 왼쪽 서브 트리인 H노드로의 중위 탐색이 진행되고 왼쪽 서브 트리가 없으므로 H노드를 방문하게 된다.
출력 : A B C D E F G H
이후 루트 노드인 I노드의 방문이 진행되고 탐색이 종료된다.
출력 : A B C D E F G H I
중위 순회 소스코드
|
1
2
3
4
5
|
void inorder(Node* root){ // 중위순회
inorder(root->left); // 왼쪽 서브트리
printf(root->data); // 루트노드 방문
inorder(root->right); // 오른쪽 서브트리
}
|
cs |
전위 순회(Preorder Traversal)
전위 순회는 VLR 탐색이 이루어진다. 즉, 루트 노드-왼쪽 서브 트리-오른쪽 서브 트리 순으로 탐색이 재귀적으로 진행된다.
중위 순회처럼 전위 순회도 재귀적으로 이루어진다는 것을 이해하면, 쉽게 이해할 수 있을 것이다.
순서대로 방문하는 것을 설명하자면,
1. 루트 노드인 F를 방문
2. F의 왼쪽 서브 트리의 루트 노드 B 방문
3. B의 왼쪽 서브 트리의 루트 노드 A 방문
4. B의 오른쪽 서브 트리의 루트 노드 D 방문
5. D의 왼쪽 서브 트리의 루트 노드 C 방문
6. D의 오른쪽 서브 트리의 루트 노드 E 방문
7. F의 오른쪽 서브 트리의 루트 노드 G 방문
8. G의 오른쪽 서브 트리의 루트 노드 I 방문
9. I의 왼쪽 서브 트리의 루트 노드 H 방문
출력 : F B A D C E G I H
전위 순회 소스코드
|
1
2
3
4
5
|
void preorder(Node* root){
printf(root->data); // 루트노드 방문
preorder(root->left); // 왼쪽 서브트리
preorder(root->right); // 오른쪽 서브트리
}
|
cs |
후위 순회(Postorder Traversal)
후위 순회는 LRV 탐색이 이루어진다. 즉 왼쪽 서브 트리-오른쪽 서브 트리-루트 노드 순으로 탐색이 재귀적으로 진행된다.
순서대로 방문하는 것을 설명하자면,
1. F의 왼쪽 서브트리 탐색
2. B의 왼쪽 서브트리 탐색
3. A노드 방문
4. B의 오른쪽 서브트리 탐색
5. D의 왼쪽 서브트리 탐색
6. C노드 방문
7. D의 오른쪽 서브트리 탐색
8. E노드 방문
9. D노드 방문
10. B노드 방문
11. F의 오른쪽 서브트리 탐색
12. G의 오른쪽 서브트리 탐색
13. I의 왼쪽 서브트리 탐색
14. H노드 방문
15. I노드 방문
16. G노드 방문
17. F노드 방문
출력 : A C E D B H I G F
후위 순회 소스코드
|
1
2
3
4
5
|
void postorder(Node* root){
postorder(root->left); // 왼쪽 서브트리
postorder(root->right); // 오른쪽 서브트리
printf(root->data); // 루트노드 방문
}
|
cs |
'Computer Science > [자료구조]' 카테고리의 다른 글
| [자료구조]Max Heap, Min Heap, Heap 이란? | C언어 Heap 구현 (0) | 2021.07.21 |
|---|---|
| [자료구조] 이진탐색트리(Binary Search Tree)의 개념, 이해 | C언어 이진탐색트리 구현 (4) | 2021.07.20 |
| [자료구조] 트리(Tree)의 개념, 이진 트리, 전 이진 트리, 완전 이진트리, 포화 이진 트리, 이진 탐색트리 (6) | 2021.07.16 |
| [자료구조] 큐(Queue)란? | c언어 큐 구현 (3) | 2021.07.15 |
| [자료구조] 스택(stack) 의 개념과 이해 | c언어 스택 구현 (0) | 2021.07.14 |