Binary Tree(이진트리)

1. Binary Tree

Binary Tree 보통 이진트리라고 부르는 이 트리는 자식노드를 최대 2개까지만 가질 수 있는 트리입니다. 예를 들어, n개의 노드를 가진 이진트리는 n-1의 간선을 가집니다. 높이가 h인 이진트리는 최소 h(높이)개의 노드를 가지며, 최대 2의 h승 -1개의 노드를 가집니다. n개의 노드를 가지는 이진트리의 높이는 최대 n이거나 최소log2(n+1)이 됩니다.

이진트리의 분류

• 포화 이진트리 : 트리의 각 레벨에 노드가 꽉 차있는 이진트리

• 완전 이진트리 : 레벨 1부터 k-1까지는 노드가 모두 채워져 있고 마지막 레벨 k에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 이진트리

• 기타 이진트리

이진트리의 순회

순회한다는 것은 이진트리에 속하는 모든 노드를 한번씩 방문하여 노드가 가지고 있는 데이터를 목적에 맞게 처리하는 것을 의미합니다. 이진트리를 순회하는 표준적인 방법에는 전위, 중위, 후위등 3가지가 있다.

• 전위 순회 : 루트를 먼저 방문하고 그 다음에 왼쪽서브트리, 마지막으로 오른쪽 서브트리를 방문하는 것이다.
  

• 중위 순회 : 먼저 왼쪽 서브트리, 루트, 오른쪽 서브트리 순으로 방문한다.
  

• 후위 순회 : 왼쪽 서브트리, 오른쪽 서브트리, 루트 순으로 방문한다.

헤더파일

BinaryTree.h

#ifndef BINARY_TREE_H
#define BINARY_TREE_H

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

typedef char ElementType;

typedef struct tagSBTNode {
	struct tagSBTNNode* Left;
	struct tagSBTNNode* Right;

	ElementType Data;
} SBTNode;

SBTNode* SBT_CreateNode(ElementType NewData);
void SBT_DestroyNode(SBTNode* Node);
void SBT_DestroyTree(SBTNode* Root);

void SBT_PreorderPrintTree(SBTNode* Node);
void SBT_InorderPrintTree(SBTNode* Node);
void SBT_PostorderPrintTree(SBTNode* Node);

#endif

Node구조체를 살펴보면 Left와 Right 2개로 ChildNode의 주소값을 받을 공간을 부여해준 모습입니다. 다음 함수들을 보면,

SBTNode* SBT_CreateNode(ElementType NewData); -> Node 생성함수
void SBT_DestroyNode(SBTNode* Node); -> Node 삭제함수
void SBT_DestroyTree(SBTNode* Root); -> Tree 삭제함수

void SBT_PreorderPrintTree(SBTNode* Node); -> 전위순회 출력함수
void SBT_InorderPrintTree(SBTNode* Node); -> 중위순회 출력함수
void SBT_PostorderPrintTree(SBTNode* Node); -> 후위순회 출력함수

생성 삭제 순회함수로만 이루어진 모습입니다.

소스파일

BinaryTree.c

#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* Node) {
	free(Node);
}

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

	//왼쪽 하위 트리 소멸
	SBT_DestroyTree(Node->Left);

	//오른쪽 하위 트리 소멸
	SBT_DestroyTree(Node->Right);

	//뿌리 노드 소멸
	SBT_DestroyNode(Node);
}

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

먼저 생성 삭제함수를 먼저 보겠습니다.

SBTNode* SBT_CreateNode(ElementType NewData) {
	SBTNode* NewNode = (SBTNode*)malloc(sizeof(SBTNode)); -> Node 동적할당
	NewNode->Left = NULL; -> Node의 Left초기화
	NewNode->Right = NULL; -> Node의 Right초기화
	NewNode->Data = NewData; -> Data 저장

	return NewNode; -> Node반환
}

void SBT_DestroyNode(SBTNode* Node) {
	free(Node); -> Node동적 할당 해제
}

void SBT_DestroyTree(SBTNode* Node) {
	if (Node == NULL) { -> 재귀함수 탈출구문
		return;
	}
	SBT_DestroyTree(Node->Left); -> 왼쪽 자식노드로 재귀적 호출

	SBT_DestroyTree(Node->Right); -> 오른쪽 자식노드로 재귀적 호출
 
	SBT_DestroyNode(Node); -> 다 훑었으면 Node삭제
}

Tree삭제 함수부터 재귀적 호출이 들어갑니다. 그만큼 Tree는 재귀적 호출이 효율적이라는 것을 알 수 있습니다.

그럼 다음으로 순회함수들을 보겠습니다.

void SBT_PreorderPrintTree(SBTNode* Node) { -> 가운데 -> 왼쪽 -> 오른쪽
	if (Node == NULL) { -> 재귀함수 탈출구문
		return;
	}

	printf(" %c", Node->Data); -> 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); -> 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); -> Data출력
}

실행예시

BinaryTreeMain.c

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

	//트리 출력
	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");

	//트리 소멸
	SBT_DestroyTree(A);

	return 0;
}

결과

Preorder ...
 A B C D E F G

Inorder ...
 C B D A F E G

Postorder ...
 C D B F G E A