[C++/자료구조] 이진트리(Binary Tree)

Tree : 트리

- 특징

1) 루트 노드를 제외한 모든 노드는 부모 노드가 있다
2) 하나의 루트 노드를 가진다
3) 노드는 0개 이상의 자식 노드를 가진다
4) 순환 구조를 가지지 않는다

- 장점

1) 계층적인 구조를 표현할 수 있으며, 검색과 삽입, 삭제가 용이하다
- 단점
1) 불균형한 트리는 탐색 시간이 느려진다

Complete Binary Tree : 완전 이진 트리

- 특징

1) 모든 노드가 꽉 찬 이진 트리
2) 마지막 레벨을 제외한 모든 레벨이 꽉 차있어야 한다
3) 마지막 레벨은 왼쪽부터 차레로 채워진다
4) 모든 노드는 왼쪽에서 오른쪽으로 채워져야 한다

- 장점

1) 배열로 구현할 때 간단하게 구현할 수 있다
- i번째 노드의 왼쪽 자식 노드는 2i 번째 노드
- i번째 노드의 오른쪽 자식 노드는 2i + 1번째 노드
- i번째 노드의 부모 노드는 i/2 번째 노드
2) 탐색 시간이 O(log n)으로 매우 빠르다
3) 노드의 개수가 적어 공간 복잡도가 적다

- 단점

1) 삽입과 삭제 시 노드의 이동이 많아서 시간 복잡도가 높다

모두 꽉 차있는 트리 = 포화 이진 트리
마지막 레벨에서 하나라도 빠져있는 트리 = 완전 이진 트리

 

트리의 형태에 따라 다양하게 나뉘는 모습

BinaryTree.h

#pragma once

void DoBinaryTree();

struct BinaryTreeNode
{
	BinaryTreeNode(DataType data)
		: Data(data), LeftChild(nullptr), RightChild(nullptr) {}

	DataType Data;
	BinaryTreeNode* LeftChild;
	BinaryTreeNode* RightChild;
};

class BinaryTree
{
public:
	BinaryTree() : Root(nullptr) {}
	~BinaryTree();

	void Insert(DataType data);
	void Remove(DataType data);

	void PreOrder();	// 전위 순회
	void InOrder();		// 중위 순회
	void PostOrder();	// 후위 순회

	void PrintHierarchy();	// 계층 구조 출력

private:
	// 노드 삭제 및 반환
	BinaryTreeNode* Remove(BinaryTreeNode* node, DataType data);
	// 노드 삭제 후 자식 노드 재배치
	BinaryTreeNode* RemoveNode(BinaryTreeNode* node);
	// 최솟값 함수
	BinaryTreeNode* FindMin(BinaryTreeNode* node);

	void PreOrder(BinaryTreeNode* node);
	void InOrder(BinaryTreeNode* node);
	void PostOrder(BinaryTreeNode* node);

	void DestroyTree(BinaryTreeNode* node);

	void PrintHierarchy(BinaryTreeNode* node, std::string indent, bool last);

private:
	BinaryTreeNode* Root;
};

BinaryTree.cpp

#include "../../stdafx.h"
#include "BinaryTree.h"

BinaryTree::~BinaryTree()
{
	// 재귀적으로 탐색하여 노드를 삭제하는 함수를 호출
	DestroyTree(Root);
}

void BinaryTree::Insert(DataType data)
{
	// 새 노드 생성
	BinaryTreeNode* newNode = new BinaryTreeNode(data);

	// 루트 노드가 없으면 새 노드를 루트 노드로 지정
	if (Root == nullptr)
	{
		Root = newNode;
		return;
	}

	// 루트 노드부터 시작하여, 새 노드를 삽입할 위치를 찾음
	BinaryTreeNode* curNode = Root;
	while (true)
	{
		// 현재 노드보다 작은 값이면
		if (data < curNode->Data)
		{
			// 왼쪽 노드가 비어있으면
			if (curNode->LeftChild == nullptr)
			{
				// 새 노드를 그 자리에 삽입
				curNode->LeftChild = newNode;
				return;
			}
			// 비어있지 않으면, 왼쪽 자식 노드를 현재 노드로 바꾸고 반복
			curNode = curNode->LeftChild;
		}

		// 현재 노드보다 큰 값이면
		else
		{
			// 오른쪽 자식 노드가 비어있으면
			if (curNode->RightChild == nullptr)
			{
				// 새 노드를 그 자리에 삽입
				curNode->RightChild = newNode;
				return;
			}
			// 비어있지 않으면, 오른쪽 자식 노드를 현재 노드로 바꾸고 반복
			curNode = curNode->RightChild;
		}
	}
}

void BinaryTree::Remove(DataType data)
{
	// 트리에서 데이터를 삭제하기 위해 루트 노드부터 재귀적으로 탐색하여
	// 노드를 삭제하는 함수를 호출
	Root = Remove(Root, data);
}

void BinaryTree::PreOrder()
{
	PreOrder(Root);
	cout << endl;
}

void BinaryTree::InOrder()
{
	InOrder(Root);
	cout << endl;
}

void BinaryTree::PostOrder()
{
	PostOrder();
	cout << endl;
}

void BinaryTree::PrintHierarchy()
{
	if (Root == nullptr)
		cout << "EmptyTree" << endl;
	else
		PrintHierarchy(Root, "", true);
}

BinaryTreeNode* BinaryTree::Remove(BinaryTreeNode* node, DataType data)
{
	// 노드가 비어있으면 nullptr 반환
	if (node == nullptr)
		return nullptr;

	// 현재 노드의 데이터가 삭제할 데이터와 같다면 삭제를 실행
	if (data == node->Data)
		return RemoveNode(node);
	// 삭제할 데이터가 현재 노드보다 작다면
	else if (data < node->Data)
	{
		// 왼쪽 자식 노드에서 삭제를 수행
		node->LeftChild = Remove(node->LeftChild, data);
		return node;
	}
	// 삭제할 데이터가 현재 노드보다 크다면
	else
	{
		// 오른쪽 자식 노드에서 삭제를 수행
		node->RightChild = Remove(node->RightChild, data);
		return node;
	}
}

BinaryTreeNode* BinaryTree::RemoveNode(BinaryTreeNode* node)
{
	// 삭제할 노드가 leaf 노드인 경우
	if (node->LeftChild == nullptr && node->RightChild == nullptr)
	{
		// 노드 삭제 후 부모 노드에서 해당 노드 연결을 끊기 위해 nullptr 리턴
		delete node;
		return nullptr;
	}
	// 삭제할 노드에 자식이 하나가 있는 경우
	else if (node->LeftChild == nullptr || node->RightChild == nullptr)
	{
		// 삭제할 노드의 자식 노드 중 존재하는 자식 노드를 찾아 target으로 설정
		BinaryTreeNode* target = (node->LeftChild != nullptr) ? 
			node->LeftChild : node->RightChild;

		// 노드 삭제
		delete node;
		// 부모 노드에서 해당 노드 연결을 끊고,
		// 존재하는 자식 노드와 연결하기 위해서 리턴
		return target;
	}
	// 삭제할 노드에 자식이 둘 있는 경우
	else
	{
		// 삭제할 노드의 오른쪽 서브트리에서 가장 작은 값을 가진 노드를 찾아서 대체
		BinaryTreeNode* target = FindMin(node->RightChild);
		// 삭제할 노드의 데이터를 찾은 노드의 데이터로 변경
		node->Data = target->Data;
		// 노드를 삭제하고, 삭제된 노드의 오른쪽 자식 노드와 연결
		node->RightChild = Remove(node->RightChild, target->Data);
		return node;
	}
}

BinaryTreeNode* BinaryTree::FindMin(BinaryTreeNode* node)
{
	// 노드의 왼쪽 자식이 없을 때까지 반복해서 왼쪽 자식으로 이동
	while (node->LeftChild != nullptr)
		node = node->LeftChild;

	// 가장 작은 값을 가진 노드를 반환
	return node;
}

// 전위 순회 (현재 노드 -> 왼쪽 자식 -> 오른쪽 자식)
void BinaryTree::PreOrder(BinaryTreeNode* node)
{
	if (node)
	{
		cout << node->Data << " ";
		PreOrder(node->LeftChild);
		PreOrder(node->RightChild);
	}
}

// 중위 순회 (왼쪽 자식 -> 현재 노드 -> 오른쪽 자식)
void BinaryTree::InOrder(BinaryTreeNode* node)
{
	if (node)
	{
		InOrder(node->LeftChild);
		cout << node->Data << " ";
		InOrder(node->RightChild);
	}
}

// 후위 순회 (왼쪽 자식 -> 오른쪽 자식 -> 현재 노드)
void BinaryTree::PostOrder(BinaryTreeNode* node)
{
	if (node)
	{
		PostOrder(node->LeftChild);
		PostOrder(node->RightChild);
		cout << node->Data << " ";
	}
}

void BinaryTree::DestroyTree(BinaryTreeNode* node)
{
	if (node)
	{
		DestroyTree(node->LeftChild);
		DestroyTree(node->RightChild);
		delete node;
	}
}

void BinaryTree::PrintHierarchy(BinaryTreeNode* node, std::string indent, bool last)
{
	if (node == nullptr)
		return;
	//출력할 노드의 위치와, 마지막 노드인지 여부에 따라 출력할 문구 설정
		cout << indent;
	if (last)
	{
		//마지막 노드인 경우 출력
			cout << "└─ ";
		//indent에 2칸 공백 추가
			indent += "  ";
	}
	else
	{
		//마지막 노드가 아닌 경우 출력
			cout << "├─ ";
		//indent에 |와 공백 추가
			indent += "| ";
	}
	//현재 노드의 값을 출력
		cout << node->Data << endl;

	//오른쪽 자식 노드를 방문하여 계층 구조를 출력
		PrintHierarchy(node->RightChild, indent, node->LeftChild == nullptr);
	//왼쪽 자식 노드를 방문하여 계층 구조를 출력
		PrintHierarchy(node->LeftChild, indent, true);
}