BOJ 1991 : 트리 순회

알고리즘 문제 전체 링크

 

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

 

참고

- 링크드 리스트 Linked List

 

 

링크드 리스트를 이용하여 간단히 트리를 만들 수 있다.

노드에 포인터를 2개 사용하면 트리가 된다.

typedef struct st
{
	char value;
	struct st *left;
	struct st *right;
}NODE;

NODE node['Z' + 1];

 

각 노드에 value를 해당 알파벳으로 설정한다.

for (int i = 'A'; i <= 'Z'; i++) node[i].value = i;

 

그리고 input에서 주어진 대로 node를 왼쪽과 오른쪽에 할당하면 된다.

	for (int i = 0; i < N; i++)
	{
		char a, b, c;

		scanf(" %c %c %c", &a, &b, &c);

		if (b != '.') node[a].left = &node[b];
		if (c != '.') node[a].right = &node[c];
	}

 

순회 방법은 간단하다.

전위 순회는 노드를 먼저 출력하고 다시 전위 순회를 실행하고,

중위 순회는 중위 순회를 한번 실행하고 노드를 출력하고,

후위 순회는 후위 순회를 모두 실행하고 노드를 출력한다.

void preorder(NODE *nd) // 전위 순회
{
	if (nd == NULL) return;

	printf("%c", nd->value);
	preorder(nd->left);
	preorder(nd->right);
}

void inorder(NODE *nd) // 중위 순회
{
	if (nd == NULL) return;

	inorder(nd->left);
	printf("%c", nd->value);
	inorder(nd->right);
}

void postorder(NODE *nd) // 후위 순회
{
	if (nd == NULL) return;

	postorder(nd->left);
	postorder(nd->right);
	printf("%c", nd->value);
}

 

문제에서 루트 노드가 A라고 하였으므로 노드 A를 넣어주면 된다.

	preorder(&node['A']);
	putchar('\n');
	inorder(&node['A']);
	putchar('\n');
	postorder(&node['A']);
	putchar('\n');

 

전체 코드는 다음과 같다.

#include <stdio.h>

int N;

typedef struct st
{
	char value;
	struct st *left;
	struct st *right;
}NODE;

NODE node['Z' + 1];

void preorder(NODE *nd) //전위 순회
{
	if (nd == NULL) return;

	printf("%c", nd->value);
	preorder(nd->left);
	preorder(nd->right);
}

void inorder(NODE *nd) //중위 순회
{
	if (nd == NULL) return;

	inorder(nd->left);
	printf("%c", nd->value);
	inorder(nd->right);
}

void postorder(NODE *nd) //후위 순회
{
	if (nd == NULL) return;

	postorder(nd->left);
	postorder(nd->right);
	printf("%c", nd->value);
}

int main(void)
{
	scanf("%d", &N);

	for (int i = 'A'; i <= 'Z'; i++) node[i].value = i;

	for (int i = 0; i < N; i++)
	{
		char a, b, c;

		scanf(" %c %c %c", &a, &b, &c);

		if (b != '.') node[a].left = &node[b];
		if (c != '.') node[a].right = &node[c];
	}

	preorder(&node['A']);
	putchar('\n');
	inorder(&node['A']);
	putchar('\n');
	postorder(&node['A']);
	putchar('\n');

	return 0;
}