[자료구조론/C] 자료구조론 5편 트리

트리

이렇게 생긴 걸 트리라고 한다

트리의 용어

• 노드 : 트리의 구성요소
• 엣지 : 노드와 노드를 연결하는 연결선
• 루트 노드 : 최상위 노드
• 터미널 노드: 아래로 더 이상의 노드가 연결되어 있지 않은 노드
• 인터널 노드: 단말 노드를 제외한 모든 노드

이진 트리의 ADT

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

이진 트리의 C구현

• 헤더

#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);
void DeleteTree(BTreeNode *bt);

typedef void (*VisitFuncPtr)(BTData data);

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

#endif

• 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 DeleteTree(BTreeNode *bt)
{
	if(bt == NULL) return;
	DeleteTree(bt->left);
	free(bt);
	DeleteTree(bt->right);
}

void MakeLeftSubTre(BTreeNode *main, BTreeNode *sub)
{
	if(main->left != NULL)
		DeleteTree(main->left);
	
	main->left = sub;
}

void MakeRightSubTree(BTreeNode *main, BTreeNode *sub)
{
	if(main->right != NULL)
		DeleteTree(main->left);
		
	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;
	PreorderTraverse(bt->left, action);
	action(bt->data);
	PreorderTraverse(bt->right, action);
}

void PostorderTraverse(BTreeNode *bt, VisitFuncPtr action)
{
	if(bt == NULL) return;
	PreorderTraverse(bt->left, action);
	PreorderTraverse(bt->right, action);
	action(bt->data);
}

VisitFuncPtr에 대해 설명을 덧붙이자면, typedef로 별칭을 만든건데 VisitFuncPtr형(함수포인터)을 반환하는 action을 매개변수로 받는 것이다. 그러므로 action위치에 들어가는 함수포인터는 BTData형을 매개변수로 받는 함수의 포인터일 것이다.

• main

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

void ShowIntData(BTData data)
{
	printf("%d ", data);
}

int main()
{
	BTreeNode * bt1 = MakeBTreeNode();
	BTreeNode * bt2 = MakeBTreeNode();
	BTreeNode * bt3 = MakeBTreeNode();
	BTreeNode * bt4 = MakeBTreeNode();
	BTreeNode * bt5 = MakeBTreeNode();
	BTreeNode * bt6 = MakeBTreeNode();
	
	SetData(bt1, 1);
	SetData(bt2, 2);
	SetData(bt3, 3);
	SetData(bt4, 4);
	SetData(bt5, 5);
	SetData(bt6, 6);
	
	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;
}

이진트리 C++ 구현

요즘 C++ 공부 중이라 이것도 하고 싶다.

#include <iostream>
using namespace std;

template <typename T>
class BTree;

template <typename T>
class BTreeNode
{
	friend class Tree<T>;
private:
	T data;
	BTreeNode *left;
	BTreeNode *right;
public:
	BTreeNode() : data(null), left(null), right(null)
	{
		this->data = data;
		this->left = left;
		this->right = right;
	}
}

template <typename T>
class BTree
{
private:
	BTreeNode<T>* root;
public:
	BTree(T data = null)
	{
		root = new BTreeNode<T>(data);
	}
	
	void MakeLeftSubTree(BTreeNode *main, BTreeNode *sub);
	void MakeRightSubTree(BTreeNode *main, BTreeNode *sub);
	T GetData(BTreeNode* bt);
	void DeleteTree(BTreeNode *bt);
	void InorderTraverse(BTreeNode *bt, void (*funcPtr)(BTreeNode *));
}

template <typename T>
void BTree::MakeLeftSubTree(BTreeNode *main, BTreeNode *sub)
{
	if(main->left != nullptr) DeleteTree(main->left);
	main->left = sub;
}

template <typename T>
void BTree::MakeRightSubTree(BTreeNode *main, BTreeNode *sub)
{
	if(main->right != nullptr) DeleteTree(main->right);
	main->right = sub;
}

template <typename T>
T BTree::GetData(BTreeNode *bt)
{
	return bt->data;
}

template <typename T>
void DeleteTree(BTreeNode *bt)
{
	if(bt == nullptr) return;
	DeleteTree(bt->left);
	free(bt);
	DeleteTree(bt->right);
}

template <typenmae T>
void InorderTraverse(BTreeNode *bt, void (*funcPtr)(BTreeNode *))
{
	if(bt == nullptr) return;
	InorderTraverse(bt->left, funcPtr);
	funcPtr(bt->data);
	InorderTraverse(bt->right, funcPtr);
}

끝