문제 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);

}