.png)
안녕하세요. 김용성입니다.
오늘은 이진 트리의 순회에 대해서 알아보고, 코드로 구현해보는 시간을 가져보도록 하겠습니다.
순회란?
순회한다는 것은 이진트리에 속하는 모든 노드를 한 번씩 방문하여 노드가 가지고 있는 데이터를 목적에 맞게 처리하는 것을 의미합니다. 우리가 트리를 사용하는 목적은 트리의 노드에 자료를 저장하고 필요에 따라서 이 자료를 처리하기 위함인데요. 그렇기 때문에 트리에서 순회는 중요한 연산이라고 할 수 있습니다.
스택, 큐 등의 선형 자료형에서는 순차적으로 순회하는 방법이 한가지였지만, 트리에서는 구조 특성상 순회 방법이 여러가지로 나뉘어지죠. 여러가지 순서로 노드가 가지고 있는 자료에 접근할 수 있다는 장점이 있습니다.
순회 방법
이진트리를 순회하는 표준적인 방법으로는 전위, 중위, 후위의 3가지 방법이 있습니다. 이는 루트와 왼쪽 서브트리, 오른쪽 서브트리 중에서 루트를 언제 방문하느냐에 따라 구분되는데요. 만약 루트를 방문하는 작업을 V라고 하고 왼쪽서브트리 방문을 L. 오른쪽 서브트리 방문을 R이라고 하면 다음과 같이 3가지 방법을 생각할 수 있습니다.
- V->L->R (전위 순회)
- L->V->R (중위 순회)
- L->R->V (후위 순회)
각각의 서브트리 또한 이진트리임을 제가 앞선 포스팅에서 말씀드렸는데요. 따라서 서브트리에서도 이러한 순회방식은 그대로 적용됩니다. 하나하나 살펴보도록 하겠습니다.
전위 순회
전위 순회는 루트를 먼저 방문한 뒤 완쪽 서브트리를 방문하고 오른쪽 서브트리를 마지막으로 방문하는 것을 말합니다.
.png)
루트가 1번, 왼쪽 서브트리 2번, 오른쪽 서브트리 3번 순서로 방문합니다.
전위 순회 알고리즘(preorder)
preorder(x):
if x=!NULL // 노드 x가 NULL일 경우 순환 호출을 진행하지 않음
then print DATA(x); // x의 데이터 출력
preorder(LEFT(x)); // x의 왼쪽 서브트리 순환호출 방문
preorder(RIGHT(x)); // x의 오른쪽 서브트리 순환호출 방문알고리즘은 위와 같이 정의되는데요. 주석과 함께 살펴보시면 간단한 순환 알고리즘임을 이해하실 수 있으실 거라 생각합니다. 서브트리에서도 해당 트리의 서브트리로 위와 같은 순환이 일어나신다고 보시면 됩니다.
중위 순회
중위 순회 알고리즘 또한 전위 순회와 매우 유사합니다. (사실 3가지 순회 모두 똑같은 순환함수를 사용하죠.) 순서에 대해서 그림으로 표현하도록 하겠습니다. 왼쪽 서브트리를 방문한 뒤에 루트노드를 반문하고, 그 뒤에 오른쪽 서브트리를 방문하죠.
.png)
왼쪽 서브트리를 방문한 뒤 루트를 방문합니다. 그 이후에 오른쪽을 방문하는 것을 확인하실 수 있습니다.
중위 순회 알고리즘(inorder)
inorder(x):
if x=!NULL // 노드 x가 NULL일 경우 순환 호출을 진행하지 않음
then inorder(Left(x)); // x의 왼쪽 서브트리 순환호출 방문
print DATA(x); // x의 데이터 출력
inorder(RIGHT(x)); // x의 오른쪽 서브트리 순환호출 방문전위 순회 알고리즘과 달라진 것이라고는 함수명과 then 이후의 코드의 순서 뿐인데요. 실제로 그리 큰 차이가 없습니다.
후위 순회
후위 순회는 왼쪽 서브트리, 오른쪽 서브트리, 루트 순서대로 방문합니다. 컴퓨터 디렉토리의 용량을 나타내다보면 가장 루트의 총 용량을 구하고 싶겠죠? 그럴 때 사용한다고 생각하시면 기억하시기 좋습니다.
.png)
후위 순회 알고리즘(postorder)
postorder(x):
if x=!NULL // 노드 x가 NULL일 경우 순환 호출을 진행하지 않음
then postorder(Left(x)); // x의 왼쪽 서브트리 순환호출 방문
postorder(RIGHT(x)); // x의 오른쪽 서브트리 순환호출 방문
print DATA(x); // x의 데이터 출력3가지 순회를 C로 나타내 보자
이번에는 코드를 통해 위 알고리즘을 구현해보도록 하겠습니다.
// 전위 순회
void preorder(TreeNode *root){
if(root!=NULL){
printf("[%d]",root->data);
preorder(root->left);
preorder(root->right);
}
}
// 중위 순회
void inorder(TreeNode *root){
if(root!=NULL){
inorder(root->left);
printf("[%d]",root->data);
inorder(root->right);
}
}
// 후위 순회
void postorder(TreeNode *root){
if(root!=NULL){
postorder(root->left);
postorder(root->right);
printf("[%d]",root->data);
}
}
더불어서 이렇게 생성한 함수를 저번 포스팅에서 생성했던 트리노드 구조체와 함께 동작하는 것도 살펴보도록 하겠습니다.
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode{
int data;
struct TreeNode *left,*right;
} TreeNode;
// 15
// 4 20
// 1 16 25 를 나타냄
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;
// 전위 순회
void preorder(TreeNode *root){
if(root!=NULL){
printf("[%d]",root->data);
preorder(root->left);
preorder(root->right);
}
}
// 중위 순회
void inorder(TreeNode *root){
if(root!=NULL){
inorder(root->left);
printf("[%d]",root->data);
inorder(root->right);
}
}
// 후위 순회
void postorder(TreeNode *root){
if(root!=NULL){
postorder(root->left);
postorder(root->right);
printf("[%d]",root->data);
}
}
int main(void){
printf("전위 순회=");
preorder(root);
printf("\n");
printf("중위 순회=");
inorder(root);
printf("\n");
printf("후위 순회=");
postorder(root);
printf("\n");
return 0;
}
위 코드를 실행하거나 스크롤을 내려 실행 결과를 살펴 보기 이전에 한번 추측해보시면 도움이 될겁니다 ㅎㅎ
실행결과는 다음과 같아요.
전위 순회=[15][4][1][20][16][25]
중위 순회=[1][4][15][16][20][25]
후위 순회=[1][4][16][25][20][15]
레벨 순회
위에서 살펴본 3가지의 순회 방법은 표준적인 순회 방법입니다. 그것과 별개로 레벨 순회라는 것이 존재하여 이 부분에 대해서 설명을 드리고자 합니다. 레벨 순회는 말 그대로 각 노드를 레벨 순으로 검사하는 순회 방법입니다.
루트 노드서부터 아래로 방문하며 루트 노드 레벨이 1이라고 할 때 아래로 내려갈수록 레벨은 증가합니다. 동일한 레벨인 경우에는 좌에서 우로 방문합니다.
표준적인 순회 법에서는 스택을 활용했던 것에 비해 레벨 순회에서는 큐를 사용합니다.
.png)
레벨 순회를 할 시에는 위 그림의 순서로 방문한다는 것을 알아두시길 바랍니다.
위 레벨 순회를 알고리즘으로 구현하면 다음과 같이 됩니다.
위에서 말했듯이 레벨 순회에서는 큐를 사용하므로 큐에 대한 개념이 조금 있으시다면 편하게 이해하실 수 있습니다. 이전에 제가 큐에 대해 포스팅한 링크도 첨부하겠습니다.
level_order(root):
initialize queue; // 큐 초기화
if(root==null) then return;
enqueue(enqueue,root); // 루트 값을 큐에 삽입
while is_empty(queue)!=TRUE do // 큐에 요소가 단 하나라도 있다면
x<-dequeue(queue); // 큐에서 요소 출력
print x->data;
if(x->left!=NULL) then
enqueue(queue,x->left); // 왼쪽 요소 큐에 삽입
if(x->right!=NULL) then
enqueue(queue,x->right); // 오른쪽 요소 큐에 삽입알고리즘이 어느정도 이해되셨나요?
이번에는 레벨 순회 프로그램을 전체적으로 만들어보도록 하겠습니다.
레벨 순회 프로그램
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode{
int data;
struct TreeNode *left,*right;
}
#define MAX_QUEUE_SIZE 100
typedef TreeNode *element;
typedef struct{
element data[MAX_QUEUE_SIZE];
int front,rear;
} QueueType;
void error(char *message){
fprintf(stderr,"%s\n",message);
exit(1);
}
void init_queue(QueueType *q){
q->rear=q->front=0;
}
int is_empty(QueueType *q){
return q->rear==(q->front); //front값과 rear값이 같은 경우
}
int is_full(QueueType *q){
return (q->rear+1)%MAX_QUEUE_SIZE==q->front);
}
void enqueue(QueueType *q,element item){
if(is_full(q)){
error("OVERFLOW");
return ;
}
q->rear=(q->rear+1)%MAX_QUEUE_SIZE;
q->data[q->rear]=item;
}
int dequeue(QueueType *q){
if(is_empty(q)){
error("UNDERFLOW");
}
q->front=(q->front+1)%MAX_QUEUE_SIZE;
return q->data[q->front];
}
void level_order(TreeNode *ptr){ // 레벨 순회 함수
QueueType q;
init_queue(&q);
if(ptr==NULL) return;
enqueue(&q,ptr);
while(!is_empty(&q)){
ptr=dequeue(&q);
printf("[%d]",ptr->data);
if(ptr->left) enqueue(&q,ptr->left);
if(ptr->right) enqueue(&q,ptr->right);
}
}
// 15
// 4 20
// 1 16 25 를 나타냄
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("레벨 순회=");
level_order(root);
printf("\n");
return 0;
}
위 코드의 결과는 다음과 같습니다.
레벨 순회=[15][4][20][1][16][25]
✋ 마무리
이렇게 해서 오늘은 트리의 순회를 알아보았는데요.
내용이 많아보이지만 금방 이해할 수 있는 내용이라고 생각해요. 조금 어려웠던 부분은 레벨 순회 알고리즘..?
큐에 대해 조금 이해하고 보시면 충분히 쉽게 이해할 수 있으실 겁니다.
또한 어떠한 상황에서 어떤 순회를 사용할지에 대해 조금 생각해보는게 좋다고 생각합니다.
다음 포스팅은 아마 우선순위 큐가 될 것 같고, 내일은 월말이라 회고록을 작성할 것 같아요. ㅎㅎ
오늘 글도 읽어주셔서 정말 감사합니다:)
