[자료구조론] C로 이진트리를 만들어보자

안녕하세요. 김용성입니다.
오늘은 지난 포스팅에서 말한대로 트리에 대해 설명하고 이진트리를 간단하게 구현해보도록 하겠습니다.

트리란?

지금껏 다뤄보았던 스택, 큐, 리스트는 선형 자료구조였습니다. 그렇지만 계층적인 구조를 가지고 있는 자료 구조도 존재합니다. 예를 들면 컴퓨터의 디렉토리 구조, 회사의 조직 체계도 등 그러한 계층적인 자료를 구현해야할 때는 어떻게 해야할까요?
그러한 계층적인 자료를 표현하기 위해서 고안된 것이 바로 트리입니다.

다음 그림과 같은 구조를 가지고 있죠.

트리의 특징에 대해서 구체적으로 이야기하자면, 우선 트리는 한 개 이상의 노드로 이뤄진 유한 집합 입니다.
이들 중 하나의 노드는 루트 노드라고 불리고 나머지 노드들은 서브 트리라고 불리죠. 위 그림의 경우 계층적인 구조에서 가장 높은 곳에 있는 노드인 A가 루트가 됩니다.
나머지 노드들은 {B,D,E}라는 서브트리와 {C,F,G}라는 서브트리로 나뉘어지게 되고 {B,D,E}라는 서브트리에서는 루트가 B가 되는 것이고 {D,E}라는 서브트리가 존재하는 것이죠.
이러한 루트와 서브트리는 선으로 연결되며 이 연결선을 우리는 간선이라고 부릅니다.
노드들 간에는 부모 관계, 형제 관계, 조상과 자손 관계가 존재하죠.

이진트리

이진트리의 특징

이러한 트리 중 가장 편리하게, 많이 사용하는 것은 바로 이진트리입니다.
일반적인 트리에서 각 노드들은 서로 다른 개수의 자식 노드를 가지고 있기 때문에 각 노드의 크기가 고정되지 않아 프로그램이 복잡해진다는 단점이 있지만, 이진트리는 최대 자식의 개수가 2개라고 설정한 트리이기에 고정되고 복잡하지 않은 프로그램을 보장해주죠. 제가 맨 처음 올린 사진의 그림 또한 이진트리입니다.

이진트리의 각 노드들은 2개의 자식을 가지고 있기 때문에 다음과 같이 표현할 수 있습니다.

이진 트리의 노드에는 최대 2개까지의 자식 노드가 존재할 수 있습니다. 그말은 즉슨 모든 노드의 차수가 2이하가 되고, 공집합 또한 이진트리가 된다는 것입니다. 또한 서브 트리간 엄연한 순서가 존재하므로 왼쪽 서브트리와 오른쪽 서브 트리는 서로 구별됩니다.

이진트리의 성질

위에서 살펴본 이진트리의 특징에 기인한 성질을 몇가지 알아보도록 하겠습니다.

• n개의 노드를 가진 이진트리는 정확하게 n-1의 간선을 가집니다. 그 이유는 이진트리에서의 노드는 루트를 제외하면 정확하게 하나의 부모노드를 가지기 때문입니다.
• 높이가 h인 이진트리의 경우, 최소 h개의 노드를 가지며 최대 2^h-1개의 노드를 가집니다. 그 이유는 한 레벨에는 적어도 하나의 노드는 존재해야하기 때문입니다. 또한 하나의 노드는 최대 2개의 자식을 가질 수 있으므로 레벨 i에서의 노드의 최대개수는 2^i-1이되고, 시그마 공식을 활용하여 i=1부터 h까지 2^i-1을 계산하면 2^h-1이 됩니다.
• n개의 노드를 가지는 이진트리의 높이는 최대 n이거나 최소 밑이 2인 log(n+1)이 됩니다. 그 이유는 레벨 당 최소한 하나의 노드가 있어야 하므로 높이가 n을 넘을 수 없고 높이 h의 이진트리가 가질 수 있는 노드의 최대값은 2^h-1이기 때문이죠. 이 부분은 시간복잡도를 측정할 때 중요하게 작용합니다.

높이에 대해서는 헷갈리시는 분들이 있을 것 같아 그림으로 나타내보도록 하겠습니다. 만약 요소가 4개인 트리가 있을 때 최대 높이와 최소 높이는 다음과 같이 됩니다.

이진트리의 분류

이진트리는 다음과 같이 3가지의 형태로 분류할 수 있습니다.

• 포화 이진 트리
• 완전 이진 트리
• 기타 이진 트리

하나하나 설명드리도록 하겠습니다.

포화 이진 트리

위 그림은 포화 이진 트리입니다. 영어로는 full binary tree라고 하는데요. 용어 그대로 트리의 각 레벨에 노드가 꽉 차있는 이진트리를 의미합니다. 즉 높이가 k인 이진트리는 정확하게 2^k-1개의 노드를 가지죠.
포화 이진트리에서는 각 노드에 번호를 붙일 수 있는데요. 부모와 자식의 번호 사이에는 다음과 같은 규칙이 있습니다.

부모의 번호*2=왼쪽 자식의 번호
부모의 번호*2+1=오른쪽 자식의 번호

이러한 규칙을 기억하시길 바랍니다.

완전 이진 트리

완전 이진 트리는 마지막 레벨 k의 노드들이 꽉차있지는 않지만 중가넹 빈곳이 없이 채워져 있는 것을 말합니다. 다음 그림과 같은 경우를 완전 이진트리라고 하죠.

이러한 완전 이진 트리는 나중에 힙(heapq)을 배울 때 유용하게 사용된다는 것을 기억해주세요.

기타 이진 트리

기타 이진 트리는 위에서 설명한 포화 이진 트리와 기타 이진 트리 그 어느 것에도 해당하지 않는 것을 의미합니다. 마지막 레벨에서 중간이 비어있다면 완전 이진 트리가 아니므로 대표적인 기타 이진 트리가 되는 것이죠.

이제 이론적인 부분은 이정도로 하고 코드로 구현하기 위해 이진트리의 표현 종류를 한번 배워보도록 하겠습니다.

이진 트리의 표현

이진 트리를 컴퓨터 프로그램 안에서 표현하는 방법으로는 다음과 같이 2가지가 존재합니다.

• 배열 표현법
• 포인터 표현법

우선 배열 표현법부터 간단하게 살펴보고 포인터 표현법을 알아보도록 하겠습니다.

배열 표현법

배열을 이용하는 방법은 주로 포화 이진 트리나 완전 이진 트리의 경우 많이 쓰이는 방법입니다. 이 방법은, 저장하고자 하는 이진 트리를 완전 이진트리라고 가정하고 이진트리의 깊이가 2^k-1개의 공간을 연속적으로 할당한 다음, 완전 이진 트리의 번호대로 노드들을 저장합니다.

부모의 번호*2=왼쪽 자식의 번호
부모의 번호*2+1=오른쪽 자식의 번호

라는 공식도 배열 표현법에서 적극 활용됩니다.

그림으로 설명해보도록 하겠습니다.

여기서 배열의 0번 인덱스를 사용하지 않는 이유는 계산의 복잡함을 방지하기 위함입니다.
만약 0번 인덱스를 사용하게 된다면 0이 루트 노드의 번호가 될 것이고 위에서 언급한 공식이 성립하지 않게 되겠죠?

링크 표현법

링크 표현법에서는 트리에서의 노드가 구조체로 표현되고, 각 노드가 포인터를 가지고 있어서 이 포인터를 이용하여 노드와 노드를 연결하는 방법입니다. 앞서 다뤘던 연결 리스트와 비슷한 개념인데요. 이 경우에 각 노드의 모양이 제가 가장 최상위에 첨부하였던 노드의 모양이 됩니다.

만약 왼쪽 오른쪽에 자식이 없다면 해당 링크에 NULL 값을 넣어주는 식으로 코드를 구현하면 됩니다.
오늘 저는 이 링크 표현법을 활용하여 C로 트리를 구현해보도록 하겠습니다.

이진트리 코드 구현

링크 표현에 의해 나타내기 위해 C언어의 구조체와 포인터 개념을 활용하도록 하겠습니다.

typedef struct TreeNode{
  int data;
  struct TreeNode *left, *right;
} TreeNode;

어디선가 본 것 같은 구조체이죠? 바로 이전 포스팅에서 진행했던 이중 연결 리스트의 노드와 굉장히 유사합니다. 하지만 의미하는 바는 전혀 다르다는 점 주의해주시길 바랍니다.
저는 위 구조체를 통해 다음과 같은 트리를 구현해보도록 하겠습니다.

코드는 다음과 같습니다.

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode{
  int data;
  struct TreeNode *left, *right;
} TreeNode;

int main(void)
{
  TreeNode *n1,*n2,*n3;
  n1=(TreeNode *)malloc(sizeof(TreeNode));
  n2=(TreeNode *)malloc(sizeof(TreeNode));
  n3=(TreeNode *)malloc(sizeof(TreeNode));
  n1->data=10;
  n1->left=n2;
  n1->right=n3;
  n2->data=20;
  n2->left=NULL;
  n2->right=NULL;
  n3->data=30;
  n3->left=NULL;
  n3->right=NULL;
  free(n1);free(n2);free(n3);
  return 0;
}

어떤가요? 잘 이해되시나요?? 🤗 🤗 🤗

마무리

오늘은 트리의 구조에 대해서 알아보았습니다.
트리하면 가장 중요한 것은 바로 순회인데요.
다음 포스팅에서는 순회에 대해 알아보도록 하겠습니다.
읽어주셔서 감사합니다:)