c++ 백준_1991_"트리 순회"

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

1991번: 트리 순회

오랜만에 트리 순회를 해보았다.

​

노드와 각 자식들이 주어지고

그 트리를 순회하는 것이다.

​

각 입력이 주어질 때

자식노드의 부모를 따로 저장하고,

root 노드를 찾기 위해

각 노드에 저장된 부모 노드를 거슬러 올라가서 root 부터 순회했다.

 

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

typedef struct {
	char ch;
	int left, right;
	int parent;
}node;

node tree[26];

int where_root(int N, int idx) {
	if (tree[idx].parent == -1)
		return idx;
	return where_root(N, tree[idx].parent);
}

void preorder(int idx) {

	cout << tree[idx].ch;

	if (tree[idx].left != -1)
		preorder(tree[idx].left);

	if (tree[idx].right != -1)
		preorder(tree[idx].right);
}

void inorder(int idx) {

	if (tree[idx].left != -1)
		inorder(tree[idx].left);

	cout << tree[idx].ch;

	if (tree[idx].right != -1)
		inorder(tree[idx].right);
}

void postorder(int idx) {

	if (tree[idx].left != -1)
		postorder(tree[idx].left);

	if (tree[idx].right != -1)
		postorder(tree[idx].right);

	cout << tree[idx].ch;
}

int main(void) {

	int N;
	cin >> N;

	
	for (int i = 0; i < N; i++) {
		tree[i].parent = -1;
		tree[i].left = -1;
		tree[i].right = -1;
	}

	char head, left, right;
	for (int i = 0; i < N; i++) {
		cin >> head >> left >> right;

		tree[head - 65].ch = head;

		if (left != '.') {
			tree[head - 65].left = left - 65;
			tree[left - 65].parent = head - 65;
		}
		
		if (right != '.') {
			tree[head - 65].right = right - 65;
			tree[right - 65].parent = head - 65;
		}
	}

	int root = where_root(N,0);
	
	
	preorder(root);
	cout << "\n";
	inorder(root);
	cout << "\n";
	postorder(root);

}