백준 1991 - 트리순회

www.acmicpc.net/problem/1991

1991번: 트리 순회

트리의 자료구조를 잘 만드는 것이 중요한데 N * 3 의 배열로 구성한다.

각 노드별 row 를 의미하고 각 row 별로 첫번째가 부모 , 두번째가 왼쪽자식, 세번째가 오른쪽 자식을 나타내게 표현한다. 불필요한 연산을 하지 않기 위해 배열크기(N) 을 'Z' + 1 이 되게 하여  알파벳 char 로 바로 해당 위치의노드를 참조할수 있도록 구성한다.

각 순회는 재귀 호출을 통해 구현할 수 있다.

 

구현된 코드는 아래와 같다.

#include <iostream>
#include <vector>

using namespace std;


void traversePrefix(const char node, const vector<vector<int>> &tree)
{
	cout << node;
	if (tree[node][1] != '.')
		traversePrefix(tree[node][1], tree);
	if (tree[node][2] != '.')
		traversePrefix(tree[node][2], tree);
}

void traversePostfix(const char node, const vector<vector<int>> &tree)
{
	if (tree[node][1] != '.')
		traversePostfix(tree[node][1], tree);
	if (tree[node][2] != '.')
		traversePostfix(tree[node][2], tree);
	cout << node;
}

void traverseInfix(const char node, const vector<vector<int>> &tree)
{
	if (tree[node][1] != '.')
		traverseInfix(tree[node][1], tree);
	cout << node;
	if (tree[node][2] != '.')
		traverseInfix(tree[node][2], tree);
}


int main()
{
	int nrNode;
	cin >> nrNode;

	vector<vector<int>> tree('Z' + 1, vector<int>(3, 0));

	for (unsigned int i = 0; i < tree.size(); i++)
		tree[i][0] = i;

	for (int i = 0; i < nrNode; i++)
	{
		char node, left, right;
		cin >> node >> left >> right;
		tree[node][1] = left;
		tree[node][2] = right;
		if (left != '.')
			tree[left][0] = node;
		if (right != '.')
			tree[right][0] = node;
	}

	char root = 'A';

	while (root != tree[root][0])
	{
		root = tree[root][0];
	}

	traversePrefix(root, tree);
	cout << endl;
	traverseInfix(root, tree);
	cout << endl;
	traversePostfix(root, tree);
	cout << endl;
	return 0;
}