[C 자료구조 ] 트리의 순회(Traversal of Tree) - 전위 / 중위 / 후위
순회(Traversal) 란 트리의 노드들을 체계적으로 방문하는 것을 말합니다. 모든 노드들을 방문해야 하고 3가지의 기본적인 순회방법이 있습니다. 전위순회(preorder traversal, VLR), 중위 순회(inorder traver
songsite123.tistory.com
위 포스팅에서 재귀적으로 전위, 중위, 후위 순회를 구현해보았습니다. 오늘은 재귀함수 호출이 아닌 스택과 반복문을 사용해서 순회함수를 구현해보도록 하겠습니다. 순회의 과정이나 메커니즘은 똑같으니 위 포스팅을 먼저 보고 순회가 무엇인지 어떤 순서로 이루어지는지 먼저 이해하고 오시는 것을 추천드립니다.
스택을 이용한 트리 순회 코드
위 같은 형태의 그래프를 전위, 중위, 후위 순회를 통해 어떤 순서로 탐색을 진행하는지 확인해보겠습니다.
스택 및 트리 구현
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int data;
struct TreeNode* left, *right;
}TreeNode;
#define SIZE 100
int top = -1;
TreeNode* stack[SIZE];
void push(TreeNode* p)
{
if (top < SIZE - 1)
{
stack[++top] = p;
}
}
TreeNode* pop()
{
TreeNode* p = NULL;
if (top > -1)
p = stack[top--];
return p;
}먼저 트리 노드를 구성합니다. 왼쪽과 오른쪽 자식 노드를 가리킬 노드 포인터와 데이터를 가지는 구조체로 구성됩니다.
그리고 스택 구조체를 만들어도 되지만 그냥 전역변수로 top 변수와 배열 스택을 구현했습니다. 노드 포인터로 트리를 나타낼 것이기 때문에 스택에 들어가는 것이 노드 포인터가 되어야 합니다. 따라서 노드 포인터 배열을 전역변수로 선언하여 스택을 구현해줍니다.
스택에 필수적인 연산인 push 와 pop 은 동일합니다. 노드 포인터를 인자로 받아 stack 의 인덱스를 증가시키고 대입하면서 노드들을 저장하고 pop의 경우 노드 포인터를 반환해줘야하기 때문에 선언하고 NULL 포인터로 초기화하여 POP 할 데이터가 있으면 그 포인터를 반환하고 스택이 비어있는 경우 NULL 포인터를 반환하게 됩니다.
전위순회 (preorder)
void preorder_iter(TreeNode* root)
{
while (1) {
for (; root; root = root->left) {
printf("[%d] ", root->data); // 현재 노드 출력
push(root); // 현재 노드 스택에 push
}
root = pop();
if (!root) break; // 스택에 노드가 없으면 종료
root = root->right; // 오른쪽 자식 노드로 이동
}
}전위순회는 VLR 로 탐색이 진행됩니다. 루트 노드 -> 왼쪽 서브 트리 -> 오른쪽 서브 트리 순으로 탐색이 진행되는 것이죠.
while(1) 의 무한 루프문을 사용하고, 탐색이 끝나기 전까지는 무한 루프를 돕니다. 그러면 반복문 종료 조건은 모든 탐색이 완료되었을 때겠죠?
루트 노드를 인자로 입력받기 때문에 루트 노드부터 데이터를 출력한 이후, 루트 노드를 스택에 push 합니다. 그리고 for 문의 조건변화수식을 보면 root->left 인데 데이터를 출력하고, push 하고 왼쪽 서브트리로 내려가는 것을 반복하는 것이죠. 종료되는 시점은 NULL 포인터를 만날 때, 즉 더 이상 왼쪽 서브 트리가 없을 때까지 내려가면서 루트 노드를 모두 출력해줍니다.
왼쪽 서브 트리가 없을 때까지 내려갔다면 pop을 통해 다시 이전 루트 노드로 돌아갑니다. 그리고 오른쪽 서브 트리로 이동하면 while문의 반복이 1회 종료됩니다. 다시 오른쪽 서브 트리의 루트 노드부터 이 과정을 계속 반복하는 것이죠.
스택에 push 를 하기 전에 출력을 하기 때문에 스택에 노드가 없다는 것은 곧 모든 노드를 출력했다는 것과 같습니다. 따라서 while 문의 종료 조건은 pop 한 루트 포인터가 NULL 일 때 즉 스택의 모든 노드를 출력했을 때 while문이 종료됩니다.
중위순회 (inorder)
void inorder_iter(TreeNode* root)
{
while (1) {
// 루트 노드부터 왼쪽 자식 노드로 계속 push하며 내려간다. 왼쪽 NULL 도달할 때까지 반복
for (; root; root = root->left)
push(root);
root = pop(); // 왼쪽 아래에서 NULL에 도달하면 하나씩 pop
if (!root) break; // 스택에 노드가 없어서 pop이 안되고 최종적으로 NULL 값이 나오면 break;
printf("[%d] ", root->data); // 데이터 출력
root = root->right; // 데이터를 출력하고 오른쪽 자식 노드 탐색. NULL 이면 for문이 안돌고 바로 pop
}
}중위 순회도 전위 순회와 거의 비슷합니다. 중위 순회는 LVR 순으로 순회가 이루어집니다. 따라서 왼쪽 끝까지 내려가는 것이 우선이죠. 내려가면서 push를 하는데 출력을 아직 하지 않습니다.
for 문의 동작을 천천히 생각해보면 루트 노드를 입력으로 받아 루트 노드를 push 한 이후 왼쪽 서브 트리로 이동하면서 root 노드를 갱신합니다. 마지막 레벨의 노드에 도착한 상황을 가정하면 push(root) 까지는 일어날 것이고 그 이후 for문이 종료됩니다. 다시 마지막 노드를 pop 해서 꺼내어 root 노드에 저장하고 노드를 출력합니다. 그런데 마지막 노드를 출력한 거니까 당연히 오른쪽 서브트리는 NULL 값일 겁니다. 그리고 다시 while 문을 돌면 for 문을 스킵하고 곧 바로 pop 이 이루어집니다. LVR 에서 LV 까지 된것이죠. 그 이후에 오른쪽 서브트리 .. 무한 반복하다가 전위 순회와 마찬가지로 스택에 노드가 없어서 pop 이후 최종적으로 NULL 값이 if 문에 걸리면 반복문을 빠져나오게 됩니다.
후위순회 (postorder)
void postorder_iter(TreeNode* root)
{
TreeNode* p = NULL;
while (1) {
for (; root; root = root->left) { // 왼쪽 아래까지 이동
push(root);
}
while (1) {
root = pop();
if (!root) return; // 스택이 빈 경우 종료
if (!root->right || p == root->right) {
printf("[%d] ", root->data);
p = root;
}
else {
push(root);
root = root->right;
break;
}
}
}
}마지막으로 LRV로 탐색을 진행하는 후위순회 함수입니다. 후위 순회의 경우는 조금 더 복잡합니다.
먼저 L부터 탐색하기 위해 for 문을 통해 왼쪽 아래까지 push 하면서 내려갑니다. 왼쪽 끝까지 내려갔다면 다시 while 문을 통해 이중 while 문을 구성합니다. 이중 while 문 안에 return 함수 종료 조건을 넣어놓고 이는 전위 순회와 중위 순회와 동일하게 스택이 비어 pop 한 결과과 NULL 포인터인 경우 종료됩니다.
그 다음 조건문에서는 오른쪽 서브 트리가 null 포인터가 아니거나 p 포인터가 우측 포인터와 동일한 경우에 if 문이 실행됩니다. 맨 처음 저 조건문을 만나면 왼쪽 끝 노드일테니까 오른쪽 서브트리는 NULL 포인터지만, p 포인터가 null 이기 때문에 if 문 안의 print 문이 실행되어 왼쪽 맨 아래 노드를 출력해줍니다. 그 이후 p 를 출력한 노드로 설정합니다.
다시 pop 을 진행하면 왼쪽 맨 아래 노드의 부모 노드로 이동하게 됩니다. 그 상황에서 if 문을 만나면 오른쪽 노드가 NULL 포인터인 경우, 즉 오른쪽 서브 트리가 없는 경우에는 곧바로 그 노드를 출력하고, 그 경우가 아닌 오른쪽 서브 트리가 있는 경우라면 오른쪽이 NULL 포인터가 아니면서, 우측 서브트리 포인터와 p(루트노드) 는 같지 않기 때문에 else 문으로 이동하여 루트 노드를 스택에 넣고, 루트 노드를 오른쪽 서브 트리로 변경합니다.
즉 정리하면 if 문의 (!root->right || p == root->right) 라는 조건은 우측 서브 트리가 없는 경우 수행 되는 조건입니다.
우측 서브 트리가 없는 경우 else 문으로 이동하게 되며, 자기 자신을 스택에 push 하고 오른쪽 서브트리로 내려가는 것이죠. 이 과정을 반복하여 LRV 탐색을 하다 모든 탐색이 끝난 경우, 즉 스택이 비어서 POP 한 결과가 NULL 인 경우 함수가 종료됩니다.
전체 코드 및 실행 결과
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int data;
struct TreeNode* left, *right;
}TreeNode;
#define SIZE 100
int top = -1;
TreeNode* stack[SIZE];
void push(TreeNode* p)
{
if (top < SIZE - 1)
{
stack[++top] = p;
}
}
TreeNode* pop()
{
TreeNode* p = NULL;
if (top > -1)
p = stack[top--];
return p;
}
void preorder_iter(TreeNode* root)
{
while (1) {
for (; root; root = root->left) {
printf("[%d] ", root->data); // 현재 노드 출력
push(root); // 현재 노드 스택에 push
}
root = pop();
if (!root) break; // 스택에 노드가 없으면 종료
root = root->right; // 오른쪽 자식 노드로 이동
}
}
void inorder_iter(TreeNode* root)
{
while (1) {
// 루트 노드부터 왼쪽 자식 노드로 계속 push하며 내려간다. 왼쪽 NULL 도달할 때까지 반복
for (; root; root = root->left)
push(root);
root = pop(); // 왼쪽 아래에서 NULL에 도달하면 하나씩 pop
if (!root) break; // 스택에 노드가 없어서 pop이 안되고 최종적으로 NULL 값이 나오면 break;
printf("[%d] ", root->data); // 데이터 출력
root = root->right; // 데이터를 출력하고 오른쪽 자식 노드 탐색. NULL 이면 for문이 안돌고 바로 pop
}
}
void postorder_iter(TreeNode* root)
{
TreeNode* p = NULL;
while (1) {
for (; root; root = root->left) { // 왼쪽 아래까지 이동
push(root);
}
while (1) {
root = pop();
if (!root) return; // 스택이 빈 경우 종료
if (!root->right || p == root->right) {
printf("[%d] ", root->data);
p = root;
}
else {
push(root);
root = root->right;
break;
}
}
}
}
TreeNode n1 = { 1, NULL, NULL };
TreeNode n2 = { 4, &n1, NULL };
TreeNode n3 = { 16, NULL, NULL };
TreeNode n4 = { 25, NULL, NULL };
TreeNode n5 = { 20, &n3, &n4 };
TreeNode n6 = { 15, &n2, &n5 };
TreeNode* root = &n6;
int main(void)
{
printf("전위 순회 : ");
preorder_iter(root);
printf("\n중위 순회 : ");
inorder_iter(root);
printf("\n후위 순회 : ");
postorder_iter(root);
return 0;
}
결과를 확인하면 전위, 중위, 후위 순회가 제대로 이루어졌음을 확인할 수 있습니다. 잘 이해가 안 가는 부분은 댓글로 남겨주세요. 감사합니다.
'C 자료구조' 카테고리의 다른 글
| [C 자료구조] 힙(Heap) - Max/Min heap (1) | 2023.05.27 |
|---|---|
| [C 자료구조] 이진 탐색 트리 (Binary Search Tree) (0) | 2023.05.25 |
| [C 자료구조 ] 트리의 순회(Traversal of Tree) - 전위 / 중위 / 후위 (1) | 2023.05.25 |
| [C 자료구조] 트리(Tree) 의 종류 (0) | 2023.05.25 |
| [C 자료구조] 그래프 ADT 구현 : 인접행렬 / 인접리스트 (2) | 2023.05.25 |