프로그래밍 대회에서 배우는 알고리즘 문제해결 전략 책 내용 정리입니다.

21.1 도입

기초적인 정의와 용어

• 트리: 계층적 구조를 갖는 자료들을 표현하기 위한 자료 구조

트리의 구성 요소

• 부모(parent): 상위 노드
• 자식(child): 하위 노드
• 형제(sibling): 부모 노드가 같은 노드
• 선조(ancestor): 부모노드와 그의 부모들
• 자손(descendant): 자식 노드와 그의 자식들
• 루트(root): 다른 모든 노드들을 자손으로 갖는 노드

트리와 노드의 속성

• 깊이(depth): 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
• 높이(height): 가장 깊숙히 있는 노드의 깊이 ****

트리의 재귀적 속성

• 트리에서 한 노드와 그의 자손들을 모두 모으면 그들도 하나의 트리가 된다.

트리의 표현

• 각 노드를 하나의 구조체/객체로 표현하고, 이들을 서로의 포인터로 연결한다.
• 각 노드들은 자신의 부모와 모든 자식들에 대한 포인터를 가지고 있다.

코드 21.1 트리의 노드를 표현하는 객체의 구현

• 이진 검색 트리는 자식 노드 포인터 배열 대신 left, right를 이용해 자식 저장
• 힙은 노드가 들어갈 수 있는 자리가 비어 있는 일이 없으므로 배열을 사용해 트리 표현 가능
• 상호 배타적 집합 구조에서는 각 노드가 자신의 부모를 가리키는 포인터를 가지고 있을 뿐, 부모는 각 자식에 대한 정보가 없다.

struct TreeNode
{
	string label; //저장할 자료
	TreeNode* parent; // 부모 노드를 가리키는 포인터
	vector<TreeNode*> children; //자손 노드들을 가리키는 포인터의 배열
}

21.2 트리의 순회

• 재귀적 속성 이용: 트리의 루트가 주어질 때, 루트를 '방문'한 뒤, 각 서브트리를 재귀적으로 방문하는 함수 구현

코드 21.2 트리를 순회하며 모든 노드에 포함된 값을 출력하기

// 주어진 트리의 각 노드에 저장된 값을 모두 출력한다.
void printLabels(TreeNode* root)
{
	// 루트에 저장된 값을 출력한다.
	cout<< root->label <<endl;

	// 각 자손들을 루트로 하는 서브트리에 포함된 값을들 재귀적으로 출력한다.
for (int i = 0; i < root->children.size(); ++i)
	{
		printLabels(root->children[i];
	}
}

코드 21.3 순회를 이용해 트리의 높이를 계산하기

1. 루트의 각 자식들을 루트로 하는 서브트리들의 높이를 각각 재귀 호출을 통해 계산
2. 전체 트리의 높이는 그 중 최대치에 1을 더한 것

• 주의: 자손의 없는 경우, 높이는 0

// root를 루트로 하는 트리의 높이를 구한다
int height(TreeNode* root)
{
	int h = 0;
	for (int i = 0; i < root->children.size(); ++i)
	{
		// h는 직전까지 계산한 서브트리의 최대 높이이다.
		h = max(h, 1 + height(root->children[i]));
	}
	return h;
}

이진 검색트리에서의 순회

순회 순서: 트리의 루트 방문 순서에 따라 (서브트리는 항상 왼쪽 먼저 방문)

1. 전위 순회(preorder traverse) : 루트→ 왼쪽→ 오른쪽
2. 중위 순회(inorder traverse) : 왼쪽→ 루트→ 오른쪽
3. 후위 순회(postorder traverse) :왼쪽→오른쪽→루트