ํธ๋ฆฌ ๊ฐ๋ ๋ฐ ๊ตฌํ
ํธ๋ฆฌ๋ ๋ค๋ฅธ ์๋ฃ๊ตฌ์กฐ์ ๋ค๋ฅด๊ฒ ๋น์ ํ ์๋ฃ๊ตฌ์กฐ์ด๋ค. ํธ๋ฆฌ๋ ๊ฐ์ง๋ฅผ ๋ป์ด ๋์๊ฐ๋ค.
ํธ๋ฆฌ์ ์ถ์ ์๋ฃํ
BTreeNode *MakeBtreeNode(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);
- ์ค๋ฅธ์ชฝ ์๋ธํธ๋ฆฌ๋ฅผ ์ฐ๊ฒฐํ๋ค.
ํธ๋ฆฌ์ ๊ฒฝ์ฐ ๊ฐ๋ ๊ณผ ๊ตฌํ์ ๊ฐ์ด ๋ณด๋ฉด ์ข์ ๊ฒ ๊ฐ์์ ํ๊ณณ์ ์ ๋ฆฌํด๋ณธ๋ค.
BinaryTree.h
#ifndef __BINARY_TREE_H__
#define __BINARY_TREE_H__
#define TRUE 1
#define FALSE 0
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
BinaryTree.c
#include <stdio.h>
#include <stdlib.h>
#include "BinaryTree.h"
BTreeNode *MakeBtreeNode(void) // intializer
{
BTreeNode *newNode = (BTreeNode *)malloc(sizeof(BTreeNode));
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
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;
}
BinaryTree.h
#ifndef __BINARY_TREE_H__
#define __BINARY_TREE_H__
#include <iostream>
typedef int BTData;
class BTreeNode
{
private:
BTData data;
BTreeNode *left;
BTreeNode *right;
public:
BTreeNode();
BTreeNode *MakeBtreeNode();
BTData GetData();
void SetData(BTData data);
BTreeNode *GetLeftSubTree();
BTreeNode *GetRIghtSubTree();
void MakeLeftSubTree(BTreeNode *sub);
void MakeRightSubTree(BTreeNode *sub);
void RemoveNode();
};
#endif
BinaryTree.cpp
#include "BinaryTree.h"
#include <iostream>
BTreeNode::BTreeNode() // ์์ฑ์๋ฅผ ํตํด ์ด๊ธฐํ ํด์ค๋ค.
{
left = NULL;
right = NULL;
}
// BTreeNode *BTreeNode::MakeBtreeNode() // main์์ ์ง์ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ํ ๋นํด ์ค ๊ฒ์ด๊ธฐ ๋๋ฌธ์
// ๊ตณ์ด ๋ง๋ค์ง ์๋๋ค.
// {
// BTreeNode *bt = new BTreeNode;
// bt->left = NULL;
// bt->right = NULL;
// return bt;
// }
BTData BTreeNode::GetData()
{
return data;
}
void BTreeNode::SetData(BTData _data)
{
data = _data;
}
BTreeNode *BTreeNode::GetLeftSubTree()
{
return left;
}
BTreeNode *BTreeNode::GetRIghtSubTree()
{
return right;
}
void BTreeNode::MakeLeftSubTree(BTreeNode *sub)
{
left = sub;
}
void BTreeNode::MakeRightSubTree(BTreeNode *sub)
{
right = sub;
}
void BTreeNode::RemoveNode()
{
BTreeNode *dTree = this;
if (dTree == NULL)
return ;
dTree->GetLeftSubTree()->RemoveNode();
dTree->GetRIghtSubTree()->RemoveNode();
std::cout << data << std::endl;
delete dTree;
}
ํธ๋ฆฌ์ ์ถ๋ ฅ์ ์ฌ๊ท๋ฅผ ํตํด ์ด๋ค์ง๋๋ฐ
void printData(BTreeNode *main)
{
if (main == NULL)
return ;
printData(main->left);
printf("%d ", main->data);
printData(main->right);
}
์ ์ ์ค์ ํ์ ์ํ๋ฅผ ํตํด๊ตฌํ ํ ์ ์๋ค. ์์ ์ฝ๋ ์ฒ๋ผ ๋ง์ด๋ค. ์ ์ฝ๋๋ ์ค์์ํ๋ฅผ ํตํด ๊ตฌํ ํ์๋ค. ๋งจ ์ผ์ชฝ ๋ ธ๋๋ก ์ด๋→์ค๋ฅธ์ชฝ ๋ ธ๋ ์ด๋ → ์ถ๋ ฅ → ๋ฉ๋ชจ๋ฆฌ ํด์ ์ ๋ฐฉ์์ ํตํด ๊ตฌํํ๋ค. ํ์ถ์ ๋ ธ๋๊ฐ null์ ๊ฐ๋ฅดํค๊ฒ ๋๋ฉด ํ์ถ ํ๋๋ก ๊ตฌํํ์๋ค.
void RemoveNode(BTreeNode *main)
{
if (main == NULL)
return ;
RemoveNode(main->left);
RemoveNode(main->right);
printf("%d ",main->data);
free(main);
}
์ญ์ ์ญ์ ์ถ๋ ฅ๊ณผ ๋ง์ฐฌ๊ฐ์ง๋ก ์ฌ๊ท๋ฅผ ์ฌ์ฉํด์ ๊ตฌํํ๋ค.
ํ ์ฝ๋: https://boiling-fowl-6d6.notion.site/Heap-e0df3107d7d344c7b02f36b9736a499f