뇌를 자극하는 알고리즘 - 4. 트리 : Simple Binary Tree

구현소스

BinaryTree.h

#ifndef BINARYTREE_H
#define BINARYTREE_H

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



// SBT = Simple Binary Tree
// Binary Tree는 Maximum Degree(- Node 가 가지는 Child Node의 개수) 가 2인 Tree이다.
// - Binary Tree의 종류
// 1. Full Binary Tree - 포화 이진 트리
//  : Leaf Node(Height[- 최대 Depth값]에 존재하는 Node)를 제외한 모든 Node가 Child Node를 2개씩 가지고 있다.
//  : Leaf Node들이 모두 같은 Depth[- Root노드에서 해당 Node까지의 경로의 길이]에 존재한다.
// 2. Complete Binary Tree - 완전 이진 트리
//  : Leaf Node들이 트리의 왼쪽부터 차곡차곡 체워진 Tree
//  : CBT(Complete Binary Tree)는 FBT(Full Binary Tree)를 이루기 전 단계의 Tree이다.
// ex)
//             A
//         B       E        : Full Binary Tree
//      C    D  F    G
// ex)
//             A
//         B       E        : Complete Binary Tree
//      C    D  F            
// ex) 
//             A
//         B       D        : FBT도 아니고 CBT도 아닌 그냥병신 Binary Tree
//      C       E           
// 3. Height Balanced Tree - 높이 균형 트리
//  : Root Node를 기준으로 Left Child Tree(왼쪽 하위 트리)와
//   Right Child Tree(오른쪽 하위 트리)의 Height가 1이상 차이나지 않는 Binary Tree
// 4. Completely Height Balance Tree - 완전 높이 균형 트리
//  : Root Node를 기준으로 Left Child Tree(왼쪽 하위 트리)와
//   Right Child Tree(오른쪽 하위 트리)의 Height가 같은 Binary Tree
// ex)
//             A
//         B        E        : HBT
//      C     D  F     G
//   H    I

// ex)
//             A
//         B       E         : CHBT
//      C    D  F    G

typedef char Element;
typedef struct tagSBTNode{

	struct tagSBTNode* Left;
	struct tagSBTNode* Right;
	Element Data;

} SBTNode;

SBTNode* SBT_CreateNode(Element NewData);
void SBT_DestroyNode(SBTNode* Node);
void SBT_DestroyTree(SBTNode* Root);
// Tree를 파괴할때는 반드시 Leaf Node부터 제거해야 한다. (별로 상관없어보이는데 책에서 그렇다네)
// - Leaf Node부터 방문하여 Root Node까지 거슬러 올라가며 방문하는 후위 순회
//  (전위,중위는 Root node가 마지막에 제거되지 않음)를 이용하여 이진 트리 전체를 없앤다.

void SBT_PreorderPrintTree(SBTNode* Node);  // 전위 순회
void SBT_InorderPrintTree(SBTNode* Node);   // 중위 순회
void SBT_PostorderPrintTree(SBTNode* Node); // 후위 순회

// 모든 노드 출력 - 그냥 만들어봤음
void SBT_PrintTree(SBTNode* Root, int Depth=0);
#endif

-------------------------------------------------------------------------------
BinaryTree.cpp

#include "BinaryTree.h"


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

	return NewNode;
}
void SBT_DestroyNode(SBTNode* Node){
	free(Node);
}
// Tree를 파괴할때는 반드시 Leaf Node부터 제거해야 한다. 
// (별로 상관없어보이는데 책에서 그렇다네..)
// - Leaf Node부터 방문하여 Root Node까지 거슬러 올라가며 방문하는 후위 순회
//  (전위,중위는 Root node가 마지막에 제거되지 않음)를 이용하여 이진 트리 전체를 없앤다.
void SBT_DestroyTree(SBTNode* Root){
	if(Root==NULL)
		return;
	
	SBT_DestroyTree(Root->Left);
	SBT_DestroyTree(Root->Right);

	printf("  %c..Deleted\n", Root->Data);
	SBT_DestroyNode(Root);
}

// 전위 순회
// ex)
//             A
//         B       E        : Preorder - A B C D E F G 
//      C    D  F    G
void SBT_PreorderPrintTree(SBTNode* Node){
	if(Node == NULL)
		return ;

	printf("  %c, ",Node->Data);

	SBT_PreorderPrintTree(Node->Left);
	SBT_PreorderPrintTree(Node->Right);

}
// 중위 순회
// ex)
//             A
//         B       E        : Inorder - C B D A F E G 
//      C    D  F    G
void SBT_InorderPrintTree(SBTNode* Node){
	if(Node == NULL)
		return ;	

	SBT_InorderPrintTree(Node->Left);

	printf("  %c, ",Node->Data);

	SBT_InorderPrintTree(Node->Right);	

}
// 후위 순회
// ex)
//             A
//         B       E        : Postorder - C D B F G E A (Left child Node - Right child Node - Root Node로..)
//      C    D  F    G
void SBT_PostorderPrintTree(SBTNode* Node){
	if(Node == NULL)
		return ;

	SBT_PostorderPrintTree(Node->Left);	
	SBT_PostorderPrintTree(Node->Right);

	printf("  %c, ",Node->Data);

}

// 모든 노드 출력 - 그냥 만들어봤음
void SBT_PrintTree(SBTNode* Root, int Depth){

	int i=0;

	for(i=0;i<Depth;i++)
		printf("ㅡ");

	printf("%c\n",Root->Data);
	
	if(Root->Left != NULL) 
		SBT_PrintTree(Root->Left , Depth+1); 
	if(Root->Right != NULL) 
		SBT_PrintTree(Root->Right , Depth+1); 
	
}

-------------------------------------------------------------------------------
Main.cpp

#include "BinaryTree.h"

int main(){
	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;
//             A
//         B       E        : 현재 트리 상태
//      C    D  F    G

	SBT_PrintTree(A);

	printf("Preorder :  ");
	SBT_PreorderPrintTree(A); // A B C D E F G
	printf("\n");

	printf("Inorder :  ");
	SBT_InorderPrintTree(A); // C B D A F E G
	printf("\n");

	printf("Postorder :  ");
	SBT_PostorderPrintTree(A); // C D B F G E A
	printf("\n");

	SBT_DestroyTree(A);

	return 0;
}

-------------------------------------------------------------------------------
실행결과