알고리즘 문제 해결 전략 2 06장 트리 (1)

void printPostOrder(const vector<int>& preorder, const vector<int>& inorder) {
	const int N = preorder.size();
	if (preorder.empty()) return;
	const int root = preorder[0];
	const int L = find(inorder.begin(), inorder.end(), root) - inorder.begin();
	const int R = N - 1 - L;
	printPostOrder(slice(preorder, 1, L + 1), slice(inorder, 0, L));
	printPostOrder(slice(preorder, L + 1, N), slice(inorder, L + 1, N));
	cout << root << " ";
}

트리는 계층 관계를 갖는 객체들을 표현하기 위해 만들어진 자료 구조임. 그러나 사실 트리는 이 외의 용도로 더 많이 사용되는데, 실제 계층 관계가 없는 자료들을 트리로 표현해서 같은 연산을 더 빠르게 할 수 있는 경우가 많기 때문임. 

 

21. 트리의 구현과 순회

21.1 도입

트리가 유용하게 사용되는 큰 이유 중 하나는 트리가 재귀적인 성질을 갖고 있다는 것임. 따라서 모든 트리는 루트와 루트 밑에 있는 서브티르들의 집합이라고 말할 수 있음. TreeNode는 특정 구조나 형태를 가정하지 않음. 어떤 형태의 트리라도 트리의 가장 기초적인 조건을 충족하기만 한다면 표현할 수 있다는 뜻임. 

 

21.2 트리의 순회

void printLabels(TreeNode* root) {
	cout << root->label << endl;
	for (int i = 0; i < root->children.size(); i++)
		printLabels(root->children[i]);
}

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

int height(TreeNode* root) {
	int h = 0;
	for (int i = 0; i < root->children.size(); ++i)
		h = max(h, 1 + height(root->children[i]));
	return h;
}

 

21.3 문제 : 트리 순회 순서 변경

모두 왼쪽 서브트리를 오른쪽보다 먼저 방문한다는 점에선 같지만, 트리의 루트를 언제 방문하는지가 다름. 어떤 이진 트리를 전위 순회했을 때 노드들의 방문 순서와, 중위 순회했을 때 노드들의 방문 순서가 주어졌다고 함. 이 트리를 후위 순회했을 떄 각 노드들을 어떤 순서대로 방문하게 될지 계산하는 프로그램 작성.

 

21.4 풀이: 트리 순회 순서 변경

struct TreeNode{
	string label;
	TreeNode* parent;
	vector<TreeNode*> children;
};

vector<int> slice(const vector<int>& v, int a, int b) {
	return vector<int>(v.begin() + a, v.begin() + b);
}

void printPostOrder(const vector<int>& preorder, const vector<int>& inorder) {
	const int N = preorder.size();
	if (preorder.empty()) return;
	const int root = preorder[0];
	const int L = find(inorder.begin(), inorder.end(), root) - inorder.begin();
	const int R = N - 1 - L;
	printPostOrder(slice(preorder, 1, L + 1), slice(inorder, 0, L));
	printPostOrder(slice(preorder, L + 1, N), slice(inorder, L + 1, N));
	cout << root << " ";
}