자료구조 - 트리의 구현

트리의 구현

● 배열에 의한 이진트리 구현

일반적으로 이진트리는 배열로 구성하지 않습니다.

배열로 구현하려면, 왼쪽 자식의 인덱스를, 그리고 오른쪽 자식은 어디인지 그 인덱스를 기록해두고,

만약 자식이 없다면 인덱스 값을 -1로 두는 방식으로 자식이 없음을 표시합니다.

하지만 이렇게 배열로 구현을 하게 되면, 노드를 삭제 한 경우, 부모 노드에서 해당 삭제 한 노드를 가리키는 인덱스 값을 -1 로 수정해야 하고, 이 과정에서 어떤 노드가 부모였는지 탐색하는 과정이 발생하여 효율이 떨어지게 됩니다.

따라서 포인터 방식으로 구현을 선호하며, 배열 방식은 완전이진트리의 경우에만 사용합니다.

● 포인터에 의한 이진트리 구현

        

하나의 노드에, 자기 자신을 가리킬 수 있는 노드 포인터 타입을 2개 가지게 합니다.

그리고 하나는 왼쪽 자식을, 나머지 하나는 오른쪽 자식을 가리키도록 구성합니다.

이진트리에서 가장 중요한 작업은 순회 입니다. 트리의 순회는 재귀적으로 풀어 낼 수 있는데요.

다음은 트리 순회를 의사코드로 표현한 것입니다.

Traverse(node) {     if (node != NULL)     {         Traverse(Left child of node);         Traverse(Right child of node);     } }

위 코드는 루트노드부터 시작해서 모든 노드를 순회하고 있습니다. 하지만 어떠한 작업도 수행하지 않고

그저 방문만 하고 있습니다. 방문한 노드에 대해서 언제 작업을 수행하나 에 따라서 순회의 방식은

달라지며 전위순회, 중위순회, 후위순회로 나뉩니다.

       전위순회                          중위순회                        후위순회

각 순회 방식을 의사코드로 나타내면 다음과 같습니다.

void PreOrder(node) {     if (node != NULL)     {         output(nodo->data);         PreOrder(node->LChild);         PreOrder(node->Rchild);     } }

전위순회

void PreOrder(node) {     if (node != NULL)     {         PreOrder(node->LChild);         output(nodo->data);         PreOrder(node->Rchild);     } }

중위순회

void PreOrder(node) {     if (node != NULL)     {         PreOrder(node->LChild);         PreOrder(node->Rchild);         output(nodo->data);     } }

후위순회

전위, 중위, 후위 순회와 별개로, 트리의 레벨별로 순회하는 레벨순회가 있습니다.

이 경우, 트리의 레벨 별로 순차적으로 방문하게 되는 순회입니다.

레벨 순회의 의사코드는 다음과 같습니다.

void LevelOrder(root node) {     queue;     queue.enqueue(root node);     while (!queue.empty())     {         node = queue.dequeue();         Output(node);         if(node->LChild != NULL)             queue.enqueue(node->LChild);         if(node->RChild != NULL)             queue.enqueue(node->RChild);     } }

레벨순회

- by Raimondo