[A* & Heap] Chapter 01. 트리

GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/ac4f9cf68e09fad3391232e069649d597289e58c

Tree · developeSHG/Data_Structure-Algorithm@ac4f9cf

 

 

---

 

 

트리의 개념

계층적 구조를 갖는 데이터를 표현하기 위한 자료구조

노드(Node) : 데이터를 표현

간선(Edge) : 노드의 계층 구조를 표현하기 위해 사용

 

위의 Tree 구조를 코드로 표현해보자.

 

#include <iostream>
#include <vector>
#include <list>
#include <stack>
#include <queue>
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 (int i = 0; i < depth; i++)
		cout << "-";
	cout << root->data << endl;

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

// 깊이(depth) : 루트에서 어떤 노드에 노달하기 위해 거쳐야 하는 간선의 수 (aka. 몇 층?)
// 높이(height) : 가장 깊숙히 있는 노드의 깊이 (max(depth))
int GetHeight(NodeRef root)
{
	int height = 1;

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

	return height;
}

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

	PrintTree(root, 0);

	int height = GetHeight(root);
	cout << "Tree Height : " << height << endl;
}