문제 08-1 이진 트리의 소멸
문제 :
이진트리를 완전히 소멸시키는 함수를 선언하고 정의해보자.
void DeleteTree(BTreeNode * bt);
int main()
{
BTreeNode * bt1 = MakeBTreeNode();
....
DeleteTree(bt1);
....
위와 같이 DeleteTree 함수가 호출되면, bt1이 가리키는 노드를 루트 노드로 하는 트리 전부가 완전히 소멸되어야 한다.
//bt.h
#ifndef __BINARY_TREE2_H__
#define __BINARY_TREE2_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);
typedef void VisitFuncPtr(BTData data);
void PreorderTraverse(BTreeNode * bt, VisitFuncPtr action);
void InorderTraverse(BTreeNode * bt, VisitFuncPtr action);
void PostorderTraverse(BTreeNode * bt, VisitFuncPtr action);
void DeleteTree(BTreeNode * bt);
#endif
// bt.c
#include <stdio.h>
#include <stdlib.h>
#include "bt.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;
}
void PreorderTraverse(BTreeNode * bt, VisitFuncPtr action)
{
if (bt == NULL)
return;
action(bt->data);
PreorderTraverse(bt->left, action);
PreorderTraverse(bt->right, action);
}
void InorderTraverse(BTreeNode * bt, VisitFuncPtr action)
{
if (bt == NULL)
return;
InorderTraverse(bt->left, action);
action(bt->data);
InorderTraverse(bt->right, action);
}
void PostorderTraverse(BTreeNode * bt, VisitFuncPtr action)
{
if (bt == NULL)
return;
PostorderTraverse(bt->left, action);
PostorderTraverse(bt->right, action);
action(bt->data);
}
void DeleteTree(BTreeNode * bt)
{
if (bt == NULL)
return;
DeleteTree(bt->left);
DeleteTree(bt->right);
printf("%d", bt->data);
free(bt);
}
// btm
#include <stdio.h>
#include "bt.h"
void showdata(int data);
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, bt3);
MakeLeftSubTree(bt2, bt4);
PreorderTraverse(bt1, showdata); // delete 전 전위 순회
printf("\n");
DeleteTree(bt1); // delete 하기
printf("\n");
PreorderTraverse(bt1, showdata); // delete 후 순회
return 0;
}
void showdata(int data)
{
printf("%d ", data);
}
