[ 자료구조 ] 트리 - 02 . 이진트리

[이진트리]

[이진트리]

Binary(이진) Tree는 모든 노드가 최대 2개의 자식을 가질 수 있는 트리 . 

데이터를 담는 용도 보다는 이진 구조를 활용한 알고리즘이 있다 .

• 수식을 트리 형태로 표현하여 계산하게 하는 수식 이진 트리  .
• 빠른 데이터 검색을 가능하게 하는 이진 탐색 트리 .

[이진트리의 형태]

이진트리는 컴파일러나 검색등에 사용되는 특수 구조 자료이다 . 이진트리를 이용한 검색에서 

높은 성능을 위해서 트리의 노드들은 가능한 완전한 모습으로 배치되어야 한다 .

다음은 완전한 모습의 트리의 목록이다 .

[포화 이진트리]

잎 노드를 재외한 모든 노드가 자식을 둘 씩 가지고 있는 이진트리

잎 노드들이 모두 같은 깊이에 존재한다 .

 

[완전 이진트리]

잎 노드들이 트리의 왼쪽부터 차곡 차곡 채워진 것이 특징이다 . 아래의 그림은 모두 완전 이진트리이다 .

=>중간에 빠진 잎이 없다 = 완전 이진트리

=>잎 노드 사이에 이빨이 빠져 있다 = 완전 이진트리가 아니다 .

 

[높이 균형 트리]

비슷한 맥락으로 이진트리의 상태를 분류하는 용어들이 또 있다 . 높이 균형 트리는 루트 노드를 기준으로 왼쪽 하위 트리와 오른쪽 하위 트리의 높이가 1 이상 차이나지 않는 이진트리를 말한다 . 

[완전 높이 균형 트리]

완전 높이 균형 트리는 루트 노드를 기준으로 왼쪽 하위 트리와 오른쪽 하위 트리의 높이가 동일한 이진트리를 말한다 . 

 

[이진트리의 순회]

순회는 트리 내의 노드들 사이를 돌아다니는 것을 말한다 . 순회는 몇 가지 규칙에 근거 , 이진 트리 내부를 돌아다니며 효율적인 방법으로 원하는 데이터에 접근 할 수 있는 방법을 제공한다 .

 

[전위 순회]

1. 루트 노드부터 시작해서 아래로 내려온다 .
2. 왼쪽 하위 트리를 방문
3. 왼쪽 하위 트리 방문이 끝나면 오른쪽 하위트리 방문

=>전위 순회는 하위트리에서도 루트 , 왼쪽 하위 , 오른쪽 하위 트리 순으로 방문한다 .

 

전위 순회를 통해 이진트리를 중첩된 괄호로 표현 할 수 있다 . 루트부터 시작하여 탐문 노드의 깊이가

깊어질때마다 괄호를 한겹씩 두른다 .

(A(B(C,D),(E(F,G))

 

[중위 순회]

1. 왼쪽 하위 트리부터 시작한다 (트리의 가장 왼쪽 잎 노드부터 시작 )
2. 루트를 거친다 .
3. 오른쪽 하위 트리를 방문한다 .

중위 순회의 대표적인 사례는 수식 트리 이다 .

노드를 방문할때마다 그 노드에 담긴 값을  순서대로 출력하고 , 하위 트리의 시작과 끝에는 '(' 와 ')'를 붙인다 .

=>수식 (1*2) + (7-8) 이 해당 방식으로 산출된다 .

 

[후위 순회]

1. 왼쪽 하위 트리부터 시작한다 (트리의 가장 왼쪽 잎 노드부터 시작 )
2. 오른쪽 하위 트리를 방문한다 .
3. 루트를 거친다 

후위 순회로 다음 트리를 읽어보면 어떤 값이 나올까 ?

 

=>바로 후위 표기식이 나온다 . 결과는 1 2 * 7 8 - + 

 

[이진트리의 주요 연산]

[ 노드의 선언 ]

typedef char ElementType;

typedef struct tagSBNode
{
    struct tagSBNode* Left;
    struct tagSBNode* Right;
    ElementType Data;
}SBTBode;

[ 노드의 생성 ]

SBTNode* SBT_CreateNode(ElementType NewData)
{
    SBTNode* NewNode = (SBTNode*)malloc(sizoeof(SBTNode));
    NewNode->Right=NULL;
    NewNode->Left=NULL;
    NewNode->Data = NewData;
    return NewNode;
}

 

[ 노드의 삭제 ]

void SBT_DestroyBode(SBTNode* Destroy)
{
	free(Destroy);
}

[ 전위순회를 응용한 이진트리 출력 구현 ]

void SBT_PreorderPrintTree(SBTNode* Node)
{
    if(Node==NULL)
    return;
    
    printf("%c",Node ->Data);
    
    SBT_PreorderPrintTree(Node->Left);
    
     SBT_PreorderPrintTree(Node->Right); 
}

[ 중위순회를 응용한 이진트리 출력 구현 ]

void SBT_InorderPrintTree(SBTNode* Node)
{
    if(Node==NULL)
    return;
      
    SBT_InorderPrintTree(Node->Left);
    
     printf("%c",Node ->Data);
    
     SBT_InorderPrintTree(Node->Right); 
}

[ 후위순회를 응용한 이진트리 출력 구현 ]

void SBT_PostorderPrintTree(SBTNode* Node)
{
    if(Node==NULL)
    return;
      
    SBT_PostorderPrintTree(Node->Left);
    
    SBT_PostorderPrintTree(Node->Right); 
    
     printf("%c",Node ->Data);
    
     
}

[ 후위순회를 응용한 트리 소멸 함수 구현 ]

void ET_DestroyTree(ETNode* Root)
{
    if(Root==NULL)
    return;
    
    ET_DestroyTree(Root->LeftNode);
    
    ET_DestroyTree(Root->RightNode);
    
    ET_DestroyNode(Root->Root);
    
}

[이진트리의 구현]

[BinaryTree.h]

#ifndef BT
#define BT

#include<stdio.h>
#include<stdlib.h>

typedef char ElementType;

typedef struct tagSBTNode
{
	struct tagSBTNode* Left;
	struct tagSBTNode* Right;
	ElementType Data;
}SBTNode;

//노드 생성
SBTNode* SBT_CreateNode(ElementType NewData);

//노드 삭제
void SBT_DestroyNode(SBTNode* Destoy);

//트리 삭제
void SBT_DestroyTree(SBTNode* Root);

//전위순회
void SBT_PreorderPrintTree(SBTNode* Node);

//중위순회
void SBT_InorderPrintTree(SBTNode* Node);

//후위순회
void SBT_PostorderPrintTree(SBTNode* Node);


#endif // !BT

[BinaryTree.cpp]

#include "BinaryTree.h"

SBTNode* SBT_CreateNode(ElementType NewData)
{
	SBTNode* NewNode = (SBTNode*)malloc(sizeof(SBTNode));
	NewNode->Left = NULL;
	NewNode->Right = NULL;
	NewNode->Data = NewData;
	return NewNode;
}

void SBT_DestroyNode(SBTNode* Destoy)
{
	free(Destoy);
}

void SBT_DestroyTree(SBTNode* Root)
{
	if (Root == NULL)
		return;

	SBT_DestroyTree(Root->Left);
	SBT_DestroyTree(Root->Right);
	SBT_DestroyNode(Root);
}

//전위순회
void SBT_PreorderPrintTree(SBTNode* Node)
{
	if (Node == NULL)
		return;

	printf("%c  ", Node->Data);
	SBT_PreorderPrintTree(Node->Left);
	SBT_PreorderPrintTree(Node->Right);
}
//중위순회
void SBT_InorderPrintTree(SBTNode* Node)
{
	if (Node == NULL)
		return;

	SBT_InorderPrintTree(Node->Left);
	printf("%c  ", Node->Data);
	SBT_InorderPrintTree(Node->Right);
}
//후위순회
void SBT_PostorderPrintTree(SBTNode* Node)
{
	if (Node == NULL)
		return;

	SBT_PostorderPrintTree(Node->Left);
	SBT_PostorderPrintTree(Node->Right);
	printf("%c  ", Node->Data);
}

[Test.cpp]

#include "BinaryTree.h"

int main(void)
{
	SBTNode* A = SBT_CreateNode('A');
	SBTNode* B = SBT_CreateNode('B');
	SBTNode* C = SBT_CreateNode('C');
	SBTNode* D = SBT_CreateNode('D');
	SBTNode* E = SBT_CreateNode('E');
	SBTNode* F = SBT_CreateNode('F');
	SBTNode* G = SBT_CreateNode('G');

	A->Left = B;
	B->Left = C;
	B->Right = D;

	A->Right = E;
	E->Left = F;
	E->Right = G;

	printf("Preorder ...\n");
	SBT_PreorderPrintTree(A);
	printf("\n\n");

	printf("Inorder ...\n");
	SBT_InorderPrintTree(A);
	printf("\n\n");

	printf("Postorder ...\n");
	SBT_PostorderPrintTree(A);
	printf("\n\n");

	SBT_DestroyTree(A);
	printf("End\n");
	return 0;
}