이 게시글은 윤성우 선생님의 자료구조 강의를 수강 후 나름대로의 내용 정리를 한 것임을 미리 밝힙니다.
스스로의 복습을 위해 작성한 글이므로 심층있는 학습을 위해서는 책의 구매 및 강의수강을 권장합니다.
Prologue
이진트리의 구현은 이진트리를 만드는 도구의 구현이다.
(1) 이진트리 구현의 두가지 방법
1) 배열을 기반으로 하는 방법
노드에 번호를 부여하고 그 번호에 해당하는 값을 배열의 인덱스값으로 활용한다.
(편의상 배열의 첫번째 요소는 사용하지 않는다. -> 구현하는 사람 마음대로)
완전 이진 트리를 만드는 형식으로 이진트리를 만들 경우, 각 레벨의 처음 인덱스는 2의 제곱수, 각 레벨의 마지막 인덱스는 2의 제곱수 - 1 이 된다.
2) 연결리스트를 기반으로 하는 방법
트리의 구조와 리스트의 연결 구조가 일치한다. 따라서 구현과 관련된 직관적인 이해가 좋은 편이다.
(2) 헤더 파일에 정의된 구조체의 이해
//이진 트리의 노드를 표현한 구조체
typedef struct _bTreeNode//bTree인 이유 - BinaryTree의 약자이다.
{
BTData data;
struct _bTreeNode* left;
struct _bTreeNode* right;
} BTreeNode;지금까지 본 원형연결리스트, 양방향 연결리스트와는 또 다른 형태이다.
지금까지와 같이 공부했다면 이진트리의 노드를 정의하는 구조체, 이진트리 자체를 정의하는 구조체도 있다고 판단할텐데
이번에는 이진트리 자체를 정의하는 구조체는 정의하지 않는다.
스텍은 topindex, 덱은 머리와 꼬리, queue는 입구와 출구 등이 필요하고
계속해서 이가 바뀌기 때문에 이를 따로 정의하는 구조체가 필요하다.
하지만 이진 트리는 루트 노드만 알면 이진트리 전체를 아는 것이고 이 루트 노드가 바뀌지 않기 때문에 이진트리의 구조체를 따로 정의하지 않아도 된다.
따라서 트리의 주소값은 루트 노드의 주소값이 대신하게 된다.
(3) 헤더파일
#ifndef __BINARY_TREE_H__
#define __BINARY_TREE_H__
typedef int BTData;
typedef struct _bTreeNode
{
BTData data;
struct _bTreeNode * left;
struct _bTreeNode * right;
} BTreeNode;//노드 구조체 정의
/*** BTreeNode 관련 연산들 ****/
BTreeNode * MakeBTreeNode(void);// 노드의 생성, left와 right에는 NULL포인터 저장
BTData GetData(BTreeNode * bt);// 노드에 저장된 데이터를 반환
void SetData(BTreeNode * bt, BTData data);// 노드에 데이터를 저장
BTreeNode * GetLeftSubTree(BTreeNode * bt); //왼쪽 서브 트리의 주소값 반환 or 왼쪽 자식 노드의 주소값 반환이라고도 할 수 있다.
BTreeNode * GetRightSubTree(BTreeNode * bt); // 오른쪽 자식 노드의 주소값 반환 -> 둘다 부모 노드의 주소값 입력시 반환
왜 GetLeftChidNode가 아닌 GetLeftSuvTree인가? -> 왼쪽 자식 노드의 주소를 얻는 것이 결국 그 아래의 모든 트리의 주소를 얻는 것과 같다.
void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub);
void MakeRightSubTree(BTreeNode * main, BTreeNode * sub);
//초기화된 주소값을 하나 받아와서 왼쪽에 부모노드가 될 노드의 주소, 오른쪽에 오른쪽 자식노드가 될 노드의 주소를 입력하면 둘을 연결해주는 함수이다.
이 때 오른쪽 자식 노드 아래로 계속 트리가 생길 것이므로 서브트리를 얻는다라고 표현하는 것이 맞다고 볼 수 있다.
#endif(4) 내가 구현한 소스파일
메인 함수의 코드
#include <stdio.h>
#include "BinaryTree.h"
int main(void)
{
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, bt3);
MakeLeftSubTree(bt2, bt4);
printf("%d \n",
GetData(GetLeftSubTree(bt1)));
printf("%d \n",
GetData(GetLeftSubTree(GetLeftSubTree(bt1))));
return 0;
}내가 구현한 소스파일의 코드
#include <stdio.h>
#include <stdlib.h>
#include "BinaryTree.h"
BTreeNode* MakeBTreeNode()
{
BTreeNode* temp = malloc(sizeof(BTreeNode));
temp->left = NULL;
temp->right = NULL;
return temp;
}
BTData GetData(BTreeNode* bt)
{
return bt->data;
}
void SetData(BTreeNode* bt, BTData data)
{
bt->data = data;
}
BTreeNode* GetLeftSubTree(BTreeNode* bt)
{
if (bt->left == NULL)
{
printf("없는 걸 왜 찾아");
exit(-1);
}
else return bt->left;
}
BTreeNode* GetRightSubTree(BTreeNode* bt)
{
if (bt->right == NULL)
{
printf("없는 걸 왜 찾아");
exit(-1);
}
else return bt->right;
}
void MakeLeftSubTree(BTreeNode* main, BTreeNode* sub)
{
main->left = sub;
}
void MakeRightSubTree(BTreeNode* main, BTreeNode* sub)
{
main->right = sub;
}강의의 소스파일 코드
#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);//아 이게 차이점이네! 덮어씌울 수는 있으나 그럼 기존의 왼쪽 자식노드를 free해주는 것이 맞다.
main->left = sub;
}
void MakeRightSubTree(BTreeNode * main, BTreeNode * sub)
{
if(main->right != NULL)
free(main->right);
main->right = sub;
}
