#15 트리(Tree)

ADT

* 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);
- 오른쪽 서브 트리를 연결한다.

 

기본 트리

Main.c

#include <stdio.h>
#include "BinaryTree.h"

//순회
void InorderTraverse(BTreeNode* bt)
{
	if (bt == NULL)
		return;

	InorderTraverse(bt->left);
	printf("%d \n", bt->data);
	InorderTraverse(bt->right);
}

int main(void)
{
	BTreeNode* bt1 = MakeBTreeNode(); // 노드 bt1 생성
	BTreeNode* bt2 = MakeBTreeNode(); // 노드 bt2 생성
	BTreeNode* bt3 = MakeBTreeNode(); // 노드 bt3 생성
	BTreeNode* bt4 = MakeBTreeNode(); // 노드 bt4 생성
	BTreeNode* bt5 = MakeBTreeNode(); // 노드 bt5 생성

	SetData(bt1, 1); // bt1에 1저장
	SetData(bt2, 2); // bt1에 2저장
	SetData(bt3, 3); // bt1에 3저장
	SetData(bt4, 4); // bt1에 4저장

	MakeLeftSubTree(bt1, bt2); // bt2를 bt1의 왼쪽 자식 노드로
	MakeRightSubTree(bt1, bt3); // bt3를 bt1의 오른쪽 자식 노드로
	MakeLeftSubTree(bt2, bt4); // bt4를 bt2의 왼쪽 자식 노드로

	// bt1의 왼쪽 자식 노드의 데이터 출력
	//printf("%d \n", GetData(GetLeftSubTree(bt1)));

	// bt1의 온쪽 자식 노드의 왼쪽 자식 노드의 데이터 출력
	//printf("%d \n", GetLeftSubTree(GetLeftSubTree(GetLeftSubTree(bt1))));

	//순회적용
	InorderTraverse(bt1);
	return 0;
}

 

BinaryTree.h

#ifndef __BINARY_TREE_H__
#define __BINARY_TREE_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);

#endif

 

BinaryTree.c

#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);

	main->left = sub;
}

void MakeRightSubTree(BTreeNode* main, BTreeNode* sub)
{
	if (main->right != NULL)
		free(main->right);

	main->right = sub;
}

 

모든순회 트리

Main.c

#include <stdio.h>
#include "BinaryTree.h"

//old: 순회
//void InorderTraverse(BTreeNode* bt)
//{
//	if (bt == NULL)
//		return;
//
//	InorderTraverse(bt->left);
//	printf("%d \n", bt->data);
//	InorderTraverse(bt->right);
//}
//new
void ShowIntData(int data);

int main(void)
{
	BTreeNode* bt1 = MakeBTreeNode(); // 노드 bt1 생성
	BTreeNode* bt2 = MakeBTreeNode(); // 노드 bt2 생성
	BTreeNode* bt3 = MakeBTreeNode(); // 노드 bt3 생성
	BTreeNode* bt4 = MakeBTreeNode(); // 노드 bt4 생성
	BTreeNode* bt5 = MakeBTreeNode(); // 노드 bt5 생성
	//new
	BTreeNode* bt6 = MakeBTreeNode(); // 노드 bt5 생성

	SetData(bt1, 1); // bt1에 1저장
	SetData(bt2, 2); // bt1에 2저장
	SetData(bt3, 3); // bt1에 3저장
	SetData(bt4, 4); // bt1에 4저장
	//new
	SetData(bt5, 5); // bt1에 4저장
	SetData(bt6, 6); // bt1에 4저장

	MakeLeftSubTree(bt1, bt2);
	MakeRightSubTree(bt1, bt3);
	MakeLeftSubTree(bt2, bt4);
	MakeRightSubTree(bt2, bt5);
	MakeRightSubTree(bt3, bt6);

	PreorderTraverse(bt1, ShowIntData);
	printf("\n");
	InorderTraverse(bt1, ShowIntData);
	printf("\n");
	PostorderTraverse(bt1, ShowIntData);
	printf("\n");
	return 0;
}

//new
void ShowIntData(int data)
{
	printf("%d ", data);
}

 

BinaryTree.h

#ifndef __BINARY_TREE_H__
#define __BINARY_TREE_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);

//new
typedef void (*VisitFuncPtr)(BTData data);

//new
void PreorderTraverse(BTreeNode* bt, VisitFuncPtr action);
void InorderTraverse(BTreeNode* bt, VisitFuncPtr action);
void PostorderTraverse(BTreeNode* bt, VisitFuncPtr action);

#endif

 

BinaryTree.c

#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);

	main->left = sub;
}

void MakeRightSubTree(BTreeNode* main, BTreeNode* sub)
{
	if (main->right != NULL)
		free(main->right);

	main->right = sub;
}

//new
void PreorderTraverse(BTreeNode* bt, VisitFuncPtr action)
{
	if (bt == NULL)
		return;

	action(bt->data);
	PreorderTraverse(bt->left, action);
	PreorderTraverse(bt->right, action);
}

//new
void InorderTraverse(BTreeNode* bt, VisitFuncPtr action)
{
	if (bt == NULL)
		return;

	InorderTraverse(bt->left, action);
	action(bt->data);
	InorderTraverse(bt->right, action);
}

//new
void PostorderTraverse(BTreeNode* bt, VisitFuncPtr action)
{
	if (bt == NULL)
		return;

	PostorderTraverse(bt->left, action);
	PostorderTraverse(bt->right, action);
	action(bt->data);
}