C++ / 백준 / 1991 / 트리 순회

문제

 

https://www.acmicpc.net/problem/1991

1991번: 트리 순회

 

문제풀이

void Preorder(char node, const vector<vector<char>>& tree) {
	cout << node;
	if (tree[node - 'A'][0] != '.') {
		Preorder(tree[node - 'A'][0], tree);
	}
	if (tree[node - 'A'][1] != '.') {
		Preorder(tree[node - 'A'][1], tree);
	}
}

 

전위 순회는 부모 노드, 왼쪽 자식 노드, 오른쪽 자식 노드 순이므로 먼저 현재 노드를 출력한다.

알파벳을 입력받고 배열의 0번째 인덱스부터 사용할 것이므로 노드에서 'A'의 아스키코드값을 뺀다.

tree[node][0]은 왼쪽 자식 노드이고 tree[node][1]은 오른쪽 자식이다.

.이 입력되어 있는 경우는 자식이 없는 경우이므로 넘어간다.

 

void Inorder(char node, const vector<vector<char>>& tree) {
	if (tree[node - 'A'][0] != '.') {
		Inorder(tree[node - 'A'][0], tree);
	}
	cout << node;
	if (tree[node - 'A'][1] != '.') {
		Inorder(tree[node - 'A'][1], tree);
	}
}

 

두 번째는 중위 순회이다.

중위 순회는 왼쪽 자식 노드, 부모 노드, 오른쪽 자신 노드 순으로 순회를 한다.

그렇기 때문에 왼쪽 노드의 값이 있으면 함수를 실행하고 현재 노드(부모 노드)를 출력한다.

.이 입력되어 있는 경우는 자식이 없는 경우이므로 넘어간다.

 

void Postorder(char node, const vector<vector<char>>& tree) {
	if (tree[node - 'A'][0] != '.') {
		Postorder(tree[node - 'A'][0], tree);
	}
	if (tree[node - 'A'][1] != '.') {
		Postorder(tree[node - 'A'][1], tree);
	}
	cout << node;
}

 

마지막으로 후위 순회이다.

후위 순회는 왼쪽 자식 노드, 오른쪽 자식 노드, 부모 노드 순으로 순회를 한다.

.이 입력되어 있는 경우는 자식이 없는 경우이므로 넘어간다.

 

코드

#include <iostream>
#include <vector>
using namespace std;

void Preorder(char node, const vector<vector<char>>& tree) {
	cout << node;
	if (tree[node - 'A'][0] != '.') {
		Preorder(tree[node - 'A'][0], tree);
	}
	if (tree[node - 'A'][1] != '.') {
		Preorder(tree[node - 'A'][1], tree);
	}
}

void Inorder(char node, const vector<vector<char>>& tree) {
	if (tree[node - 'A'][0] != '.') {
		Inorder(tree[node - 'A'][0], tree);
	}
	cout << node;
	if (tree[node - 'A'][1] != '.') {
		Inorder(tree[node - 'A'][1], tree);
	}
}

void Postorder(char node, const vector<vector<char>>& tree) {
	if (tree[node - 'A'][0] != '.') {
		Postorder(tree[node - 'A'][0], tree);
	}
	if (tree[node - 'A'][1] != '.') {
		Postorder(tree[node - 'A'][1], tree);
	}
	cout << node;
}

int main() {
	int N(0);
	cin >> N;
	vector<vector<char>>tree(N, vector<char>(2, ' '));

	char parent(' '), left_child(' '), right_child(' ');
	for (int idx = 0; idx < N; ++idx) {
		cin >> parent >> left_child >> right_child;
		tree[parent - 'A'][0] = left_child;
		tree[parent - 'A'][1] = right_child;
	}

	Preorder('A', tree);
	cout << '\n';
	Inorder('A', tree);
	cout << '\n';
	Postorder('A', tree);
}