Tree

트리

• 계층적 구조를 갖는 데이터를 표현하기 위한 자료구조
  • 노드: 데이터를 표현
  • 간선: 노드의 계층 구조를표현하기 위해 사용
• 트리의 특성상 재귀 알고리즘과 잘 어울린다.

// 기본적인 트리
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>("Root");
	{
		NodeRef node = make_shared<Node>("children1");
		root->children.push_back(node);
		{
			NodeRef leaf= make_shared<Node>("children1-1");
			node->children.push_back(leaf);
		}
		{
			NodeRef leaf= make_shared<Node>("children1-2");
			node->children.push_back(leaf);
		}
		{
			NodeRef leaf= make_shared<Node>("children1-3");
			node->children.push_back(leaf);
		}
	}
	{
		NodeRef node = make_shared<Node>("children2");
		root->children.push_back(node);
		{
			NodeRef leaf= make_shared<Node>("children2-1");
			node->children.push_back(leaf);
		}
		{
			NodeRef leaf= make_shared<Node>("children2-2");
			node->children.push_back(leaf);
		}
		{
			NodeRef leaf= make_shared<Node>("children2-3");
			node->children.push_back(leaf);
		}
	}
	{
		NodeRef node = make_shared<Node>("children3");
		root->children.push_back(node);
		{
			NodeRef leaf= make_shared<Node>("children3-1");
			node->children.push_back(leaf);
		}
		{
			NodeRef leaf= make_shared<Node>("children3-2");
			node->children.push_back(leaf);
		}
		{
			NodeRef leaf= make_shared<Node>("children3-3");
			node->children.push_back(leaf);
		}
	}
	{
		NodeRef node = make_shared<Node>("children4");
		root->children.push_back(node);
		{
			NodeRef leaf= make_shared<Node>("children4-1");
			node->children.push_back(leaf);
		}
		{
			NodeRef leaf= make_shared<Node>("children4-2");
			node->children.push_back(leaf);
			{
				NodeRef leaf2 = make_shared<Node>("children4-2-1");
				leaf->children.push_back(leaf2);
			}
		}
	}

	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) : 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
// 높이(height) : 가장 깊숙히 있는 노드의 깊이
int GetHeight(NodeRef root)
{
	int height = 1;
	for (NodeRef& child : root->children)
	{
		height = max(height, GetHeight(child) + 1);
	}
	return height;
}

• 재귀를 통해 출력과 높이를 구하는 함수이다.

• 트리 밑에는 트리가 있는 형태이기 때문에 재귀를 사용하면 편하다.