19-5-다.트리의 순회

트리로 어떤 작업을 하려면 트리의 모든 노드를 한 번씩 방문하는 순회를 해야 한다. 그래야 노드의 값을 출력하거나 검색, 삭제 등의 작업을 할 수 있다. 이진 트리를 구성하는 작은 서브 트리는 루트, 왼쪽, 오른쪽 세 개의 노드로 구성되어 있으므로 이 세 노드의 방문 순서에 따라 다음 여섯 가지 순회 방법을 생각할 수 있다.

① 루트-왼쪽-오른쪽 ② 루트-오른쪽-왼쪽

③ 왼쪽-루트-오른쪽 ④ 왼쪽-오른쪽-루트

⑤ 오른쪽-루트-왼쪽 ⑥ 오른쪽-왼쪽-루트

이 중 왼쪽을 반드시 오른쪽보다 먼저 순회하도록 한다면 ①, ③, ④ 세 가지만 남는다. 이 세가지 순회 방법을 각각 전위 순회(PreOrder), 중위 순회(InOrder), 후위 순회(PostOrder)라고 하는데 루트의 방문 위치에 따라 이름을 붙인다. 전위 순회는 루트를 먼저 방문하고 좌우를 각각 방문하며 중위 순회는 왼쪽을 먼저 방문하고 루트를 중간에 방문하며 마지막으로 오른쪽을 방문하는 방식이다.

차일드가 또 다른 자식을 가지고 있다면 차일드의 자식을 먼저 순회하고 돌아와야 하므로 트리의 순회 함수들은 재귀적인 호출을 한다. 다음 예제는 간단한 트리를 생성하고 이 트리를 세 가지 방법으로 모두 순회하면서 노드의 값을 출력한다.

예 제 : TreeTraverse

#include <Turboc.h>

struct Node

{

int data;

Node *left;

Node *right;

};

Node *Root;

void InitTree(int data)

{

Root=(Node *)malloc(sizeof(Node));

Root->data=data;

}

Node *AddChild(Node *Parent,int data,BOOL bLeft)

{

Node *New;

New=(Node *)malloc(sizeof(Node));

New->data=data;

New->left=NULL;

New->right=NULL;

if (bLeft) {

Parent->left=New;

} else {

Parent->right=New;

}

return New;

}

void PreOrder(Node *R)

{

printf("%d ",R->data);

if (R->left) PreOrder(R->left);

if (R->right) PreOrder(R->right);

}

void InOrder(Node *R)

{

if (R->left) InOrder(R->left);

printf("%d ",R->data);

if (R->right) InOrder(R->right);

}

void PostOrder(Node *R)

{

if (R->left) PostOrder(R->left);

if (R->right) PostOrder(R->right);

printf("%d ",R->data);

}

void FreeTree(Node *R)

{

if (R->left) FreeTree(R->left);

if (R->right) FreeTree(R->right);

free(R);

}

void main()

{

Node *Left,*Right;

InitTree(1);

Left=AddChild(Root,2,TRUE);

Right=AddChild(Root,3,FALSE);

AddChild(Left,4,TRUE);

AddChild(Left,5,FALSE);

AddChild(Right,6,TRUE);

PreOrder(Root);puts("");

InOrder(Root);puts("");

PostOrder(Root);puts("");

FreeTree(Root);

}

트리를 초기화하고 트리에 노드를 추가하는 InitTree, AddChild 함수가 작성되어 있는데 InitTree는 루트만 생성하고 AddChild는 지정한 부모의 왼쪽이나 오른쪽에 차일드를 추가한다. AddChild의 코드는 연결 리스트의 링크 조작 코드와 비슷하게 작성되어 있다. 이 두 함수는 어디까지나 인위적인 테스트 트리를 생성하기 위해 작성한 것이며 실제 트리 생성 방법은 알고리즘에 따라 특수하게 작성되어야 한다. main에서는 정수를 데이터로 가지는 다음과 같은 트리를 생성한다.

이렇게 만들어진 트리를 세 가지 방법으로 순회하면서 데이터를 출력하는데 대표적으로 루트를 먼저 방문하는 PreOrder 함수를 보자. 루트를 우선적으로 처리해야 하므로 자신의 데이터를 printf 함수로 먼저 출력했다. 여기서 printf 함수 호출은 순회중에 하고자 하는 작업에 해당하는데 검색이라면 data를 비교하고 삭제라면 노드 제거 함수를 호출하면 될 것이다.

그리고 루트의 왼쪽, 오른쪽 각각을 출력하되 각 차일드들이 또 다른 서브 트리일 수도 있으므로 이 서브 트리에 대해서도 PreOrder 함수를 호출하여 차일드의 루트부터 모든 차일드를 출력하도록 해야 한다. 그래서 자신을 다시 호출하는 재귀 호출 구조를 가지고 있다. 위 그림에서 1을 출력할 때 왼쪽 차일드 2가 또 다른 서브 트리이므로 2에 대해서도 PreOrder 함수를 호출하였다.

PreOrder(2) 호출은 자신을 먼저 출력하고 또 4, 5번 자식에 대해 전위 순회를 하되 4, 5는 모두 차수가 0인 잎 노드이므로 더 이상 재귀를 하지 않고 자신만 출력한 후 리턴할 것이다. 2번 서브 트리의 출력이 끝나면 다음번 호출인 PreOrder(3)이 호출되어 오른쪽 서브 트리가 출력된다. 각 서브 트리에 대해 루트와 차일드를 모두 거치므로 트리의 모든 노드를 순회하게 된다. 중위 순회하는 InOrder, 후위 순회하는 PostOrder 함수도 루트를 처리하는 순서만 다를 뿐 재귀 구조는 동일하다.

재귀 호출을 사용하지 않으려면 자식 노드로 내려 가기 전에 스택에 돌아올 번지를 푸시하면서 순회하는 방법을 사용할 수도 있다. 그러나 트리는 자료 구조 자체가 재귀적이기 때문에 재귀 호출을 사용하는 것이 가장 자연스럽다. main에서는 세 방법으로 순회한 결과를 출력하는데 순서가 틀릴 뿐이지 결국 모든 노드를 한 번씩 방문한다.

1 2 4 5 3 6

4 2 5 1 6 3

4 5 2 6 3 1

생성한 트리를 해제하는 FreeTree 함수는 각 노드를 해제하되 자식 노드를 먼저 해제한 후 루트를 해제해야 하므로 후위 순회법을 사용한다. 루트를 먼저 해제하면 자식 노드를 알 수 없게 되므로 후위 순회가 적합하다.

레벨별 순회는 레벨이 낮은 순으로 노드를 방문하는 방식이다. 전위, 중위, 후위 순회는 일단 주어진 서브 트리를 먼저 완전히 방문한 후 다음 서브 트리를 찾지만 레벨별 순회는 서브 트리를 기준으로 하지 않고 레벨을 기준으로 하므로 재귀 호출을 사용하지 않는다. 대신 노드를 만날 때마다 자신을 출력한 후 자신의 자식들을 차례대로 큐에 밀어 넣어 직계 자식들이 우선적으로 처리되도록 한다.

예 제 : LevelTraverse

#include <Turboc.h>

struct Node

{

int data;

Node *left;

Node *right;

};

Node *Root;

Node **Queue;

int QSize;

int head,tail;

void InitQueue(int size)

{

QSize=size;

Queue=(Node **)malloc(QSize*sizeof(Node *));

head=tail=0;

}

void FreeQueue()

{

free(Queue);

}

BOOL Insert(Node *data)

{

if ((tail+1) % QSize == head) {

return FALSE;

}

Queue[tail]=data;

tail=(tail+1) % QSize;

return TRUE;

}

Node *Delete()

{

Node *data;

if (head==tail) {

return NULL;

}

data=Queue[head];

head=(head+1) % QSize;

return data;

}

void InitTree(int data)

{

Root=(Node *)malloc(sizeof(Node));

Root->data=data;

}

Node *AddChild(Node *Parent,int data,BOOL bLeft)

{

Node *New;

New=(Node *)malloc(sizeof(Node));

New->data=data;

New->left=NULL;

New->right=NULL;

if (bLeft) {

Parent->left=New;

} else {

Parent->right=New;

}

return New;

}

void FreeTree(Node *R)

{

if (R->left) FreeTree(R->left);

if (R->right) FreeTree(R->right);

free(R);

}

void LevelOrder(Node *R)

{

Node *tNode;

Insert(R);

while (head != tail) {

tNode=Delete();

printf("%d ",tNode->data);

if (tNode->left) Insert(tNode->left);

if (tNode->right) Insert(tNode->right);

}

}

void main()

{

Node *Left,*Right;

InitQueue(128);

InitTree(1);

Left=AddChild(Root,2,TRUE);

Right=AddChild(Root,3,FALSE);

AddChild(Left,4,TRUE);

AddChild(Left,5,FALSE);

AddChild(Right,6,TRUE);

LevelOrder(Root);puts("");

FreeTree(Root);

FreeQueue();

}

앞에서 만들었던 큐 관련 함수를 그대로 복사해 오되 큐에 들어가는 데이터가 Node * 타입이라는 점이 다르다. LevelOrder 함수는 큐에 저장된 노드를 순서대로 꺼내 출력하는데 먼저 루트부터 큐에 밀어 넣고 루프를 시작한다. 매 루프에서 큐에 최후로 저장된 노드를 꺼내 이 노드를 출력하고 자신의 차일드를 차례대로 큐에 삽입한다. 첫 번째 루프에서 1이 출력되고 1의 자식 2와 3이 차례대로 큐에 들어갔을 것이다.

다음 번 루프를 돌 때는 다음 레벨인 2와 3이 순서대로 큐에서 꺼내져 처리되는데 이때 2와 3의 각 자식인 4, 5, 6이 차례대로 큐에 삽입되어 다음 차례를 기다릴 것이다. 레벨 2의 노드들이 처리되는 과정에서 레벨 2의 자식 노드인 레벨 3의 모든 노드가 큐에 삽입되는 것이다. 그래서 다음 레벨에서는 사촌들끼리 모아서 출력되면서 레벨 4의 자식 노드들이 삽입된다. 이런 식으로 레벨별로 좌에서 우로 모든 노드를 큐에 삽입하면서 하나씩 꺼내 출력하면 레벨별 순회를 할 수 있다.

먼저 삽입된 노드가 먼저 처리되어야 하므로 이 경우는 큐가 가장 적절하다. 이때 큐의 크기는 한 레벨의 최대 노드 개수만큼이어야 하는데 예제의 경우 128로 잡았으므로 한 레벨에 최대 128개까지의 노드가 있는 트리를 처리할 수 있다. 물론 크기를 늘리면 얼마든지 더 큰 트리도 레벨 순회를 할 수 있을 것이다.

이상으로 트리의 기본적인 용어와 많이 사용되는 이진 트리의 모양, 생성하는 방법, 그리고 순회하는 방법에 대해 알아보았다. 다소 이론적인 내용만 다루었고 실무에 바로 적용할 수 있을만한 내용은 없는 셈인데 트리는 워낙 형태가 변화 무쌍해서 적용되는 알고리즘에 따라 구현 방법이 다양하므로 여기서 응용을 다루기는 어렵다.