1991번: 트리 순회

 

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

1991번: 트리 순회

전위순회 중위순회 후위순회를 차례로 출력하는 문제다.

 

재귀를 이용하는 방법이 먼저 생각이 나서 재귀함수를 만들어서 풀었다.

 

 

문제에서 예시로 준 트리이다.

 

각 순회마다 출력되는 순서는 다음과 같아야 한다.

 

전위순회 (루트-왼-오) : ABDCEFG

중위순회 (왼-루트-오) : DBAECFG

후위순회 (왼-오-루트) : DBEGFCA

 

 

 

 

 

 

어떤 부트리에서든지 각 순회의 순서가 지켜져야 한다.

그러므로 어떤 부트리에서든지 사용 가능하도록 순서를 정해서 함수를 작성했다.

 

• 전위순회는 처음에 출력(방문) 후 왼쪽 자식을 인자로 주는 재귀호출, 오른쪽 자식을 인자로 주는 재귀호출 순으로 작성되어야 한다. 자식이 결국 또 다른 부트리더라도 출력 후 다시 왼쪽 자식을 부르는 식의 재귀가 일어난다.

 

• 중위순회는 왼쪽 자식을 인자로 주는 재귀호출, 중간에 출력(방문), 오른쪽 자식을 인자로 주는 재귀호출 순으로 작성되어야 한다. 자식이 또 다른 부트리더라도 왼쪽 자식을 계속해서 부르다가 결국 제일 왼쪽의 외부노드의 원소부터 출력하게된다. 

 

• 후위순회는 왼쪽 자식을 인자로 주는 재귀호출, 오른쪽 자식을 인자로 주는 재귀호출 후 마지막으로 출력(방문)하는 순으로 작성되어야 한다. 

 

 

 

항상 왼쪽자식을 오른쪽 자식보다 먼저 방문하기 때문에 오른쪽 자식이 없는 B와 같은 경우라면 그냥 return으로 B가 거느리는 부트리에 대한 방문을 완료해도 된다.

 

하지만 역시 항상 왼쪽자식을 오른쪽 자식보다 먼저 방문하기 때문에 F와 같이 왼쪽 자식은 없지만 오른쪽 자식은 존재하는 경우(외부 노드가 아니지만 왼쪽 자식이 없는 경우)에 대한 예외처리가 필요했다.

 

이 경우에는 각 순회마다 적절한 위치에 출력문(방문)을 넣고 왼쪽은 자식이 없으니 지나치고 오른쪽 자식을 인자로 주는 재귀호출을 한다. 그럼 그 밑에 수없이 많은 부트리가 있더라도 재귀함수에 따라 호출에 호출을 하면서 알아서 방문을 마칠 것이다.

 

이 예외에 대한 처리를 하다가 자꾸 오류가 났다. 이 경우에 오른쪽 자식을 호출하고서 다시 돌아왔을때 return으로 그 부트리에 대한 방문을 마쳐야 하는데 그것을 안하니까 if절 다음줄에 있는 (있지도 않은)왼쪽 자식을 인자로 갖는 재귀함수 호출이 일어나서 생기는 오류였다. 

 

#pragma warning (disable : 4996)
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct NODE {
	char elem;
	struct NODE* parent, * lchild, * rchild;
}NODE;
typedef struct Tree {
	struct NODE* root;
	int n;//노드의 수
}Tree;

int isExternal(NODE* v);
void rpreorder(NODE* v);
void rinorder(NODE* v);
void rpostorder(NODE* v);

int main() {
	int N;
	scanf("%d", &N);
	Tree* T = (Tree*)malloc(sizeof(Tree));
	T->n = N;
	T->root = (NODE*)malloc(sizeof(NODE));
	NODE** tree = (NODE**)malloc(sizeof(NODE*) * N);

	char me, left, right, order = 'A';
	int i, m, l, r;

	for (i = 0; i < N; i++) {
		tree[i] = (NODE*)malloc(sizeof(NODE));
		tree[i]->elem = order;
		order++;
	}
	T->root = tree[0];

	for (i = 0; i < N; i++) {
		getchar();
		scanf("%c %c %c", &me, &left, &right);
		m = me - 'A';
		l = left - 'A';
		r = right - 'A';
		if(left=='.') {
			tree[m]->lchild = NULL;
		}
		else {
			tree[m]->lchild = tree[l];
			tree[l]->parent = tree[m];
		}
		if(right=='.') {
			tree[m]->rchild = NULL;
		}
		else {
			tree[m]->rchild = tree[r];
			tree[r]->parent = tree[m];
		}
	}
	rpreorder(T->root); printf("\n");
	rinorder(T->root); printf("\n");
	rpostorder(T->root);
	return 0;
}
int isExternal(NODE* v) {
	if (v->lchild == NULL && v->rchild == NULL)return 1;
	return 0;
}
void rpreorder(NODE* v) {
	if (isExternal(v) == 1) {
		printf("%c", v->elem);
		return;
	}
	printf("%c", v->elem);
	if (v->lchild == NULL && v->rchild != NULL) {
		rpreorder(v->rchild);
		return;
	}
	rpreorder(v->lchild);
	if (v->rchild == NULL)return;
	rpreorder(v->rchild);
}
void rinorder(NODE* v) {
	if (isExternal(v) == 1) {
		printf("%c", v->elem);
		return;
	}
	if (v->lchild == NULL && v->rchild != NULL) {
		printf("%c", v->elem);
		rinorder(v->rchild);
		return;
	}
	rinorder(v->lchild);
	printf("%c", v->elem);
	if (v->rchild == NULL)return;
	rinorder(v->rchild);
}
void rpostorder(NODE* v) {
	if (isExternal(v) == 1) {
		printf("%c", v->elem);
		return;
	}
	if (v->lchild == NULL && v->rchild != NULL) {
		rpostorder(v->rchild);
		printf("%c", v->elem);
		return;
	}
	rpostorder(v->lchild);
	if (v->rchild == NULL) {
		printf("%c", v->elem);
		return;
	}
	rpostorder(v->rchild);
	printf("%c", v->elem);
}

 

 

이 오류가 아니었으면 더 빨리 끝낼 수 있는 문제였다. 좀 더 체계적으로 생각해야겠다.