(C++) 자료구조 - 이진트리(Binary Tree) - 링크드리스트(Linked List)

안녕하세요 

오늘은 자료구조 이진트리에 관련된 포스팅 입니다!

이진트리 구현에 앞서 트리(Tree) 가 무엇인지 한번 훑고 가보도록 하겠습니다

 

1. 트리(Tree) 란?

 

트리는 스택(Stack) 큐(Queue) 와 다르게 비선형적 자료구조 입니다.

일렬로 쭉 이어진 선형적 구조와는 다르게 트리는 계층적 관계를 표현하는 자료구조 입니다.

마치 조직도의 계급이나 컴퓨터 폴더 안에 폴더 같은 느낌이 들지 않나요??

가지를 뻗어 나가는 모습때문에 Tree 라는 이름이 붙었다고 합니다.

어디에선가 들었는데 트리는 입출력 (스택, 큐) 자료구조라기보다 

무엇인가 표현하는 자료구조라고 생각하는게 좋다고 하네요!

 

2. 트리의 관련 용어

노드(Node), 버텍스(Vertex)

트리의 구성요소 (A,B,C,D,E,F,G)

간선(Edge), 링크(Link)

노드와 노드를 연결하는 연결선 (위 그림에서 파란선)

루트 노드(Root Node)

트리구조에서 최상위에 있는 노드 (A)

부모 노드 (Parent Node)

특정노드와 연결되어 있는 윗 노드 (Ex - D의 부모노드는 B)

자식 노드 (Child Node)

특정노드와 연결되어 있는 아래 노드 (Ex - B의 자식노드는 D, E)

형제 노드 (Sibling Node)

같은 부모를 둔 노드 (Ex - D는 E와 형제 노드)

단말 노드 (Terminal Node), 잎사귀 노드(Leaf Node)

아래로 다른 노드가 연결되어있지 않은 노드 (D,E,F,G)

비단말 노드 (Nonterminal Node), 내부 노드 (Internal Node)

아래로 다른 노드가 연결되어 있는 노드 (A,B,C)

레벨 (Level)

각 계층을 숫자를 표현 (루트 노드가 0 레벨)

높이 (Height), 깊이(Depth)

트리 구조의 계층 길이 (A 의 높이는 2, B의 높이는 1, D의 높이는 0)

 

3. 이진 트리(Binary Tree) 란?

간단히 말하면 모든 트리가 0개 혹은 최대 2개의 자식(왼쪽,오른쪽)노드를 갖는 트리를 말합니다.

그런 의미에서 이 그림도 이진트리입니다!

B 의 같은 경우 오른쪽 자식만, C 의 경우 왼쪽 자식만 가지고 있는데 왜 이진 이라는 말을 쓰냐구요!?

 

이런식으로 하나의 자식만 있는 부모 노드는 비어 있는 나머지 자식 노드를

비어있는 노드(공집합 노드)가 존재 하는 것으로 취급하여

이진트리가 될수 있습니다! 

그러면 이진트리 종류를 몇가지 설명하고 구현해보도록 할게요

 

3 - 1 포화 이진트리(Full Binary Tree)란?

위에서 보셧던 이 그림이 바로 포화 이진 트리입니다.

모든 레벨이 꽉 차 있는 트리의 모습을 포화 이진 트리라고 합니다!

 

3 - 2 완전 이진트리(Complete Binary Tree)란?

완전 이진트리는 모든 레벨이 꽉차 있는 건 아니지만

위에서부터 아래로, 왼쪽에서 부터 오른쪽으로 노드가 채워진 트리를 뜻합니다.

여기서 F 가 없어져도 완전 이진트리, F, E 가 없어져도 완전 이진트리가 됩니다! 

 

3 - 3 이진트리(Binary Tree)란?

이 그림을 다시 한번 보도록 하겠습니다.

모든 레벨이 꽉차 있지 않기 때문에 포화 이진트리는 아니구

왼쪽부터 채워져 있지 않기 때문에 완전 이진트리도 아닙니다.

그래서 그냥 이진트리가 되는 것이죠! 

 

4. 배열을 이용한 이진 트리 구현...?

.

본 포스팅에서는 배열을 이용하여 이진트리를 구현하지 않습니다!

그 이유에 대해서 설명하고 넘어가도록 할게요

이진 트리라 하면 특정노드에 대해 왼쪽 오른쪽 자식노드를 추가 할수 있어야 하는데

배열로 만들게 되면 메모리 공간의 낭비가 너무 심합니다.

예를 들어 

단 3개의 데이터를 저장 하는데 최소 7개의 배열을 선언해야합니다.

만약 C의 노드에서 자식노드가 늘어난다면.... 얼마나 낭비가 될지 아시겠나요??

그래서 보통 배열을 통한 트리 구현은 자료구조 힙(Heap)을 구현할때 사용합니다.

힙(Heap) 은 간단하게 말하면 위에서 말씀드린 완전 이진트리(Complete Binary Tree) 입니다.

힘의 구현은 아래 링크를 참조해주세요.

우선순위 큐(Priority Queue) - 힙(Heap) - 배열(Array)

마지막으로 다시 정리자면 차곡차곡 쌓이는 완전 이진트리가 아닌 그냥 이진트리는

배열로 구현하는 것이 적합하지 않다! 라고 말씀드릴 수 있을거 같습니다.

 

5. 연결리스트를 이용한 이진트리 구현

 

struct Node
{
	int data;		//데이터
	Node* left;		//왼쪽 자식노드
	Node* right;		//오른쪽 자식노드
};

class BinaryTreeLinkedList
{
public:
	BinaryTreeLinkedList();				//생성자
	~BinaryTreeLinkedList();			//소멸자
	
	Node* CreateNode();				//노드 생성
	bool GetData(Node* node, int& data);		//값 반환
	bool SetData(Node* node, int data);		//값 지정

	bool GetLeftNode(Node* parent, Node** node);	//노드의 왼쪽 자식노드 반환
	bool GetRightNode(Node* parent, Node** node);	//노드의 오른쪽 자식노드 반환

	bool SetLeftNode(Node* parent, Node* child);	//노드의 왼쪽 자식노드 지정
	bool SetRightNode(Node* parent, Node* child);	//노드의 오른쪽 자식노드 지정

	void PreorderPrint(Node* node);			//전위 순회
	void InorderPrint(Node* node);			//중위 순회
	void PostorderPrint(Node* node);		//후위 순회

	void RemoveNode(Node* node);			//노드 제거
};

 

링크드 리스트 이진트리의 헤더입니다.

 

노드 생성, 값 반환, 값 지정

노드의 왼쪽, 오른쪽 노드 지정 및 반환

노드 순회와 노드 제거 함수를 구현하였습니다.

다른 함수들은 넘어가고 순회에 대해서 설명하고 넘어 가도록 하겠습니다!

 

트리 구조는 선형 구조와는 다르다는 것을 알고 계시죠?!

쭉 읽으면 되는 선형구조와는 달리 트리 구조는 순회 방법에 따라 데이터를 읽는 순서가 다릅니다.

대표적인 순회 방법 3가지를 구현하였는데요.

각 순회 방법은 루트노드를 처음, 중간, 끝 언제 방문 하는지에 따라 구분할 수 있습니다,

 

1) 전위 순회

루트 노드를 가장 처음 방문 하는 전위 순회입니다.

A -> B -> D -> E -> C -> F -> G

순으로 방문 합니다.

부모 ㄱ , 왼쪽 ㄴ , 오른쪽 ㄷ 으로 봤을때 

ㄱ -> ㄴ -> ㄷ 순으로 반복되는 것을 볼 수 있습니다.

 

2) 중위 순회

루트 노드를 중간으로 방문 하는 중위 순회입니다.

루트 노드 기준 왼쪽 서브 노드를 모두 순회하고 루트 노드 방문, 오른쪽 서브 노드로 이동합니다.

D -> B -> E -> A -> F -> C -> G

순으로 방문 합니다.

부모 ㄱ , 왼쪽 ㄴ , 오른쪽 ㄷ 으로 봤을때 

ㄴ -> ㄱ -> ㄷ 순으로 반복되는 것을 볼 수 있습니다.

 

3) 후위 순회

루트 노드를 마지막으로 방문 하는 후위 순회입니다.

D -> E -> B -> F -> G -> C -> A

순으로 방문 합니다.

부모 ㄱ , 왼쪽 ㄴ , 오른쪽 ㄷ 으로 봤을때 

ㄴ -> ㄷ -> ㄱ 순으로 반복되는 것을 볼 수 있습니다.

 

#include "BinaryTreeLinkedList.h"
#include <iostream>

BinaryTreeLinkedList::BinaryTreeLinkedList()
{
	printf("생성자\n");
}

BinaryTreeLinkedList::~BinaryTreeLinkedList()
{
	printf("소멸자\n");
}

Node* BinaryTreeLinkedList::CreateNode()
{
	Node* newNode = new Node;
	newNode->left = NULL;
	newNode->right = NULL;
	return newNode;
}

bool BinaryTreeLinkedList::GetData(Node* node, int& data)
{
	if (node == NULL)
		return false;

	data = node->data;
	printf("GetData : %d\n", data);
	return true;
}

bool BinaryTreeLinkedList::SetData(Node* node, int data)
{
	if (node == NULL)
		return false;

	node->data = data;
	printf("SetData : %d\n", node->data);
	return true;
}

bool BinaryTreeLinkedList::GetLeftNode(Node* parent, Node** node)
{
	if (parent == NULL || parent->left == NULL)
	{
		*node = NULL;
		return false;
	}

	*node = parent->left;
	printf("GetLeftNode : %d\n", (*node)->data);
	return true;
}

bool BinaryTreeLinkedList::GetRightNode(Node* parent, Node** node)
{
	if (parent == NULL || parent->right == NULL)
	{
		*node = NULL;
		return false;
	}

	*node = parent->right;
	printf("GetRightNode : %d\n", (*node)->data);
	return true;
}

bool BinaryTreeLinkedList::SetLeftNode(Node* parent, Node* child)
{
	if (parent == NULL || child == NULL)
		return false;

	if (parent->left != NULL)				//이미 왼쪽 자식노드가 있으면
		RemoveNode(parent->left);			//왼쪽 자식노드를 지워준다.

	parent->left = child;
	printf("Set %d Node's LeftData : %d\n", parent->data, child->data);
	return true;
}

bool BinaryTreeLinkedList::SetRightNode(Node* parent, Node* child)
{
	if (parent == NULL || child == NULL)
		return false;

	if (parent->right != NULL)				//이미 오른쪽 자식노드가 있으면
		RemoveNode(parent->right);			//오른쪽 자식 노드를 지워준다.

	parent->right = child;
	printf("Set %d Node's RightData : %d\n", parent->data, child->data);
	return true;
}

void BinaryTreeLinkedList::PreorderPrint(Node* node)
{
	if (node == NULL)
		return;

	printf("Pre : %d\n", node->data);
	PreorderPrint(node->left);
	PreorderPrint(node->right);
}

void BinaryTreeLinkedList::InorderPrint(Node* node)
{
	if (node == NULL)
		return;

	InorderPrint(node->left);
	printf("In : %d\n", node->data);
	InorderPrint(node->right);
}

void BinaryTreeLinkedList::PostorderPrint(Node* node)
{
	if (node == NULL)
		return;

	PostorderPrint(node->left);
	PostorderPrint(node->right);
	printf("Post : %d\n", node->data);
}

void BinaryTreeLinkedList::RemoveNode(Node* node)
{
	if (node == NULL)
		return;

	RemoveNode(node->left);					//지우는 방식은 후위 순회방식으로
	RemoveNode(node->right);
	printf("Delete : %d\n", node->data);
	delete node;
}

링크드리스트 이진트리의 CPP 입니다.

 

노드를 반환하는 Get 함수 같은경우 이중 포인터를 사용하였습니다.

함수 반환 값을 노드로 지정하는 것보다 bool 로 성공 실패 여부를 반환하는 방식을

선호 하여 이중포인터를 사용하였구요.

왼쪽 오른쪽 노드로 Set 할때 이미 그 자리에 다른 노드가 있으면 

그 노드를 지워 주어 메모리 누수를 방지하였습니다!

각 순회 방식은 ㄱ ㄴ ㄷ 이 반복 되는 형태에 따라 재귀적으로 구현 하였고

RemoveNode 함수 같은 경우 후위 순회 방식으로 구현하였습니다.

#include <iostream>
#include "BinaryTreeLinkedList.h"

int main()
{
	BinaryTreeLinkedList* ListBinaryTree = new BinaryTreeLinkedList();

	Node* tempANode = ListBinaryTree->CreateNode();
	Node* tempBNode = ListBinaryTree->CreateNode();
	Node* tempCNode = ListBinaryTree->CreateNode();
	Node* tempDNode = ListBinaryTree->CreateNode();
	Node* tempENode = ListBinaryTree->CreateNode();
	Node* tempFNode;

	ListBinaryTree->SetData(tempANode, 1);
	ListBinaryTree->SetData(tempBNode, 2);
	ListBinaryTree->SetData(tempCNode, 3);
	ListBinaryTree->SetData(tempDNode, 4);
	ListBinaryTree->SetData(tempENode, 5);

	printf("\n");
	ListBinaryTree->SetLeftNode(tempANode, tempBNode);
	ListBinaryTree->SetRightNode(tempANode, tempCNode);
	ListBinaryTree->SetData(tempANode->left, 20);		//왼쪽 자식 노드 값 변경

	printf("\n");
	ListBinaryTree->GetRightNode(tempANode, &tempFNode);	//오른쪽 자식 노드 가져와서
	ListBinaryTree->SetData(tempFNode, 30);			//그 노드의 값 변경

	printf("\n");
	ListBinaryTree->GetLeftNode(tempANode, &tempFNode);
	ListBinaryTree->SetLeftNode(tempFNode, tempDNode);
	ListBinaryTree->SetRightNode(tempFNode, tempENode);

	printf("\n");

	int data;
	ListBinaryTree->GetData(tempANode, data);
	ListBinaryTree->GetData(tempBNode, data);
	ListBinaryTree->GetData(tempCNode, data);
	ListBinaryTree->GetData(tempDNode, data);
	ListBinaryTree->GetData(tempENode, data);
	ListBinaryTree->GetData(tempFNode, data);

	printf("\n");
	ListBinaryTree->PreorderPrint(tempANode);
	printf("\n");
	ListBinaryTree->InorderPrint(tempANode);
	printf("\n");
	ListBinaryTree->PostorderPrint(tempANode);

	printf("\n");
	ListBinaryTree->RemoveNode(tempANode);
	delete ListBinaryTree;
}

 

 

감사합니다.

 

다른 자료구조

단일 연결 리스트(Singly Linked List)

이중 연결 리스트(Doubly Linked List)

스택(Stack) - 배열(Array), 링크드리스트(Linked List)

큐(Queue) - 배열(Array), 링크드리스트(Linked List)

이진트리(Binary Tree) - 링크드리스트(Linked List)

우선순위 큐(Priority Queue) - 힙(Heap) - 배열(Array)