트리 기초

 

트리란? 

기존의 그래프와 비슷하게 노드와 가지(edge)로 이루어져 있는 트리 알고리즘은 그래프와 다르게 계층이 나뉘어져 있는게 특징이다. 그래프의 노드는 동등한 입장이라면, 트리는 노드간의 계층이 존재하여 부모 혹은 루트로 이루어져 있는걸 볼 수 있다. 

 

이는 조직도 혹은 폴더 등에서 많이 볼 수 있는 구조이다.

 

 

• Root Node : 트리 구조에서 최상위에 존재하는 A와 같은 노드
• Node : 트리의 구성요소에 해당하는 A,B,C,D,E,F,G,H,I,J와 같은 요소
• Edge : 노드와 노드를 연결하는 연결설
• Terminal Node(Leaf Node) : 밑으로 또 다른 노드가 연결되어 있지 않은 H,I,J,F,G와 같은 노드
• Sub-Tree : 큰 트리(전체)에 속하는 작은 트리
• Level : 트리에서 각 층별로 숫자를 매김
• Height : 트리의 최고 레벨 (3)

 

 

구현하면서 새로운 지식을 알게 되었는데, 자기 자신을 가리키는 포인터를 사용할 때, 동적할당 및 해제를 자동으로 해주는 기능을 처음 알게 되었다.

 

using NodeRef = shared_ptr<struct Node>;

struct Node
{
	string data;
	vector<NodeRef> children;
};

 

여기서 shared_ptr<>는 스마트 포인터라고 불리는데,

 

스마트 포인터(smart pointer)

C++ 프로그램에서 new 키워드를 사용하여 동적으로 할당받은 메모리는, 반드시 delete 키워드를 사용하여 해제해야 합니다.

C++에서는 메모리 누수(memory leak)로부터 프로그램의 안전성을 보장하기 위해 스마트 포인터를 제공하고 있습니다.

스마트 포인터(smart pointer)란 포인터처럼 동작하는 클래스 템플릿으로, 사용이 끝난 메모리를 자동으로 해제해 줍니다.

 

자세한 내용

http://www.tcpschool.com/cpp/cpp_template_smartPointer

코딩교육 티씨피스쿨

을 참고하자.

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
using namespace std;

using NodeRef = shared_ptr<struct Node>;

struct Node
{
	Node() {}
	Node(const string& data) : data(data) {}

	string data;
	vector<NodeRef> children;
};


NodeRef CreateTree()
{
	NodeRef root = make_shared<Node>("R1 개발실");
	{
		NodeRef node = make_shared<Node>("디자인팀");
		root->children.push_back(node);
		{
			NodeRef leaf = make_shared<Node>("전투");
			node->children.push_back(leaf);
		}
		{
			NodeRef leaf = make_shared<Node>("경제");
			node->children.push_back(leaf);
		}
		{
			NodeRef leaf = make_shared<Node>("스토리");
			node->children.push_back(leaf);
		}
	}
	{
		NodeRef node = make_shared<Node>("프로그래밍팀");
		root->children.push_back(node);
		{
			NodeRef leaf = make_shared<Node>("서버");
			node->children.push_back(leaf);
		}
		{
			NodeRef leaf = make_shared<Node>("클라이언트");
			node->children.push_back(leaf);
		}
		{
			NodeRef leaf = make_shared<Node>("엔진");
			node->children.push_back(leaf);
		}
	}
	{
		NodeRef node = make_shared<Node>("디자인팀");
		root->children.push_back(node);
		{
			NodeRef leaf = make_shared<Node>("배경");
			node->children.push_back(leaf);
		}
		{
			NodeRef leaf = make_shared<Node>("캐릭터");
			node->children.push_back(leaf);
		}
	}

	return root;
}

void PrintTree(NodeRef root, int depth)
{

	for (size_t i = 0; i < depth; i++)
	{
		cout << "-";
	}
	cout << root->data << endl;

	for (NodeRef& child : root->children)
	{
		PrintTree(child,depth+1);
	}
}

int main()
{
	NodeRef root =  CreateTree();

	PrintTree(root,0);

}

코드는 위와 같이 구현을 할 수 있다. 

최상위 Root = R1 개발실을 만들고,

하위에 Root의 children의 디자인팀, 프로그래밍팀, 기획팀을 만든다.

마지막 하위인 Leaf은 하위 Root의 children으로 들어가게 된다. 결과적으로 

 

이런 결과 값이 나오게 된다.

 

여기서 만약 높이(height) : (루트의 가장 긴 깊이(depth)) 를 구하고 싶다면, 이러한 코드를 통해 높이를 얻을 수 있다.

 

int GetHeight(NodeRef root)
{
	int height = 1;

	for (NodeRef& child : root->children)
	{
		height = max(height,GetHeight(child) + 1);
	}

	return height;
}

 

 

 

 

참고 

https://monsieursongsong.tistory.com/6

[알고리즘] 2.3.자료구조 : 트리(Tree) 이해하기와 구현