트리 (Tree)

트리란?

트리(Tree)는 계층 구조(Hierarchical Structure)로 자료를 저장하는 자료구조이다. 여기서 말하는 계층 구조란 트리를 구성하는 노드가 부모-자식(Parent-Child) 관계라는 의미이다. 즉 특정 부모 노드 하나에 여러 개의 자식 노드들이 연결되는 구조를 말한다. 이러한 구조로 노드들이 연결된 모습이 마치 마치 나무와 같아 트리라는 이름이 붙여졌다. 그래서 앞으로 살펴 볼 용어 중 나무의 부분에 대한 명칭을 가져온 것이 있다. 

 

예를 들어, 컴퓨터의 폴더 구조나 가족의 가계도, 직장의 조직도 등과 같이 계층적인 관계를 가진 자료를 표현하고 싶은 경우 선형 자료구조만으로 충분하지 않다. 트리는 이러한 계층적인 자료를 표현하는데 이용되는 자료구조이다.

 

컴퓨터 폴더 구조

---

트리의 용어들

트리와 관련된 용어들을 정의해보자. 그림과 같은 트리에서 알파뱃 A, B, C, ..., J를 노드(Node)라고 부른다.

트리는 한 개 이상의 노드로 이루어지는데, 계층적인 구조에서 가장 높은 곳에 있는 노드를 루트(Root) 노드라 부른다. 나머지 노드들은 서브 트리(Subtree)라고 부르는데, 루트의 다음 레벨에 있는 노드들은 서브 트리들의 루트가 된다.

 

그림에서 루트 노드는 A이며, 다른 노드들 {B, E, F, G}, {C, H}, {D, I, J} 3개의 집합으로 나누어진 노드들은 A의 서브 트리이다. 서브 트리인 {B, E, F, G}의 루트 노드는 다시 B가 되고 나머지 노드 3개는 서브트리가 된다. 

 

루트와 서브트리는 선으로 연결되는데, 이를 간선 또는 에지(Edge)라고 한다.

 

트리의 노드들 사이에는 인간의 관계와 같이 부모, 형제, 조상 및 자손의 관계가 존재한다. 그림을 예로 들면 A는 B의 부모 노드(Parent node)이고, 반대로 B는 A의 자식 노드(Child node)이며, B, C, D는 형제(Sibling)이다.

 

조상 노드(Ancestor node)는 임의의 노드 하위에서 루트 노드까지의 경로를 이루고 있는 노드들을 말하고, 자손 노드(Descendent node)는 임의의 노드 하위에 연결된 모든 노드들을 의미한다. 즉 어떤 노드의 서브 트리에 속하는 모든 노드들은 자손 노드이다. 

 

자식 노드가 없는 노드를 단말노드(Leaf node)라 한다.

 

어떤 노드가 가지고 있는 자식의 수를 그 노드의 차수(Degree)라고 한다. 그림에서 루트 노드는 자식 노드가 3개이므로 차수가 3이고, E, F, G, H, I, J와 같은 단말 노드들은 차수가 0이다.

 

트리의 차수는 트리가 가지고 있는 노드의 차수 중에서 가장 큰 값이다. 그림에서 A와 B노드의 차수가 최대 3이므로 전체 트리의 차수는 3이다.

 

레벨(Level)은 트리의 각층에 번호를 매기는 것으로서 루트의 레벨은 1이 되고 한 층씩 내려갈수록 1씩 증가한다. 

 

트리의 높이(Height)는 트리가 가지고 있는 최대 레벨을 말한다. 위의 트리의 높이는 3이다.

 

나무가 모이면 숲이 되듯이 트리들의 집합을 포레스트(Forest)라고 한다.

---

이진 트리

트리는 여러 종류가 존재한다. 하지만 여기서는 기본적으로 많이 사용하고 있는 이진 트리에 대해서 설명하려고 한다. 

 

이진 트리(Binary tree)는 모든 노드가 2개의 서브 트리를 갖는 트리이다. 모든 노드의 차수가 2 이하로, 최대 2개까지의 자식 노드를 가질 수 있는데, 자식들 사이에도 순서가 존재하므로 왼쪽 자식과 오른쪽 자식은 반드시 구별되어야 한다. 

 

이진 트리의 여러 모양

 

이진트리의 성질

• n개의 노드를 가진 트리는 n - 1개의 간선을 가진다. 그 이유는 루트노드를 제외한 트리의 모든 노드가 하나의 부모노드를 가지기 때문이다. 부모와 자식 간에는 하나의 간선만이 존재한다. 따라서 간선의 개수는 n - 1개이다.

노드의 개수 : 9개, 간선의 개수 : 8

 

• 높이가 h인 이진트리는 h개 이상, 2^h - 1개 이하의 노드를 가진다. 한 레벨에는 적어도 하나의 노드는 존재해야 하므로 높이가 h인 이진트리는 최소한 h개의 노드를 가져야 한다. 또한 하나의 노드는 최대 2개의 자식을 가질 수 있으므로 레벨 i에서의 최대 개수는 2^i - 1이 된다. 

• n개의 노드를 가지는 이진트리의 높이는 [log2(n+1)]이상이고 n이하이다. 먼저, 한 레벨에서 최소한 하나의 노드는 있어야 하므로 높이가 n을 넘을 수는 없다. 앞의 성질에서 높이 h의 이진트리가 가질 수 있는 노드의 최댓값은 2^h - 1이다. 따라서 n <= 2^h - 1의 부등식이 성립하고 양변에 log를 취하면 h >= log2(n+1)이 된다. h는 정수이므로 h >= [log2(n+1)]이 된다.

 

이진트리의 분류

이진트리는 형태에 따라 포화 이진트리, 완전 이진트리와 기타 이진트리로 분류할 수 있다.

 

• 포화 이진트리(Full binary tree)는 트리의 각 레벨에 노드가 꽉 차있는 이진트리이다. 즉 높이 k인 포화 이진트리는 정확하게 2^k - 1개의 노드를 가진다. 

• 완전 이진트리(Complete binary tree)는 높이가 k인 트리에서 레벨 1부터 k - 1까지는 노드가 모두 채워져 있고 마지막 레벨 k에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 트리이다. 마지막 레벨에서는 노드가 꽉차있지 않아도 되지만 중간에 빈곳이 없으면 안된다. 따라서 포화 이진트리는 완전 이진트리이지만 그 역은 성립하지 않는다. 

 

이진트리의 순회

트리를 순회(Traversal)한다는 것은 트리에 속하는 모든 노드를 한 번씩 방문하여 노드의 데이터를 목적에 맞게 처리하는 것을 의미한다. 예를 들어, 트리의 모든 항목들을 화면에 출력하기 위해서도 순회가 필요하다. 따라서 순회는 트리에서 가장 기본적인 연산이다. 

 

선형 자료구조에서는 모든 항목들이 순차적으로 들어 있으므로 순회 방법이 단순하지만 트리는 그렇지 않다. 기본적으로 순회의 간단한 구현을 위해 재귀함수를 사용한다.

 

이진트리의 표준 순회에는 전위, 중위, 후위의 3가지 방법이 있다. 이들은 루트와 왼쪽 서브 트리, 오른쪽 서브트리를 각각 어떤 순서로 방문하는가에 따라 구분된다. 루트를 방문하는 작업을 V, 왼쪽과 오른쪽 서브트리를 방문하는 작업을 각각 L과 R이라 하자 이진트리의 기본 순회에는 다음과 같이 3가지 방법이 있다.

 

• 전위 순회 : VLR

• 중위 순회 : LVR

• 후위 순회 : LRV

전위 순회(Preorder)

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

 

전위순회에서 루트노드의 방문을 마쳤다고 가정하자. 그러면 왼쪽 서브트리를 방문할 차례이다. 왼쪽 서브트리도 하나의 이진 트리이다. 따라서 전체 트리와 똑같은 방식으로 서브트리를 방문하게 된다. 즉 왼쪽 서브트리의 루트를 먼저 방문하고 왼쪽 서브트리의 왼쪽 서브트리를 그 다음에, 마지막 왼쪽 서브트리의 오른쪽 서브트리를 방문하면 된다. 모든 서브트리에 대해서 같은 알고리즘을 반복한다. 

 

코드로 구현하면 다음과 같다.

void PreOrder(NODE* n)
{
	if (nullptr == n)
		return;

	cout << "[" << n->data << "] ";
	PreOrder(n->left);
	PreOrder(n->right);
}

 

중위 순회(Inorder)

중위 순회에서는 왼쪽 서브트리, 루트, 오른쪽 서브트리 순으로 방문한다.

 

코드로 구현하면 다음과 같다.

void InOrder(NODE* n)
{
	if (nullptr == n)
		return;

	InOrder(n->left);
	cout << "[" << n->data << "] ";
	InOrder(n->right);
}

 

후위 순회(Postorder)

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

 

코드로 구현하면 다음과 같다.

void PostOrder(NODE* n)
{
	if (nullptr == n)
		return;
        
	PostOrder(n->left);
	PostOrder(n->right);
	cout << "[" << n->data << "] ";
}

 

레벨 순회(Level order)

레벨 순회는 각 노드를 레벨 순으로 검사하는 방법이다. 루트 노드의 레벨이 1이고 아래로 내려갈수록 레벨은 증가한다. 동일한 레벨의 경우에는 좌에서 우로 방문한다.

 

레벨 순회는 큐를 사용한다. 레벨 순회는 큐에서 노드를 하나 꺼내 방문하고 그 자식들을 큐에 삽입한다. 삽입에도 순서가 있다. 왼쪽 자식을 먼저 오른쪽 자식을 그 다음에 처리한다. 물론 자식이 없으면 삽입하지 않는다. 이 과정은 큐가 공백일때까지 반복한다. 처음에는 큐에 루트 노드만 들어 있다.

레벨 순회의 과정

그림을 살펴보면 처음에 루트노드 1을 큐에 삽입한다. 그리고 큐가 빌때까지 반복을 시작한다. 1을 꺼내고 1의 자식노드 2, 3을 큐에 넣는다. 그리고 2를 꺼내면서 4, 5를 넣고 3을 꺼내면서 6, 7을 넣는다. 4, 5, 6, 7은 자식 노드가 없으므로 큐에 추가없이 그냥 꺼내어진다. 그래서 레벨순회의 순서는 1, 2, 3, 4, 5, 6, 7이 된다.

 

코드로 표현하면 다음과 같다.

void LevelOrder(NODE* root)
{
	if (nullptr == root)
		return;

	// STL Queue를 사용
	queue<NODE*> q;
	q.push(root);
	while (!q.empty())
	{
		NODE* node = q.front();
		if (nullptr != node)
		{
			cout << "[" << node->data << "] ";
			q.push(node->left);
			q.push(node->right);
		}
		q.pop();
	}
}

 

이진트리의 연산

노드 개수 구하기

이진트리의 전체 노드의 개수를 구하기 위해서는 모든 노드의 순회가 필요하다. 그렇기 때문에 재귀함수를 사용한다. 어떤 노드를 루트로 하는 이진트리의 노드의 개수는 왼쪽 서브트리의 노드 개수와 오른쪽 서브트리의 노드 개수에 루트노드를 더하면 된다. 이것을 후위순회 방식으로 계산한다. 

 

코드로 표현하면 다음과 같다.

int CountNode(NODE* n)
{
	if (nullptr == n) 
		return 0;
	return 1 + CountNode(n->left) + CountNode(n->right);
}

 

단말 노드 개수 구하기

단말 노드의 개수를 세기 위해서도 트리의 순회를 사용해야 한다. 만약 왼쪽 자식과 오른쪽 자식이 없다면 단말 노드이고, 1을 반환하면 된다. 아니면 비단말 노드이므로 각각의 서브트리에 대하여 순환 호출하여 반환되는 두 값을 더해 반환하면 된다.

 

코드로 표현하면 다음과 같다.

int CountLeaf(NODE* n)
{
	// 리프노드의 갯수
	if (nullptr == n) 
		return 0;
	if (nullptr == n->left && nullptr == n->right)
		return 1;
	else
		return CountLeaf(n->left) + CountLeaf(n->right);
}

 

트리의 높이 구하기

트리의 높이 또한 기본적으로 후위 순회 방법을 이용한다. 먼저 루트의 각 서브 트리에 대해 순환호출을 통해 높이를 구해야 현재 트리의 높이를 계산할 수 있다. 트리의 높이는 왼쪽 서브트리와 오른쪽 서브트리 중에서 더 높은 트리를 먼저 찾고, 이 트리의 높이에 1을 더한 값이다.

 

코드로 표현하면 다음과 같다.

int BinaryTree::CalcHeight(NODE* n)
{
	if (nullptr == n)
		return 0;
	return 1 + max(CalcHeight(n->left), CalcHeight(n->right));
}

---

이진트리의 구현

이제 위 알고리즘 들을 바탕으로 이진트리를 코드로 구현해보도록 하겠다. 배열과 연결리스트 구현 방식 두가지로 나뉘는데, 연결리스트를 사용하여 구현한다.

 

미리 컴파일하는 헤더

// pch.h

#ifndef PCH_H
#define PCH_H

// 여기에 미리 컴파일하려는 헤더 추가
#include <iostream>
#include <queue>
using namespace std;

#include "DataType.h"
#include "Macro.h"

#endif //PCH_H

STL 큐를 쓰기 위해 queue 라이브러리를 추가하였다. 그리고 전역으로 사용할 구조체와 템플릿 함수를 위해 DataType.h와 Macro.h를 추가하였다.

 

DataType.h

#pragma once

typedef char DATA;
typedef struct _Node
{
	DATA data;
	_Node* left;
	_Node* right;
}NODE;

데이터 내용은 char값 하나이며 자식노드간의 연결을 위한 왼쪽, 오른쪽 노드 포인터가 포함된다.

 

Macro.h

#pragma once

template<typename T>
inline void SAFE_DELETE(T& value)
{
	if (nullptr != value)
	{
		delete value;
		value = nullptr;
	}
}

안전한 동적할당 해제를 위한 인라인 템플릿 함수를 선언하였다.

 

BinaryTree 클래스

// BinaryTree.h

#pragma once
class BinaryTree
{
public:
	BinaryTree();
	~BinaryTree();
public:
	bool IsEmpty() { return (nullptr == m_Root); }
public:
	void InOrder(NODE* root);
	void PreOrder(NODE* root);
	void PostOrder(NODE* root);
	void LevelOrder(NODE* root);
public:
	int CountNode(NODE* root);
	int CountLeaf(NODE* root);
	int CalcHeight(NODE* root);
public:
	NODE* SetRoot(DATA data, NODE* left, NODE* right);
	NODE* CreateNode(DATA data, NODE* left, NODE* right);
private:
	void ClearAll(NODE* root);
private:
	NODE* m_Root = nullptr;
};

루트 노드를 멤버 변수로 가지고 있다. 그리고 인스턴스에 대한 호출로 부터 멤버 변수에 대한 데이터를 세팅한다. 앞서 봤던 순회 함수들과 연산 함수들이 포함되어 있다.

 

// BinaryTree.cpp

#include "pch.h"
#include "BinaryTree.h"

BinaryTree::BinaryTree()
{
	
}

BinaryTree::~BinaryTree()
{
	ClearAll(m_Root);
}

void BinaryTree::InOrder(NODE* root)
{
	if (nullptr == root)
		return;
	// 중위 순회
	InOrder(root->left);
	cout << "[" << root->data << "] ";
	InOrder(root->right);
}

void BinaryTree::PreOrder(NODE* root)
{
	if (nullptr == root)
		return;
	// 전위 순회
	cout << "[" << root->data << "] ";
	PreOrder(root->left);
	PreOrder(root->right);
}

void BinaryTree::PostOrder(NODE* root)
{
	if (nullptr == root)
		return;
	// 후위 순회
	PostOrder(root->left);
	PostOrder(root->right);
	cout << "[" << root->data << "] ";
}

void BinaryTree::LevelOrder(NODE* root)
{
	if (nullptr == root)
		return;

	// 큐를 이용한 레벨 순회
	queue<NODE*> q;
	q.push(root);
	while (!q.empty())
	{
		NODE* node = q.front();
		if (nullptr != node)
		{
			cout << "[" << node->data << "] ";
			q.push(node->left);
			q.push(node->right);
		}
		q.pop();
	}
}

int BinaryTree::CountNode(NODE* root)
{
	// 노드의 갯수
	if (nullptr == root) 
		return 0;
	return 1 + CountNode(root->left) + CountNode(root->right);
}

int BinaryTree::CountLeaf(NODE* root)
{
	// 리프노드의 갯수
	if (nullptr == root) 
		return 0;
	if (nullptr == root->left && nullptr == root->right)
		return 1;
	else
		return CountLeaf(root->left) + CountLeaf(root->right);
}

int BinaryTree::CalcHeight(NODE* root)
{
	// 높이 구하기
	if (nullptr == root)
		return 0;
	return 1 + max(CalcHeight(root->left), CalcHeight(root->right));
}

NODE* BinaryTree::SetRoot(DATA data, NODE* left, NODE* right)
{
	// 루트노드 세팅
	m_Root = new NODE;
	m_Root->data = data;
	m_Root->left = left;
	m_Root->right = right;

	return m_Root;
}

NODE* BinaryTree::CreateNode(DATA data, NODE* left, NODE* right)
{
	// 노드를 만들어 트리에 세팅
	NODE* newNode = new NODE;
	newNode->data = data;
	newNode->left = left;
	newNode->right = right;

	return newNode;
}

void BinaryTree::ClearAll(NODE* root)
{
	// 모두 삭제
	// 후위순회 순으로 삭제한다
	if (nullptr == root)
		return;

	ClearAll(root->left);
	ClearAll(root->right);
	SAFE_DELETE(root);
}

 

main()

아래 그림과 같은 구조의 트리를 만들어 보도록 하겠다. 그리고 이 이진트리의 전위, 중위, 후위 순회로 알파벳을 출력하며, 노드의 총 개수, 단말노드 개수, 그리고 최고 높이를 출력한다.

#include "pch.h"
#include "BinaryTree.h"

int main()
{
	BinaryTree tree;
	NODE *a, *b, *c, *d, *e, *f, *g;
	NODE* root;

	// 단말 노드
	d = tree.CreateNode('D', nullptr, nullptr);
	f = tree.CreateNode('F', nullptr, nullptr);
	g = tree.CreateNode('G', nullptr, nullptr);
	//
	b = tree.CreateNode('B', d, f);
	c = tree.CreateNode('C', g, nullptr);
	a = tree.CreateNode('A', b, c);
	e = tree.CreateNode('E', nullptr, nullptr);
	root = tree.CreateNode('R', a, e);

	cout << "In-Order : "; tree.InOrder(root); cout << endl;
	cout << "Pre-Order : "; tree.PreOrder(root); cout << endl;
	cout << "Post-Order : "; tree.PostOrder(root); cout << endl;
	cout << "Level-Order : "; tree.LevelOrder(root); cout << endl<< endl;

	cout << "Node-Count : " << tree.CountNode(root); cout << endl;
	cout << "Leaf-Count : " << tree.CountLeaf(root); cout << endl;
	cout << "Max Height : " << tree.CalcHeight(root); cout << endl;
}

 

출력 값