[C++ 자/알 Note] 트리 기초

트리 개념

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

그래프처럼 노드와 간선으로 구성되어 있지만

계층적 구조를 갖는다는 점이 다르다

 

트리 관련 용어

- Root: 가장 상위 노드

- Parent Node: 특정 노드를 기준으로 상위에 있는 경우

- Child Node: 특정 노드를 기준으로 하위에 있는 경우

- Siblings: 특정 노드를 기준으로 하위에 있는 여러 Child Node들

- Leaf Nodes: 자식이 없는 노드들

- Subtree: 모든 트리는 트리의 재귀적인 구조로 각자 하위 트리들로 구성되어 있음을 의미

- Level(Depth): Root부터 Level 0으로 시작하는 트리의 깊이를 의미

- Height: 가장 깊은 노드의 깊이를 의미한다

간선 기준으로는 가장 깊은 노드의 깊이

노드 기준으로는 가장 깊은 노드의 깊이 + 1을 의미한다

 

트리 구현

위의 트리를 구현하면 아래와 같이 작성할 수 있다

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>("A");
	{
		NodeRef node = make_shared<Node>("B");
		root->children.push_back(node);
		{
			NodeRef leaf = make_shared<Node>("D");
			node->children.push_back(leaf);
		}
		{
			NodeRef leaf = make_shared<Node>("E");
			node->children.push_back(leaf);
		}
	}
	{
		NodeRef node = make_shared<Node>("C");
		root->children.push_back(node);
		{
			NodeRef leaf = make_shared<Node>("F");
			node->children.push_back(leaf);
		}
		{
			NodeRef leaf = make_shared<Node>("G");
			node->children.push_back(leaf);
		}
	}

	return root;
}

 

트리 순회 및 트리 깊이

DFS로 트리를 간단하게 순회하는 코드는 아래와 같다

순회를 하는 경우에 각 노드의 depth를 측정해 활용하는 경우가 많다

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);
}

 

트리 높이

노드 기준으로 Height는 가장 깊숙이 있는 노드의 깊이 + 1이고

이를 출력하는 코드는 아래와 같다

다양한 방법으로 Height를 찾아낼 수 있지만

여기서는 가장 끝 리프노드부터 height가 1이 시작되어

재귀함수가 종료되면서 height가 + 1이 되는 코드이다

그리고 max를 이용해 가장 큰 height가 저장되도록 되어있다

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

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

	return height;
}