이진탐색트리 순회 개념

 

이진탐색트리 순회 종류

•  중위(inorder) 순회
• 전위(preorder) 순회
• 후위(postorder) 순회 

 

여기서 설명할 때 L은 Left, V는 Visit, R은 Right를 의미한다. 즉 왼쪽 서브 트리, 노드 방문, 오른쪽 서브 트리를 의미한다.

 

중위 순회(inorder traversal)

중위 순회는 LVR 탐색이 이루어진다.

즉, 왼쪽 서브 트리-루트 노드-오른쪽 서브 트리 탐색이 재귀적으로 이루어진다. 아래 그림을 보면 이해가 빠를 것이다.

 

중위순회 과정1

 

가장 먼저 루트 노드를 기준으로 왼쪽 서브 트리로의 탐색이 시작된다. 즉, 왼쪽 서브 트리에서 또다시 중위 순회가 재귀적으로 이루어진다. 

 

중위순회 과정2

 

B노드가 루트 노드인 것처럼 되고, 왼쪽 서브 트리인 A노드로의 중위 탐색이 진행된다. 이후 A노드는 왼쪽 서브 트리(Left)가 없으므로 해당 노드를 방문(Visit) 하게 된다. 

 

출력 : A

 

중위순회 과정3

 

B가 루트 노드인 것처럼 될 때 , 왼쪽 서브 트리의 탐색을 마쳤으니, 루트 노드인 B의 방문(Visit)이 진행된다.

 

출력 : A B

중위순회 과정4

 

이후 B의 오른쪽 서브 트리로의 중위 탐색이 다시 진행된다. 이때는 D노드가 마치 루트 노드인 것처럼 된다.

 

중위순회 과정5

 

D가 루트 노드일 때, 왼쪽 서브 트리인 C노드로의 중위 탐색이 진행된다. 이후 C노드는 왼쪽 서브 트리(Left)가 없으므로 해당 노드를 방문(Visit) 하게 된다. 

 

출력 : A B C

 

중위순회 과정6

 

이후 루트 노드인 D노드를 방문하게 된다.

 

출력 : A B C D

 

중위순회 과정7

 

D 노드가 루트 노드 일 때 , 오른쪽 서브 트리인 E노드로의 중위 탐색이 진행되고, 왼쪽 서브 트리가 없으므로 바로 E노드를 방문한다.

 

출력 : A B C D E

 

중위순회 과정8

 

F 노드가 루트 노드일 때 왼쪽 서브 트리의 탐색이 모두 완료되었으니, 루트 노드인 F를 방문한다.

 

출력 : A B C D E F

 

중위순회 과정9

 

이후 오른쪽 서브 트리에서 중위 탐색이 진행된다. 이때 G노드가 루트 노드처럼 된다.

중위순회 과정10

 

G노드가 루트노드 일 때, 왼쪽 서브 트리가 없으므로 루트 노드인 G노드를 방문한다.

 

출력 : A B C D E F G

 

중위순회 과정11

 

이후 오른쪽 서브 트리로 다시 중위 탐색이 진행된다. 이때 I 노드가 루트 노드인 것처럼 된다.

 

중위순회 과정12

 

이후 왼쪽 서브 트리인 H노드로의 중위 탐색이 진행되고 왼쪽 서브 트리가 없으므로 H노드를 방문하게 된다.

 

출력 : A B C D E F G H

 

중위순회 과정13

 

 

이후 루트 노드인 I노드의 방문이 진행되고 탐색이 종료된다.

 

출력 : A B C D E F G H I

 

코드상의 중위 순회

void inorder(Node* root){ // 중위순회
   inorder(root->left);    // 왼쪽 서브트리
    printf(root->data);    // 루트노드 방문
   inorder(root->right);    // 오른쪽 서브트리
}

 

전위 순회(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

 

코드상의 중위 순회

void preorder(Node* root){
    printf(root->data);    // 루트노드 방문
    preorder(root->left);    // 왼쪽 서브트리
    preorder(root->right);    // 오른쪽 서브트리
}

 

후위 순회(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

 

코드상의 후위 순회

void postorder(Node* root){
    postorder(root->left);    // 왼쪽 서브트리
    postorder(root->right);    // 오른쪽 서브트리
    printf(root->data);    // 루트노드 방문
}

 

---

 

요약

 

• 전위

• 중위

 

• 후위

 

 

---

참조

https://code-lab1.tistory.com/9

[자료구조] 트리의 순회, 중위 순회, 전위 순회, 후위 순회 | C언어 트리 순회 구현

https://www.crocus.co.kr/348

이진 트리 순회(Traversal) (1)