트리의 개념과 설명 - 8장

트리

앞서 배운 자료구조들(리스트,스택,큐,덱등)은 모두 선형 자료구조이다.

이번에 배울 트리는 비선형 자료구조.

 

트리는 계층적 관계를 표현하는 자료구조이다.

 

 

트리와 관련된 용어를 정의해본다.

1. 노드 : node

- 트리의 구성요소에 해당하는 A,B,C,D,E,F등 

 

2. 간선 : edge

- 노드와 노드를 연결하는 선

 

3. 루트 노드 : root node

- 트리 구조에서 최상위에 존재하는 노드 (위 그림에선 A노드)

 

4. 단말 노드 : terminal node

- 아래로 또 다른 노드가 연결되어 있지 않은 E,F,C,D와 같은 노드. (다른말로 리프(leaf)노드라고도 함)

 

5. 내부 노드 : internal node

- 단말 노드를 제외한 모든 노드로 A, B와 같은 노드. (비단말 노드라고도 불린다)

 

6. 형제 노드 : sibling NODE

- 같은 부모를 가지는 노드들 위 그림에선 각 (B,C,D)와 (E,F)

 

이진 트리(Binary Tree)와 서브 트리(Sub Tree)

 

서브 트리. 구조상으로 A노드를 기준으로 왼쪽에도 트리가 형성이 되어있고 오른쪽에도 트리가 형성이 되어있다.

이것을 서브 트리. B를 예로들어 재귀적으로 들어가면 B는 루트노드이고 (D,I,J)서브 트리와 (E,K)서브 트리가 형성이 된다.

-> 구조가 재귀적임

 

이진 트리. 간단히 설명하면 자식 노드를 최대 2개까지 가질 수 있는 트리를 이진 트리라고 한다.

(이 규칙은 서브 트리도 지켜져야한다)

 

자식 노드가 최대 2개만 넘지않는다면 

위 그림의 트리도 이진 트리라는 것.

 

포화 이진 트리(Full Binary Tree)와 완전 이진 트리(Complete Binary Tree)

 

설명하기에 앞서 앞서 트리에 대한 용어가 몇가지 더 있다. 바로 레벨과 높이.

트리에서 각 층별로 숫자를 매겨 이를 트리의 '레벨'이라 하고,

트리의 최고 레벨을 가리켜 '높이'라고 표현한다.

 

이 책에서는 레벨과 높이를 0부터 세지만 1부터 시작하여 세는경우도 많다.

 

이제 포화 이진트리를 설명한다.

이렇듯. 최대 레벨까지 형성된 트리에서 노드가 가득 찬 구조를 포화 이진 트리라고 말한다.

 

다음은 완전 이진트리

완전 이진트리. 노드가 위에서 아래로, 그리고 왼쪽에서 오른쪽의 순서대로 채워지는 트리

(힙(heap)이라는 자료구조가 이 완전 이진트리를 채택)

그리고 왼쪽에서 오른쪽의 순서대로 채워지는 트리이기에 배열로 구현하기가 편하다.

(각 노드의 저장되는 순서가 배열의 인덱스에 적용이 가능하므로)

 

포화 이진트리는 완전 이진트리라고 부를 수 있다. 하지만 그 역은 성립하지 않는다.

 

정리 

이진트리 - 최대 자식노드의 수가 2개까지

포화 이진트리 - 최대 레벨까지 노드가 가득 찬 트리

완전 이진트리 - 위에서 아래로, 왼쪽에서 오른쪽으로 순서대로 노드가 채워진 트리

 

코드를 통해 간단하게 이진 트리의 클래스를 정의해본다.

#pragma once

// 간단하게 데이터는 int형을 담는다.
class BinaryTree // 이진 트리의 노드는 규칙에 의해 그 자체가 이진트리를 표현.
{
public:
	BinaryTree() = delete;
	BinaryTree(int data);
	~BinaryTree();
	int GetData() const;
	void MakeLeftSubTree(BinaryTree* leftNode);
	void MakeRightSubTree(BinaryTree* rightNode);
	BinaryTree* GetLeftSubTreeOrNull();
	BinaryTree* GetRightSubTreeOrNull();
private:
	BinaryTree* m_left; // 왼쪽 자식
	BinaryTree* m_right; // 오른쪽 자식
	int			m_data;
};

 

아직은 부족한 cpp코드. (서브트리의 삭제가 불가능하다.)

#include "BinaryTree.h"

BinaryTree::BinaryTree(int data) : m_left(nullptr),m_right(nullptr),m_data(data)
{

}
BinaryTree::~BinaryTree()
{
	// 생성한 노드개체 소멸자 호출시점에서 트리에서 모든 노드삭제.
}

int BinaryTree::GetData() const
{
	return m_data;
}

void BinaryTree::MakeLeftSubTree(BinaryTree* leftNode)
{
	if (this->m_left == nullptr)
		this->m_left = leftNode;
	else // 삭제 아직 부족한코드.
		delete this->m_left;
}
void BinaryTree::MakeRightSubTree(BinaryTree* rightNode)
{
	if (this->m_right == nullptr)
		this->m_right = rightNode;
	else // 삭제 아직 부족한코드.
		delete this->m_right;
}

BinaryTree* BinaryTree::GetLeftSubTreeOrNull()
{
	if (this->m_left != nullptr)
		return this->m_left;
	else
		return nullptr;
}
BinaryTree* BinaryTree::GetRightSubTreeOrNull()
{
	if (this->m_right != nullptr)
		return this->m_right;
	else
		return nullptr;
}

 

트리에 존재하는 노드 하나하나는 스택에 생성했다면 함수를 벗어나면 삭제되고

힙에 할당된 노드는 delete를 호출한다.

 

이진 트리의 순회(Traversal)

 

위 코드의 문제는 트리의 노드를 제거할 방법이 없다는 것. 트리의 노드를 전부 제거하거나,

왼쪽 서브트리를 다른 서브트리(하나의 노드는 예외)로 다시 맞출때. 기존의 서브트리를 제거(delete)해줄 필요성이 존재한다.

 

이럴 때 사용되는 방법이 순회방법.

 

이진트리의 순회 세가지 방법.

 

1. 전위 순회(Preorder Traversal) - 루트 노드를 먼저 순회

2. 중위 순회(Inorder Traversal)   - 루트 노드를 중간에 순회

3. 후위 순회(Postorder Traversal) - 루트 노드를 마지막에 순회 -> 제거를 위해 사용되는 순회

 

앞서 설명할 때 이진 트리는 재귀적인 구조를 가진다고 하였다.(서브트리)

 

간단하게 중위 순회의 코드를 보면서 그 결과를 확인해본다.

void InorderTraverse(BinaryTree* bt) // 중위순회
{
	if (bt == nullptr)
		return;

	InorderTraverse(bt->GetLeftSubTreeOrNull()); // 1단계 왼쪽 노드의 방문.
	cout << bt->GetData() << endl; // 2단계 루트노드 방문.
	InorderTraverse(bt->GetRightSubTreeOrNull()); // 3단계 오른쪽 노드 방문.
}

 

트리는 A가 루트노드이며 루트 노드를 기준으로 왼쪽으로 하나씩 서브트리를 형성.

 

중위 순회결과 : 20 15 10 5. 가 제대로 잘 나왔다는 것을 알 수 있다.

 

전위 순회, 후위순회도 간단하다. 중위 순회의 함수에서 자신을 호출하고 각각 왼쪽,오른쪽주소를 넘기는 함수사이에서

중간에 껴있으니 루트노드를 중간에 순회했다고 보면된다.

(왼쪽 노드를 계속 내려가다가 NULL이면 돌아오고 출력.)

 

그럼 이제 이진 트리에서 노드를 삭제하기 위한 코드를 추가 해본다.

#pragma once

// 간단하게 데이터는 int형을 담는다.
class BinaryTree // 이진 트리의 노드는 규칙에 의해 그 자체가 이진트리를 표현.
{
public:
	BinaryTree() = delete;
	BinaryTree(int data);
	~BinaryTree();
	int GetData() const;
	void MakeLeftSubTree(BinaryTree* leftNode);
	void MakeRightSubTree(BinaryTree* rightNode);
	BinaryTree* GetLeftSubTreeOrNull();
	BinaryTree* GetRightSubTreeOrNull();
	static void DeleteTree(BinaryTree* bt); // 추가
private:
	BinaryTree* m_left; // 왼쪽 자식
	BinaryTree* m_right; // 오른쪽 자식
	int			m_data;
};

cpp코드

#include "BinaryTree.h"
#include <iostream>
using namespace std;
int NodeDelcount = 0;

BinaryTree::BinaryTree(int data) : m_left(nullptr),m_right(nullptr),m_data(data)
{

}
BinaryTree::~BinaryTree()
{

}

int BinaryTree::GetData() const
{
	return m_data;
}

void BinaryTree::MakeLeftSubTree(BinaryTree* leftNode)
{
	if (this->m_left == nullptr)
		this->m_left = leftNode;
	else // 삭제(보완)
	{
		DeleteTree(this->m_left);
		this->m_left = leftNode; // 삭제 후 연결
	}
}
void BinaryTree::MakeRightSubTree(BinaryTree* rightNode)
{
	if (this->m_right == nullptr)
		this->m_right = rightNode;
	else // 삭제 (보완)
	{
		DeleteTree(this->m_right);
		this->m_right = rightNode; // 삭제 후 연결
	}
}

BinaryTree* BinaryTree::GetLeftSubTreeOrNull()
{
	if (this->m_left != nullptr)
		return this->m_left;
	else
		return nullptr;
}
BinaryTree* BinaryTree::GetRightSubTreeOrNull()
{
	if (this->m_right != nullptr)
		return this->m_right;
	else
		return nullptr;
}

void BinaryTree::DeleteTree(BinaryTree* bt)
{
	if (bt == nullptr)
		return;

	DeleteTree(bt->m_left);
	DeleteTree(bt->m_right);
	cout << bt->GetData() << "삭제!" << endl;
	delete bt;
}