트리

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

노드 : 데이터를 표현

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

부모, 자식 노드 : 계층 구조의 노드

형제 노드 : 같은 부모와의 계층 구조를 이루는 노드

루트 노드 : 최상위 노드

잎 노드 : 맨 밑에 노드들

깊이 : 루트 노드를 기준으로 0부터 아래 계층에 1씩 더해진다

높이 : 트리의 계층의 갯수를 의미

트리는 재귀적 속성 및 서브트리로 볼 수 있다.

트리 내부에 트리가 있다.

 

 

#include <iostream>
#include <queue>
#include <vector>
#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 (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);

		// 위의 코드와 같다.
		// 모든 자식 노드를 순회하면서 height 를 반환하는데 그 값에 + 1 을 한다.
		// 이때 순회 중이던 자식 노드가 가지는 자식이 더 없다면 1을 반환한다.
		// 이렇게 1 + 1 + 1 + 1 + ... 해서 루트노드의 retur 값은 leaf 노드에서 시작한 깊이로 반환 되어진다.
		/*if (height < GetHeight(child) + 1)
		{
			height = GetHeight(child) + 1;
		}*/
	}

	return height;
}

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

	PrintTree(root,0);

	cout << "트리 높이" << GetHeight(root) << endl;
	return 0;
}