<이진 트리 구현>
[BinaryTree.h]
/*
* 비선형 자료구조 - 연결 리스트 기반 이진 트리
* 파일명: BinaryTree.h
* 파일 버전: 0.2
* 작성자: Sevenshards
* 작성 일자: 2023-11-23
* 이전 버전 작성 일자: 2023-11-23
* 버전 내용: 전위, 중위 순회 추가 및 순회 시 할 일을 결정할 수 있도록 함수 포인터 사용.
* 이전 버전 내용: 중위 순회 기능까지 포함한 이진 트리 구현.
*/
// 저자의 표현을 빌리자면, 이진 트리를 구현"할 수 있는 도구"를 만드는 과정이다.
// 어디다 갖다 쓸 것인가는 나중에 생각하자.
#ifndef __BINARY_TREE_H__
#define __BINARY_TREE_H__
typedef int BTData; // 이진 트리의 데이터. 자료형은 편의상 int
// 이진 트리의 노드 구조체. 이중 연결 리스트 구조.
// 그리고 이 자체가 Tree다.
// 이전 선형 자료 구조에서는 리스트나 스택, 큐와 같은 경우는 노드 따로, 리스트, 스택, 큐를 따로 구조체를 정의하였다.
// 하지만 이건 노드임과 동시에 트리가 된다.
typedef struct _bTreeNode
{
BTData data;
struct _bTreeNode* left;
struct _bTreeNode* right;
} BTreeNode;
// 노드의 생성 및 데이터 저장과 조회
BTreeNode* MakeBTreeNode(void); // 이진 트리의 노드 생성
BTData GetData(BTreeNode* bt); // 이진 트리 노드의 데이터를 반환 (Getter)
void SetData(BTreeNode* bt, BTData data); // 이진 트리 노드에 데이터를 저장 (Setter)
BTreeNode* GetLeftSubTree(BTreeNode* bt); // 왼쪽 서브 트리의 주소 값(왼쪽 서브 트리의 루트 노드)을 반환
BTreeNode* GetRightSubTree(BTreeNode* bt); // 오른쪽 서브 트리의 주소 값(오른쪽 서브 트리의 루트 노드)을 반환
// 노드의 연결
void MakeLeftSubTree(BTreeNode* main, BTreeNode* sub); // 매개변수 sub로 전달된 트리 또는 노드를 매개변수 main의 왼쪽 서브트리로 연결
void MakeRightSubTree(BTreeNode* main, BTreeNode* sub); // 매개 변수 sub로 전달된 트리 또는 노드를 매개변수 main의 오른쪽 서브트리로 연결
// 순회 (재귀를 이용하여 구현한다!)
// 함수 포인터를 선언 -> 이 부분에 대한 설명이 좀 더 필요하다.
typedef void VisitFuncPtr(BTData data);
// typedef void (*VisitFuncPtr)(BTData data); -> 이거랑 동일하다.
// 여기에 대해서 내용을 추가 정리해두겠다.
// typedef 선언이 없었다고 치면 현재 반환형은 void에 매개변수는 BTData형의 data를 받는 함수가 되고, 함수의 이름은 VisitFuncPtr이 된다.
// 그런데 여기서 typedef 선언이 추가되면, 함수의 이름이 아니라 "함수 포인터"로 인지를 하게 된다.
// 마치 배열이 연산식에 사용되면 포인터가 되는 것처럼 decay된다는 개념과 비슷하다.
// 그렇기 때문에 VisitFuncPtr이라는 이름을 자료형처럼 쓸 수 있는 것이다.
// 중위 순회 1)왼쪽 서브 트리 -> 2)루트 노드 -> 3)오른쪽 서브 트리
void InorderTraversal(BTreeNode* bt, VisitFuncPtr action);
// 전위 순회 1)루트 노드 -> 2)왼쪽 서브 트리 -> 3)오른쪽 서브 트리
void PreorderTraversal(BTreeNode* bt, VisitFuncPtr action);
// 후위 순회 1)왼쪽 서브 트리 -> 2)오른쪽 서브트리 -> 3)루트 노드
void PostorderTraversal(BTreeNode* bt, VisitFuncPtr action);
// 트리의 모든 노드 삭제
void DeleteTree(BTreeNode* bt);
#endif
[BinaryTree.c]
/*
* 비선형 자료구조 - 연결 리스트 기반 이진 트리
* 파일명: BinaryTree.c
* 파일 버전: 0.2
* 작성자: Sevenshards
* 작성 일자: 2023-11-23
* 이전 버전 작성 일자: 2023-11-23
* 버전 내용: 전위, 중위 순회 추가 및 순회 시 할 일을 결정할 수 있도록 함수 포인터 사용.
* 이전 버전 내용: 중위 순회 기능까지 포함한 이진 트리 구현.
*/
// 저자의 표현을 빌리자면, 이진 트리를 구현"할 수 있는 도구"를 만드는 과정이다.
// 어디다 갖다 쓸 것인가는 나중에 생각하자.
#include <stdio.h>
#include <stdlib.h>
#include "BinaryTree.h"
// 노드의 생성 및 데이터 저장과 조회
BTreeNode* MakeBTreeNode(void) // 이진 트리의 노드 생성
{
BTreeNode* node = (BTreeNode*)malloc(sizeof(BTreeNode));
node->left = NULL;
node->right = NULL;
return node;
}
BTData GetData(BTreeNode* bt) // 이진 트리 노드의 데이터를 반환 (Getter)
{
return bt->data;
}
void SetData(BTreeNode* bt, BTData data) // 이진 트리 노드에 데이터를 저장 (Setter)
{
bt->data = data;
}
BTreeNode* GetLeftSubTree(BTreeNode* bt) // 왼쪽 서브 트리의 주소 값(왼쪽 서브 트리의 루트 노드)을 반환
{
return bt->left;
}
BTreeNode* GetRightSubTree(BTreeNode* bt) // 오른쪽 서브 트리의 주소 값(오른쪽 서브 트리의 루트 노드)을 반환
{
return bt->right;
}
// 노드의 연결
void MakeLeftSubTree(BTreeNode* main, BTreeNode* sub) // 매개변수 sub로 전달된 트리 또는 노드를 매개변수 main의 왼쪽 서브트리로 연결
{
if (main->left != NULL) // 이미 왼쪽에 연결된 트리나 노드가 있다면
free(main->left); // 할당된 메모리를 해제한다.
main->left = sub; // 그리고 새로 왼쪽에 연결한다.
}
void MakeRightSubTree(BTreeNode* main, BTreeNode* sub) // 매개 변수 sub로 전달된 트리 또는 노드를 매개변수 main의 오른쪽 서브트리로 연결
{
if (main->right != NULL) // 이미 오른쪽에 연결된 트리나 노드가 있다면
free(main->right); // 할당된 메모리를 해제한다.
main->right = sub; // 그리고 새로 오른쪽에 연결한다.
}
// 순회 (재귀를 이용하여 구현한다!)
// 중위 순회 1)왼쪽 서브 트리 -> 2)루트 노드 -> 3)오른쪽 서브 트리
void InorderTraversal(BTreeNode* bt, VisitFuncPtr action)
{
if (bt == NULL) // 만약 공집합 노드(NULL)이라면? 재귀의 탈출 조건이 된다.
return;
InorderTraversal(bt->left, action); // 1) 왼쪽 서브 트리를 순회
action(bt->data); // 2) 루트 노드를 방문
InorderTraversal(bt->right, action); // 3) 오른쪽 서브 트리를 순회
}
// 전위 순회 1)루트 노드 -> 2)왼쪽 서브 트리 -> 3)오른쪽 서브 트리
void PreorderTraversal(BTreeNode* bt, VisitFuncPtr action)
{
if (bt == NULL) // 만약 공집합 노드(NULL)이라면? 재귀의 탈출 조건이 된다.
return;
action(bt->data); // 1) 루트 노드를 방문
PreorderTraversal(bt->left, action); // 2) 왼쪽 서브 트리를 순회
PreorderTraversal(bt->right, action); // 3) 오른쪽 서브 트리를 순회
}
// 후위 순회 1)왼쪽 서브 트리 -> 2)오른쪽 서브트리 -> 3)루트 노드
void PostorderTraversal(BTreeNode* bt, VisitFuncPtr action)
{
if (bt == NULL) // 만약 공집합 노드(NULL)이라면? 재귀의 탈출 조건이 된다.
return;
PostorderTraversal(bt->left, action); // 1) 왼쪽 서브 트리를 순회
PostorderTraversal(bt->right, action); // 2) 오른쪽 서브 트리를 순회
action(bt->data); // 3) 루트 노드를 방문
}
// 트리의 모든 노드 삭제
void DeleteTree(BTreeNode* bt)
{
if (bt == NULL) // 공집합 노드(NULL)이라면 재귀 탈출.
return;
// 후위 순회를 통해 왼쪽, 그리고 오른쪽, 마지막으로 루트 노드를 비우는 형태로 진행.
DeleteTree(bt->left);
DeleteTree(bt->right);
printf("delete tree node data: %d\n", bt->data);
free(bt);
}
[BinaryTreeMain.c]
/*
* 비선형 자료구조 - 연결 리스트 기반 이진 트리
* 파일명: BinaryTreeMain.c
* 파일 버전: 0.2
* 작성자: Sevenshards
* 작성 일자: 2023-11-23
* 이전 버전 작성 일자: 2023-11-23
* 버전 내용: 전위, 중위 순회 추가 및 순회 시 할 일을 결정할 수 있도록 함수 포인터 사용.
* 이전 버전 내용: 중위 순회 기능까지 포함한 이진 트리 구현.
*/
#include <stdio.h>
#include "BinaryTree.h"
void ShowIntData(int data);
int main()
{
// 노드 생성
BTreeNode* bt1 = MakeBTreeNode();
BTreeNode* bt2 = MakeBTreeNode();
BTreeNode* bt3 = MakeBTreeNode();
BTreeNode* bt4 = MakeBTreeNode();
BTreeNode* bt5 = MakeBTreeNode();
BTreeNode* bt6 = MakeBTreeNode();
// 노드에 데이터 저장
SetData(bt1, 1);
SetData(bt2, 2);
SetData(bt3, 3);
SetData(bt4, 4);
SetData(bt5, 5);
SetData(bt6, 6);
MakeLeftSubTree(bt1, bt2); // bt1의 왼쪽 자식 노드로 bt2 연결
MakeRightSubTree(bt1, bt3); // bt1의 오른쪽 자식 노드로 bt3 연결
MakeLeftSubTree(bt2, bt4); // bt2의 왼쪽 자식 노드로 bt4 연결
MakeRightSubTree(bt2, bt5); // bt2의 오른쪽 자식 노드로 bt5 연결
MakeRightSubTree(bt3, bt6); // bt3의 오른쪽 자식 노드로 bt6 연결
PreorderTraversal(bt1, ShowIntData);
printf("\n");
InorderTraversal(bt1, ShowIntData);
printf("\n");
PostorderTraversal(bt1, ShowIntData);
printf("\n");
DeleteTree(bt1);
return 0;
}
void ShowIntData(int data)
{
printf("%d ", data);
}
이진 트리 구현을 하는 것은 어제 공부를 했었는데, 노션에만 따로 기록하고 여기에는 기록은 하지 않았다.
까먹을까봐 오늘은 구현했던 내용을 정리하는 겸 다시 복습 차원에서 내용을 좀 더 정리해둘까 싶다.
1) 헤더파일 (BinaryTree.h)
양방향 연결 리스트를 기반으로 작성했기 때문에 구조체는 left와 right라는 자기 참조 구조체를 정의하였다.
그리고 이진 트리의 ADT에 따라 사용할 함수들을 선언한 파일.
이진 트리의 ADT는 단순하다.
BTreeNode* MakeBTreeNode(void);
- 노드(트리)를 생성 및 초기화
BTData GetData(BTreeNode* bt);
- 노드에 저장된 데이터 반환 → 객체 지향의 관점에서 본다면 Getter가 될 수 있겠다.
void SetData(BTreeNode* bt, BTData data)
- 노드에 데이터를 저장, data로 전달된 값을 저장한다. → 마찬가지로 객체 지향의 관점에서 본다면 Setter
BTreeNode* GetLeftSubTree(BTreeNode* bt);
- 왼쪽 서브트리 (또는 단말노드)의 주소 값을 반환한다.
BTreeNode* GetRightSubTree(BTreeNode* bt);
- 오른쪽 서브트리( 또는 단말노드)의 주소 값을 반환한다.
void MakeLeftSubTree(BTreeNode* main, BTreeNode* sub);
- main으로 전달된 노드의 왼쪽에 sub로 전달받은 노드를 왼쪽 서브 트리로 연결한다.
void MakeRightSubTree(BTreeNode* main, BTreeNode* sub);
- main으로 전달된 노드의 오른쪽에 sub로 전달받은 노드를 오른쪽 서브 트리로 연결한다.
여기까지가 기본적인 ADT라고 보면 된다.
뒤는 추가를 한 부분인데, 재귀적인 부분에 대한 이해를 위해서 알아두면 좋다.
void PreorderTraversal(BTree Node*, VisitFuncPtr action);
void InorderTraversal(BTree Node*, VisitFuncPtr action);
void PostorderTraversal(BTree Node*, VisitFuncPtr action);
- Tree를 전위/중위/후위 순회하는 함수.
- 여기서 사용한 VisitFuncPtr은 함수 포인터 변수로, typedef 선언을 통해 정의하였다.
- 개인적으로 왜 이걸 이렇게 썼을까에 대해서는 주석을 읽어보시면 좋겠다.
void DeleteTree(BTreeNode* bt);
- 트리의 모든 노드를 삭제하는 함수.
2) 소스파일(BinaryTree.c)
헤더파일에서 선언한 함수들의 정의를 해놓은 파일.
핵심은 "트리는 재귀다" 라는 머릿속에 맴돌 정도로 중요하다고 생각한다.
순회 관련 함수를 정의할 때를 보면 재귀를 이용해서 순회를 하는 것을 구현해두었다.
왜 재귀를 사용하였는가 하면, 트리의 아래에는 또 다른 서브트리가 있을 수도 있고 없을 수도 있다.
하지만 서브트리가 있다고 하면 그 트리 안에서도 결국 순회를 해야하기 때문이다.
그래서 트리 아래에는 또 다른 트리가 있기 때문에 재귀적으로 해결을 하는 것이다.
순회도 그렇고 삭제도 재귀를 통해서 진행한다.
추가로 삭제의 경우에는 후위 순회 방식을 이용하여 삭제를 진행한다.
루트 노드는 가장 마지막에 메모리 할당이 해제되어야 하는 노드다.
그래서 왼쪽부터 시작해서 오른쪽, 그리고 마지막으로 루트 노드를 지워 나가야 한다.
3) 메인 함수 소스파일(BinaryTreeMain.c)
위에서 구현한 이진 트리가 제대로 작동하는지 확인하기 위해 작성한 코드.
문제는 없었고 제대로 돌아가는 것도 확인했다.
선형 자료 구조때도 그랬지만, 손으로 그려가면서 이해하는 것이 생각보다 도움이 많이 된다.
그리고 비선형 자료구조로 넘어오면서 뭔가 느낌이 확 달라졌다.
이전까지는 구조체로 노드를 따로 정의하고 리스트나 스택, 큐를 따로 정의했다.
그런데 트리부터는 그런 개념이 아니다.
자료구조는 데이터의 저장, 조회, 삭제만이 목적이 아니라 '표현' 또한 할 수 있어야 한다.
이 다음에 올라갈 글은 '수식 트리'를 올리게 될 것 같다.
'수식 트리'는 이진 트리의 일종이다.
수식을 표현하는 방식을 트리를 이용하여 데이터를 표현하는 방식을 맛볼 수 있는 자료구조라고 생각하면 되겠다.
