Crocodile Tears

[알고리즘] 이진트리(Binary Tree)

* 리스트 구현

1. 이진 트리(binary tree)란 한 노드가 최대 두 개의 자식 노드를 가지는 트리를 뜻한다. 보통 첫 번째 노드를 부모 노드라고 하며 자식 노드는 왼쪽(left)과 오른쪽(right)으로 불린다. 이진 트리는 이진 탐색 트리와 이진 힙의 구현에 흔히 쓰인다.( Wiki )

From : http://www.silverwolf.co.kr/algorithm/4810

2. 순회

- 연결 리스트와 1차원 배열과 같은 선형 자료 구조에서는 한 가지의 논리적인 순회 방법만이 존재하지만, 

트리 구조의 순회에는 많은 방법이 존재한다. 

이진 트리의 루트 노드에서 시작해서, 세 가지 주요 단계를 거치며 순회를 진행하는데, 

그 단계에는 현재 노드를 방문하는 것, 

왼쪽 자식 노들 순회하는 것과 오른쪽 자식 노드를 순회하는 것이 있다. 이러한 과정은 재귀로 쉽게 설명할 수 있다.(Wiki)

* Images are from Wiki

A. 전위순회

- 노드 방문 -> 왼쪽 서브 트리를 전위 순회 -> 오른쪽 서브 트리를 전위 순회

B. 중위순회

- 왼쪽 서브 트리를 중위 순회 ->노드 방문 -> 오른쪽 서브 트리를 중위 순회

C. 후위순회

- 왼쪽 서브 트리를 후위 순회 -> 오른쪽 서브 트리를 후위 순회 -> 노드 방문

< BT.h >

#pragma once

typedef int BTData;

typedef struct _bTreeNode
{
	_bTreeNode *left;
	_bTreeNode *right;

	BTData data;
} 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 InorderTrasverse( BTreeNode *bt, VisitFuncPtr action );
// 후위 순회
void PostorderTraverse( BTreeNode *bt, VisitFuncPtr action );
// 트리 삭제
void DeleteTree( BTreeNode *bt );

< BT.cpp >

#include "BT.h"
#include 


BTreeNode* MakeBTreeNode( void )
{
	BTreeNode *node = (BTreeNode*)malloc( sizeof( BTreeNode ) );
	node->left = nullptr;
	node->right = nullptr;
	node->data = 0;

	return node;
}

BTData GetData( BTreeNode *bt )
{
	if ( bt == nullptr ) return -1;

	return bt->data;
}

void SetData( BTreeNode *bt, BTData data )
{
	if ( bt == nullptr ) return;

	bt->data = data;
}

BTreeNode* GetLeftSubTree( BTreeNode *bt )
{
	if ( bt == nullptr ) return nullptr;

	return bt->left;
}

BTreeNode* GetRightSubTree( BTreeNode *bt )
{
	if ( bt == nullptr ) return nullptr;

	return bt->right;
}
/// free하는 노드의 자식들이 있으면 메모리 누수남!
void MakeLeftSubTree( BTreeNode *main, BTreeNode *sub )
{
	if ( main == nullptr ) return;

	/// 이렇게 하면 메모리 누수
	//if ( main->left != nullptr )
	//	free( main->left );
	if ( main->left != nullptr )
		DeleteTree( main->left );

	main->left = sub;
}

void MakeRightSubTree( BTreeNode *main, BTreeNode *sub )
{
	if ( main == nullptr ) return;
	
	/// 이렇게 하면 메모리 누수
	//if ( main->right != nullptr )
	//	free( main->right );
	if ( main->right != nullptr )
		DeleteTree( main->right );

	main->right = sub;
}

void PreorderTraverse( BTreeNode *bt, VisitFuncPtr action )
{
	if ( bt == nullptr )
		return;

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

void InorderTrasverse( BTreeNode *bt, VisitFuncPtr action )
{
	if ( bt == nullptr )
		return;

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

void PostorderTraverse( BTreeNode *bt, VisitFuncPtr action )
{
	if ( bt == nullptr )
		return;

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

void DeleteTree( BTreeNode *bt )
{
	if ( bt == nullptr )
		return;

	DeleteTree( bt->left );
	DeleteTree( bt->right );
	free( bt );
}

< BTMain.cpp >

#include "BT.h"
#include 

//void InorderTraverse( BTreeNode *bt )
//{
//	if ( bt == nullptr )
//		return;
//
//	InorderTraverse( bt->left );
//	printf( "%d \n", bt->data );
//	InorderTraverse( bt->right );
//}
//
//void PreorderTraverse( BTreeNode *bt )
//{
//	if ( bt == nullptr )
//		return;
//
//	printf( "%d \n", bt->data );
//	PreorderTraverse( bt->left );
//	PreorderTraverse( bt->right );
//}
//
//void PostorderTraverse( BTreeNode *bt )
//{
//	if ( bt == nullptr )
//		return;
//
//	PostorderTraverse( bt->left );
//	PostorderTraverse( bt->right );
//	printf( "%d \n", bt->data );
//}

void ShowIntData( int data );

int main( void )
{
	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, 4 );
	SetData( bt6, 4 );

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

	PreorderTraverse( bt1, ShowIntData );
	printf( "\n" );
	InorderTrasverse( bt1, ShowIntData );
	printf( "\n" );
	PostorderTraverse( bt1, ShowIntData );

	DeleteTree( bt1 );

	return 0;
}

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

From : 열혈 C 자료구조