3-1. 트리 기초

1. 개념

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

(1) 노드(Node) : 각 데이터를 표현하는 정점

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

 

2. 관련 용어

- 부모 노드, 자식 노드, 형제 노드

- 선조, 자손

- 루트 ; 최상위 노드, 잎 ; 최하위 노드

- 깊이 ; 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수

- 높이 ; 가장 깊숙히 있는 노드의 깊이

- 트리의 재귀적 속성 ; 트리의 일부분만 잘라도 트리의 속성을 띄고 있음

- 서브트리

 

3. 코드로 작성해보기

(1) 노드(Node)

#include <iostream>
#include <vector>
#include <memory> // shared_ptr 사용
#include <list>
#include <queue>
#include <stack>

using namespace std;
using NodeRef = shared_ptr<struct Node>;

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


	string data;
	vector<NodeRef> children;
};

 

(2) NodeRef ; shared_ptr을 사용한 Node의 참조형

NodeRef를 사용하여 각 노드가 자기 자신을 가리키는 스마트 포인터를 가지게 한다.

이를 통해 노드끼리 안전하게 참조하고 소멸 시에 적절히 메모리를 해제하게 된다.

 

(3) CreateTree ; 본격적인 Tree 만들기

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; // 최상위 노드를 이용하여 순회할 수 있음
}

각 노드들은 children이라는 멤버 변수(동적 배열)를 가지고 있다.

root - node - leaf의 종속 관계에서 root의 children은 node, node의 children은 leaf로 지정한다.

그리고 Node의 오버로딩된 생성자를 이용하여 값을 data 멤버변수에 넣어준다.

 

(4) PrintTree ; 트리 출력하기

void PrintTree(NodeRef root, int depth)
{
	for (int i = 0; i < depth; i++)
		cout << "-";
	cout << root->data << endl;

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

범위 기반(range-based) for 루프를 사용하여 root 노드의 children 벡터에 있는 각 자식 노드를 순회한다.

root -> children에서 가져온 각 자식 노드를 child라는 변수에 할당하고, 루프 내에서 PrintTree 함수를 재귀적으로 호출한다.

그리고 각 자식 노드에 대해 '-'를 하나씩 증가시킨 depth + 1 값을 전달하여 하위 트리를 출력한다.

 

(5) GetHeight ; 높이 구하기

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

	for (NodeRef& child : root->children)
	{ // 각 자식마다 높이가 다를 수 있음에 유의
		height = max(height, GetHeight(child) + 1); // 자식 트리의 높이에 1을 더하면 전체 트리의 높이
	}

	return height;
}

자식 트리의 높이를 구해서 1을 더해주면 전체 트리의 높이가 된다.

max를 이용하는 이유는 자식 노드마다 높이가 다를 수 있기 때문에, 최하위에서부터 트리의 높이를 측정하기 위함이다.

 

(6) main

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

	PrintTree(root, 0);

	return 0;
}