트리(Tree) 전위, 중위, 후위 순회 with C언어

트리의 순회 중

중위(inorder), 전위(preorder), 후위(postoder) 순회에 대해 알아보자.

 

여기서 설명할 때의 L은 LEFT, V는 VISIT, R은 RIGHT를 의미한다.

즉, 왼쪽 서브 트리, 노드 방문, 오른쪽 서브 트리를 의미한다.

 

중위 순회(inorder traversal)

중위 순회

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

즉, 왼쪽-방문-오른쪽 탐색이 재귀적으로 이루어진다.

중위순회 과정1

가장 먼저 루트 노드를 기준으로 왼쪽 서브트리로의 탐색이 시작된다.

즉, 왼쪽 서브 트리에서 또다시 중위 순회가 재귀적으로 이루어진다.

 

중위순회 과정2

B노드가 루트 노드인 것처럼 되고, 왼쪽 서브 트리인 A노드로의 중위 탐색이 진행된다.

이후 A노드는 왼쪽 서브트리가 없으므로 해당 노드를 방문(V)하게 된다.

 

출력: A

중위순회 과정3

B가 루트 노드인 것 처럼 될 때, 왼쪽 서브트리의 탐색을 마쳤으니

루트 노드인 B의 방문이 진행된다.

 

출력 : A B

 

중위순회 과정4

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

중위순회 과정5

D가 루트 노트일 때, 왼쪽 서브트리인 C노드로의 중위 탐색이 진행된다. 이후 C노드는 왼쪽

서브 트리가 없으므로 해당 노드를 방문하게 된다.

 

출력 : 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);    // 오른쪽 서브트리
}


출처: https://code-lab1.tistory.com/9?category=1213002 [code_lab]

 

---

전위 순회(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);    // 오른쪽 서브트리
}


출처: https://code-lab1.tistory.com/9?category=1213002 [code_lab]

---

 

후위 순회(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?category=1213002 [code_lab]

출처: https://code-lab1.tistory.com/9?category=1213002 [code_lab]