[C 자료구조 ] 트리의 순회(Traversal of Tree) - 전위 / 중위 / 후위

순회(Traversal) 란 트리의 노드들을 체계적으로 방문하는 것을 말합니다. 모든 노드들을 방문해야 하고 3가지의 기본적인 순회방법이 있습니다. 전위순회(preorder traversal, VLR), 중위 순회(inorder traversal, LVR), 후위순회(postorder traversal, LRV) 입니다.

 

가장 먼저 중위순회에 대해 자세하게 단계별로 이해하고, 전위 순회와 후위 순회와의 차이점에 대해 알아보겠습니다.

밑의 포스팅에서 L, V, R 이라는 약자가 많이 나올텐데 L은 Left 의 약자로 왼쪽 서브 트리, V 는 Visit, R은 Right의 약자로 오른쪽 서브 트리를 의미합니다.

 

 중위 순회 (inorder traversal)

 

 

중위순회는 LVR 탐색이 이루어집니다. 왼쪽 서브 트리 - 루트 노드 - 오른쪽 서브 트리 순으로 탐색이 재귀적으로 이루어지는 것을 말합니다. 실제로 중위 순회 코드를 짜면 3줄이면 끝나는 간단한 코드입니다. 그림을 보면서 중위 순회 탐색을 이해해봅시다.

 

먼저 루트 노드를 기준으로 왼쪽 서브 트리의 탐색이 시작됩니다. 그럼 B가 루트 노드인 셈이죠? 여기서 또 다시 중위 순회가 재귀적으로 이루어집니다.

B 노드에서 다시 중위순회 함수가 호출되면 왼쪽 서브 트리인 A로 이동합니다. 그 이후 A 노드에서 다시 한 번 중위 순회 함수가 호출될텐데 이 때 A 는 자식 노드가 없으므로 더 이상 이동할 노드가 없습니다. 그런 경우에 해당 노드를 방문(Visit) 하고 함수를 종료합니다. Visit 한 노드를 순서대로 출력한다고 생각해보면 현재 A가 출력된 상황입니다.

 

출력 : A

함수가 종료된다면 이전에 재귀적으로 함수를 호출한 B 노드로 돌아가게 될겁니다. LVR 순서이므로 왼쪽은 이미 탐색을 하고 왔으니 루트 노드인 B의 방문(Visit) 이 진행됩니다.

 

출력 : A B 

 

이 후 B의 오른쪽 서브트리로 중위 탐색이 다시 진행됩니다. 이 때는 D가 루트 노드가 됩니다.

 

동일한 과정으로 왼쪽 서브트리 탐색, C는 왼쪽 자식 노드가 없으므로 방문이 진행됩니다.

 

출력 : A B C

이후 루트 노드인 D는 왼쪽 서브트리를 이미 방문했으므로 D를 방문합니다.

 

출력 : A B C D

 

D 노드가 루트 노드일 때 왼쪽 서브트리는 이미 탐색했고, 루트 노드인 D 도 방문했으므로 오른쪽 서브트리로 탐색이 진행되고 E 또한 왼쪽 자식 노드가 없으므로 E의 방문(Visit) 이 진행됩니다.

 

출력 : A B C D E

 

이후 F 노드로 돌아가서 왼쪽 서브트리가 모두 탐색되었으니 F를 Visit 하고 오른쪽 서브트리로 탐색을 시작합니다.

 

출력 : A B C D E F

 

 

 

G는 왼쪽 자식 노드가 없으므로 바로 Visit 이 진행되고 방문 이후 I로 중위 탐색이 진행됩니다.

 

출력 : A B C D E F G

 

 

I는 왼쪽 자식 노드가 있으므로 I보다 H를 먼저 방문하고, H는 왼쪽 자식 노드가 없으므로 방문, 그 이후 I로 돌아와서 I까지 방문하면서 전체 트리의 순회를 마칩니다.

 

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

 

전체 과정을 다시 한번 요약해보면 아래와 같습니다.

F -> 왼쪽 서브트리 방문 -> 왼쪽 서브트리 방문 -> A Visit -> B Visit

B에서 오른쪽 서브트리 탐색 -> D 에서 왼쪽 서브트리 탐색 -> C Visit -> D visit

D에서 오른쪽 서브트리 탐색 -> E Visit -> F로 돌아와서 F Visit -> 오른쪽 탐색 진행

G는 왼쪽 서브트리가 없으므로 바로 G Visit -> 오른쪽 서브트리 탐색 진행 -> I는 왼쪽 자식 노드가 있으므로 H 먼저 Visit -> I Visit

위 과정의 코드는 3줄이면 짤 수 있다고 했습니다. 중위 순회의 소스 코드는 다음과 같습니다.

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

 

 전위 순회 (preorder traversal)

 

전위 순회는 VLR 탐색이 이루어집니다. 루트 노드-왼쪽 서브트리-오른쪽 서브 트리 순으로 탐색이 재귀적으로 진행됩니다. 중위 순회와 동일한 재귀 탐색이 진행되기 때문에 출력을 보고 단계별로 이해하면 쉽습니다.

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

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

 

 후위 순회 (postorder traversal)

 

후위 순회는 LRV 순으로 탐색이 이루어집니다. 왼쪽 서브 트리 - 오른쪽 서브 트리 - 루트 노드 순으로 탐색이 재귀적으로 진행됩니다.

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

void postorder(Node* root){
	postorder(root->left);
    postorder(root->right);
    printf("%d ", root->data);
}

---

재귀적으로 중위, 전위, 후위 순회를 구현하면 코드가 매우 직관적이며 짜기도 쉽습니다. 그러나 재귀적으로 함수를 호출하는 것은 무거운 프로그램입니다. 따라서 스택을 사용하여 반복문만으로도 순회 함수를 구현할 수 있고 트리를 순회할 때 그 방법을 쓰는 것이 더 효율적입니다. 다음 포스팅에서 스택으로 전위, 중위, 후위 순회를 구현해보도록 하겠습니다. 감사합니다.

 

 

참고 및 출처 :

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