이진 트리란?
루트 노드를 중심으로 두 개의 서브 트리로 나뉘어 짐.
나뉘어진 두 서브 트리도 모두 이진 트리.
노드가 위치 할 수 있는 곳에 노드가 존재하지 않으면, 공집합 노드가 존재하는 것으로 간주.
서브 트리
큰 트리는 작은 트리로 구성이 되는데 이렇듯 큰 트리에 속하는 작은 트리를 서브 트리라 함.
포화 이진 트리와 완전 이진 트리
포화 이진 트리
모든 레벨이 꽉 차 있고 노드를 더 추가하려면 레벨을 늘려야 하는 이진 트리.
완전 이진 트리
포화 이진 트리처럼 모든 레벨이 꽉 찬 상태는 아니지만, 차곡차곡 빈틈없이 노드가 채워진 이진 트리를 뜻한다.
연결 리스트 기반 이진 트리 구현
헤더파일에 정의된 구조체 // 구조체 자체만으로도 공집합 노드 두 개를 갖은 노드이자 트리
typedef struct _bTreeeNode //이진 트리의 노드를 표현한 구조체
{
BTData data; //데이터를 저장할 변수
struct _bTreeNode* left; //왼쪽 서브트리의 주소 값 저장할 포인터 변수
struct _bTreeNode* right; //오른쪽 서브트리의 주소 값 저장할 포인터 변수
}BTreeNode;
--BinaryTree.h
#ifndef BINARY_TREE_H
#define BINARY_TREE_H
typedef int BTData;
typedef struct _bTreeeNode
{
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 // !BINARY_TREE_H
--BinaryTree.c
#include <stdio.h>
#include <stdlib.h>
#include "BinaryTree.h"
BTreeNode* MakeBTreeNode(void) //이진 트리의 노드를 생성
{
BTreeNode* nd = (BTreeNode*)malloc(sizeof(BTreeNode)); //노드 생성
nd->left = NULL; //left 포인터 변수 초기화
nd->right = NULL; //right 포인터 변수 초기화
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; //서브트리를 메인의 오른쪽과 연결
}
--BinaryTreeMain.c
#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;
}
실행 결과
2
4
