[#5] Binary Search Tree (이진 탐색 트리)

BinaryTree ( 이진 트리 ) 개념

BinaryTree (이진 트리)란?

수식 계산이나 컴파일러, 데이터 검색을 구현할 때 사용하는 특수한 형태의 자료구조이다. 수식 이진 트리(Expression Binary Tree)와 이진 탐색 트리(Binary Search Tree)가 있다. 이 포스팅에서는 이진 탐색 트리를 다룬다.

 

Full Binary Tree (포화 이진 트리)

노드의 끝에 해당하는 잎노드가 모두 같은 깊이일 경우 포화 이진 트리라 한다.

 

 

Complate Binary Tree (완전 이진 트리)

위에 그림에서 G부터 순차적으로 하나씩 비어있는 노드를 완전 이진 트리라 한다.

 

위 그림 처럼 중간에 이빨 빠진 듯이 노드가 없는 상태면 완전 이진 트리가 아니다. 굳이 완전 이진 트리를 규명하는 이유는 트리의 노드를 비교적 완전한 형태로 배치해야 높은 성능을 발휘하기 때문이다.

 

 

Height Balanced Tree (높이 균형 트리)

높이 균형 트리는 Root 노드를 기준으로 각 왼쪽 하위 트리와 오른쪽 하위 트리의 높이가 1이상 차이나지 않는 이진 트리를 뜻한다.

 

Complately Height Balanced Tree (완전 높이 균형 트리)

완전 높이 균형 트리는 왼쪽 하위 트리와 오른쪽 하위 트리의 높이가 동일할 때를 의미한다.

 

*높이 : 트리의 가장 깊은 곳에 있는 단말 노드(잎 노드)까지의 깊이를 뜻한다.

*Root : Root 노드는 뿌리를 의미하는 노드이며 트리를 이루는 세 구조 뿌리(Root), 가지(Branch), 잎(Leaf) 중 가장 최초로 생성되는 노드를 뜻한다. 

 

 

 

Traversal (순회)

순회는 트리 내의 노드들 사이를 돌아다니는 것을 의미한다. 이진 트리의 순회 방식에는 총 3가지가 있으며, 전위 순회, 중위 순회, 후위 순회가 있다.

 

 

Preorder Traversal (전위 순회)

전위 순회는 루트 노드부터 왼쪽 하위 노드까지 방문 한다음 오른쪽 하위 노드를 방문하는 방식이다. 

위 그림을 중괄호로 표현하면 다음과 같다. ( A ( B ( C, D ) ) , ( E ( F , G ) ) )

 

트리는 하위 트리의 집합이다.
각 하위 트리 역시 또 다른 하위 트리의 집합이다. 이러한 정의는 또 다른 하위 트리로 나뉘어질 수 없을 때 까지 계속 된다. 

 

Inorder Traversal (중위 순회)

중위 순회의 대표적인 사용 예는 수식 트리(Expression Tree)이다.  위에 언급한 방식대로 하위트리의 하위트리까지 방문한 후 왼쪽 하위 트리의 마지막까지 방문한 후 출력을 재귀적으로 시작한다.

 

Postorder Traversal (후위 순회)

왼쪽 하위 트리 - 오른쪽 하위 트리 - 루트 노드 순으로 방문한다. 하위 트리가 잎 노드면 방문이 중지된다. 이진 트리의 데이터 회수시에도 후위 순회가 유용하게 사용된다.

 

---

 

전체 코드

BinaryTree.h

// 2022-08-05 by
// Fubao & Jin 
// BinaryTree 이진트리 구현

#ifndef __BINARY_TREE_H__
#define __BINARY_TREE_H__

#include <iostream>
#include <cstdlib>

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

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

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

#endif

 

BinaryTree.cpp

#include "BinaryTree.h"

// 잎노드 2개를 가리키는 트리 노드를 생성 
SBTNode* SBT_CreateNode(ElementType NewData)
{
	SBTNode* NewNode = new SBTNode;
	NewNode->Left = nullptr;
	NewNode->Right = nullptr;
	NewNode->Data = NewData;
	return NewNode;
}

void SBT_DestroyNode(SBTNode* Node)
{
	delete Node;
}

// Postorder travelsal (후위 순회)를 이용한 데이터 회수
void SBT_DestroyTree(SBTNode* Node)
{
	if (Node == nullptr)
		return;
	SBT_DestroyTree(Node->Left);
	SBT_DestroyTree(Node->Right);
	SBT_DestroyNode(Node);
}

/* Preorder Travelsal (전위 순회) */
void SBT_PreorderPrintTree(SBTNode* Node)
{
	if (Node == nullptr)
		return;
	// 데이터 출력
	std::cout << Node->Data << std::endl;
	// 왼쪽 하위 트리 출력
	SBT_PreorderPrintTree(Node->Left);
	// 오른쪽 하위 트리 출력
	SBT_PreorderPrintTree(Node->Right);
}

/* Inorder Travelsal (중위 순회) */
void SBT_InorderPrintTree(SBTNode* Node)
{
	if (Node == nullptr)
		return;
	// 왼쪽 하위 트리 출력
	SBT_InorderPrintTree(Node->Left);
	// 데이터 출력
	std::cout << Node->Data << std::endl;
	// 오른쪽 하위 트리 출력
	SBT_InorderPrintTree(Node->Right);
}

/* Postorder Travelsal (후위 순회) */
void SBT_PostorderPrintTree(SBTNode* Node)
{
	if (Node == nullptr)
		return;
	// 왼쪽 하위 노드 출력
	SBT_PostorderPrintTree(Node->Left);
	// 오른쪽 하위 노드 출력
	SBT_PostorderPrintTree(Node->Right);
    // 데이터 출력
	std::cout << Node->Data << std::endl;
}

 

Test_BinaryTree.cpp

#include "BinaryTree.h"

int main(void)
{
	using namespace std;
	/* to create nodes */
	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');

	/* to add node to a tree*/
	A->Left  = B;
	B->Left  = C;
	B->Right = D;

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

	/* print tree */
	cout << "preorder..." << endl;
	SBT_PreorderPrintTree(A);
	cout << endl << endl;

	cout << "inorder..." << endl;
	SBT_InorderPrintTree(A);
	cout << endl << endl;

	cout << "postorder..." << endl;
	SBT_PostorderPrintTree(A);
	cout << endl << endl;

	/* delete tree memory */
	SBT_DestroyTree(A);

	return 0;
}

 

출력 결과

 

 

 

---