[C로 만드는 자료구조]이진 트리(Binary Tree) - 배열

이진 트리 (Binary Tree) - 정의

이진트리란 트리의 노드 구조를 일정하게 정의하여 트리의 구현과 연산이 쉽도록 정의한 트리입니다. 또한 이진이라는 단어에서 의미처럼 모든 노드가 2개의 서브 트리를 가지고 있는 트리를 의미입니다. (서브트리는 공집합일 수 있습니다.)

이진트리의 모든 노드는 왼쪽 자식노드와 오른쪽 자식 노드를 가집니다. 자식노드는 최소 0개부터 최대 2개 까지 가질 수 있습니다.

이진 트리 (Binary Tree) - 특성

이진트리는 노드의 개수가 n개일때 n-1개의 간선의 개수를 가지게 됩니다. root를 제외한 (n-1)개의 노드가 부모 노드와 연결되는 한개의 간선을 가지기 때문에 이런 결과가 나오게됩니다.

또한 높이가 h인 이진 트리가 가질 수 있는 노드의 최소 개수는 h+1개가 되며, 최대 개수는 (2^(h+1)) + 1개가 됩니다.

• 최소 노드 개수 : 이진 트리 높이가 h가 되려면, 한 레벨에 최소한 한 개의 노드가 있어야 하기 떄문에 h+1개가 나오게 된다.
  
  
• 최대 노드 개수 : 한나의 노드는 최대 2개의 자식 노드를 가질 수 있으므로 레벨 i에서의 노드 최대 개수는 2^i개 이며 계산식으로 나타내면 다음과 같이 됩니다.
  
  
  
  

추가로 왼쪽에 있는 트리를 지칭해서 편향 이진 트리(skewed binary tree) 라고 하며 오른쪽에 있는 트리를 포화 이진 트리 라고 합니다.

n개의 노드를 가지는 이진트리의 높이의 최대값은 n-1개가 되며 최소는 이 됩니다.

이진 트리 (Binary Tree) - 이진 트리의 분류

위 그림에서 왼쪽부터 포화이진트리, 완전이진트리, 기타이진트리라고 부릅니다.

• 포화이진트리 : 모든 단말 노드가 같은 레벨에 있으며, 모든 중간 노드는 두 개의 자식노드를 가지는 경우를 의미
  
  
• 단말 노드의 수가 n일때 전체 노드의 수 N = 2n -1개
• 아래와 같이 각 노드에 번호를 붙일 수 있음.
  

• 완전이진트리 : 위에서 아래로 왼쪽에서 오른쪽으로 순차적으로 채워가는 트리
  
  
• 마지막 레벨을 제외하고 포화 이진 트리이며, 최하위 레벨의 단말 노드들은 왼쪽에서부터 채워진 형태로 되어 있는 경우를 의미
• 중간 노드의 자식 수가 2일 때, 단말 노드의 수가 n이면, 전체 노드 수는 N = 2n-1개가 됨
• 완전 이진트리 또한 포화 이진트리와 노드 번호와 일치합니다.
  
  
  

• 기타이진트리 : 그 외의 트리

이진 트리 (Binary Tree) - 이진 트리의 구현 - 배열

이진트리는 다음과 같은 구조를 가지게됩니다.

이진 트리는 순환적 구성을 가지기 때문에 재귀함수로 구현이 가능합니다. 노드의 왼쪽 자식을 루트로 했을때도 트리 오른쪽 자식 노드를 루트로 해도 트리인 것이 그 이유입니다.

트리구현은 배열로도 할 수 있고 동적으로도 할 수 있는데 배열기반을 먼져 해보겠습니다. 트리를 배열로 구현할 때는 1차원 배열을 이용하며 트리의 노드번호들이 배열의 인덱스 번호와 일치하게 만듭니다.

이진 트리 (Binary Tree) - ADT - 배열

이진 트리를 배열로 구현할 때는 다음의 구조체들을 사용하게됩니다.

#include<stdio.h>
#define MAX_SIZE 16
struct Tree_Node
{
    int key;//데이터
};
struct Tree
{
    Tree_Node TreeArray[MAX_SIZE];//트리용 배열
    int cur = 1;
};

이제 각 ADT들을 구현해 보겠습니다.

• Add_Tree()
  
  
  

  void Add_Tree(Tree *Target_Tree, int Item)
  {
      if (Target_Tree->cur == MAX_SIZE)
      {
          printf("Tree is Full\n");
          return;
      }
      Target_Tree->TreeArray[Target_Tree->cur].key = Item;
      Target_Tree->cur += 1;
  }

  트리에 노드를 추가하는 함수입니다. 최대 값을 이용해 꽉 찼는지 확인한후 채워 넣습니다.
  
  

• Erase_Tree    
  
  
  

  void Erase_Tree(Tree *Target_Tree)
  {
      if (Target_Tree->cur == 0)
      {
          printf("Tree is empty\n");
          return;
      }
      Target_Tree->cur -= 1;
  }

  비어있는 지를 확인한 후 트리에서 노드 하나를 제거하는 함수 입니다. 리턴을 시켜야 하는데 이번엔 제외했습니다.
  
  

• void Show_Right/Left_Child()
  
  

  void Show_Right_Child(Tree *Target_Tree,int POSITION)
  {
      if (POSITION * 2 > MAX_SIZE)
      {
          printf("This Node is Terminal Node\n");
          return;
      }
      printf("right child is %d\n", Target_Tree->TreeArray[POSITION * 2].key);
  }
  void Show_left_Child(Tree *Target_Tree,int POSITION)
  {
      if (POSITION * 2 + 1 > MAX_SIZE)
      {
          printf("This Node is Terminal Node\n");
          return;
      }
      printf("right child is %d\n", Target_Tree->TreeArray[POSITION * 2 + 1].key);
  }

  지정한 위치에서 노드의 오른쪽 자식 또는 왼쪽 자식을 출력해주는 함수입니다. 단말노드일 경우  종료합니다
  
  

• int Show_Parents()
  

  int Show_Parents(Tree *Target_Tree,int Position)
  {
      if (Position <= 0)
      {
          printf("\n");
          return 0;
      }
      printf("%d ", Target_Tree->TreeArray[Position].key);
      if (Position % 2 == 1)
          return Show_Parents(Target_Tree,(Position-1) / 2);
      if (Position % 2 == 0)
          return Show_Parents(Target_Tree,Position / 2);
      return 0;
  }

  특정 위치에서의 노드에서 부터 루트까지의 모든 부모들을 출력하는 함수입니다. 재귀함수를 이용하여 제작하였습니다.
  
  
  

배열을으론 특별히 구현해볼만한 기능이 없어서 간단하게 몇개만 구현해 보았습니다. 다음번엔 동적으로 구현한 이진트리에서의 이진트리 순회에 대해서 포스팅 하겠습니다.