자료구조 : 트리 구현

ROK·2022년 10월 26일

C tree 구현 배열 열혈 자료구조 트리

열혈 자료구조

목록 보기

23/30

이진 트리의 구현

이제 트리에 대한 기본 정리를 완료했으니 구현을 통해서 이해해볼 차례이다.

이진 트리는 재귀적인 특성을 지니고 있다. 따라서 일부 연산은 재귀호출의 형태를 띈다.
재귀적인 사고, 재귀함수의 정의에 어느정도 익숙한 상태일 필요가 있다.

앞서 구현했던 자료 구조들처럼 배열 또는 연결 리스트 기반으로 구현이 가능하다.
하지만 트리를 구현하기에는 연결 리스트가 더 유연하기 때문에 구현할 트리는 연결리스트로 구현한다.

단, 트리가 완성 된 이후 해당 트리를 대상으로 탐색이 자주 이루어진다면 배열을 통한 구현도 고려해볼만 하다.
배열이 연결리스트에 비해 탐색이 매우 용이하고 빠르기 때문이다

배열 기반 이진 트리 구현

간략하게 배열을 통한 이진 트리를 구현하는 법

핵심은 노드에 번호를 부여하는 것이다.
번호의 의미는 각 노드의 데이터가 저장되어야 할 배열의 인덱스 값을 의미한다.

루트 노드를 인덱스 1번으로 지정하고 그 아래로 하나씩 값을 할당했다.

인덱스 0은 일반적으로 사용하지 않는다.

배열 기반의 트리는 나중에 힙(heap)을 공부할 때 다시 보게 된다.
힙은 완전 이진 트리 구조를 갖고, 배열을 기반으로 구현한다.

연결 리스트 기반 이진 트리 구현

위 사진을 보면 연결 리스트 구현 방식이 쉽게 이해가 된다.

이진 트리 자료구조의 ADT

BTreeNode * MakeBTrreNode(void);
- 이진 트리 노드를 생성하여 그 주소 값을 반환
BTData GetData(BTreeNode * bt);
- 노드에 저장된 데이터를 반환
void SetData(BTreeNode * bt, BTData data);
- 노드에 데이터 저장, data로 전달값 저장
BTreeNode * GetLeftSubTree(BTreeNode * bt);
- 왼쪽 서브 트리의 주소 값을 반환
BTreeNode * GetRightSubTree(BTreeNode * bt);
- 오른쪽 서브 트리의 주소 값을 반환
void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub);
- 왼쪽 서브 트리를 연결
void MakeRightSubTree(BTreeNode * main, BTreeNode * sub);
- 오른쪽 서브 트리를 연결

헤더파일

#ifndef __BINARY_TREE_H__
#define __BINARY_TREE_H__

typedef int BTData;

typedef struct _bTreeNode
{
   BTData data;
   struct _bTreeNode *left;
   struct _bTreeNode *right;
} BTreeNode;

BTreeNode *MakeBTreeNode(void);           // 노드의 생성 및 초기화
BTData GetData(BTreeNode *bt);            // 노드에 저장된 데이터 반환
void SetData(BTreeNode *bt, BTData data); // 노드에 데이터 저장

BTreeNode *GetLeftSubTree(BTreeNode *bt); //
BTreeNode *GetRightSubTree(BTreeNode *bt);

void MakeLeftSubTree(BTreeNode *main, BTreeNode *sub);
void MakeRightSubTree(BTreeNode *main, BTreeNode *sub);

#endif

소스파일

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

BTreeNode *MakeBTreeNode(void)
{
   BTreeNode *nd = (BTreeNode *)malloc(sizeof(BTreeNode));
   nd->left = NULL;
   nd->right = NULL;

   return nd;
}

BTData GetData(BTreeNode *bt)
{
   return bt->data;
}

void SetData(BTreeNode *bt, BTData data)
{
   bt->data = data;
}

BTreeNode *GetLeftSubTree(BTreeNode *bt)
{
   return bt->left;
}

BTreeNode *GetRightSubTree(BTreeNode *bt)
{
   return bt->right;
}

void MakeLeftSubTree(BTreeNode *main, BTreeNode *sub)
{
   if (main->left != NULL)
   {
      free(main->left);
   }
   main->left = sub;
}

void MakeRightSubTree(BTreeNode *main, BTreeNode *sub)
{
   if (main->right != NULL)
   {
      free(main->right);
   }
   main->right = sub;
}

메인파일

#include <stdio.h>
#include "BinaryTree.h"

int main()
{
   BTreeNode *bt1 = MakeBTreeNode();
   BTreeNode *bt2 = MakeBTreeNode();
   BTreeNode *bt3 = MakeBTreeNode();
   BTreeNode *bt4 = MakeBTreeNode();

   SetData(bt1, 1);
   SetData(bt2, 2);
   SetData(bt3, 3);
   SetData(bt4, 4);

   MakeLeftSubTree(bt1, bt2);
   MakeRightSubTree(bt1, bt2);
   MakeLeftSubTree(bt2, bt4);

   printf("%d \n", GetData(GetLeftSubTree(bt1)));

   printf("%d \n", GetData(GetLeftSubTree(GetLeftSubTree(bt1))));

   return 0;
}