336x280(권장), 300x250(권장), 250x250, 200x200 크기의 광고 코드만 넣을 수 있습니다.
[알고리즘] 이진트리(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" #includeBTreeNode* 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 자료구조
'알고리즘' 카테고리의 다른 글
| [알고리즘] 선형검색(linear search) (0) | 2016.06.08 |
|---|---|
| [알고리즘]삽입정렬(InsertionSort) (0) | 2016.05.20 |
| [알고리즘]선택정렬(Selection Sort) (0) | 2016.05.19 |
| [알고리즘]버블정렬(Bubble Sort) (0) | 2016.05.17 |
| [알고리즘]XOR 이용한 교체 알고리즘(swap) (0) | 2016.05.17 |
