트리순회 결과 출력하기

문제

---

루트가 0인 이진트리가 주어질 때, 이를 전위순회, 중위순회, 후위순회한 결과를 각각 출력하는 프로그램을 작성하시오. 아래 그림은 이진트리의 예제와, 이 이진트리를 전위순회, 중위순회, 후위순회 한 결과를 나타낸다.

 

입력

---

첫 번째 줄에 트리의 노드 개수 n이 주어진다. ( 1 ≤ n ≤ 100 ) 두 번째 줄부터 트리의 정보가 주어진다. 각 줄은 3개의 숫자 a, b, c로 이루어지며, 그 의미는 노드 a의 왼쪽 자식노드가 b, 오른쪽 자식노드가 c라는 뜻이다. 자식노드가 존재하지 않을 경우에는 -1이 주어진다.

 

출력

---

첫 번째 줄에 전위순회, 두 번째 줄에 중위순회, 세 번째 줄에 후위순회를 한 결과를 출력한다.

 

예제 입력

6
0 1 2
1 3 4
2 -1 5
3 -1 -1
4 -1 -1
5 -1 -1

예제 출력

0 1 3 4 2 5
3 1 4 0 2 5
3 4 1 5 2 0

 

---

트리가 주어졌을 때 어떻게 배열에 받는지 고민이 필요하다. 나는 2차원 배열 tree[][2] 을 선언해서 

[x][0] ----> 노드x의 왼쪽 자식

[x][1] ----> 노드x의 오른쪽 자식

이라고 생각하고 예제를 입력받았다. 전위, 중위, 후위순회는 재귀적으로 구현하는데 그 중 하나만 짜게 되면 나머지는 비슷하기 때문에 쉽게 작성할 수 있다.

(전위순회의 예시)

1. preOrder(int x) 는 노드x의 전위순회를 시행하는 함수 인데, 기저 조건을 살펴보면 x의 왼쪽자식과 오른쪽자식이 없어야 한다. 즉 둘다 -1이여야 한다.

2. 만약에 기저조건이 아니라면 전위순회 이기 때문에 x를 먼저 출력하고 왼쪽자식에서 다시 전위순회를 시행하고 그 다음에 오른쪽 자식에서 전위순회를 시행하면 된다.

3. 여기서 주의할 점은 왼쪽자식이나 오른쪽자식이 없다면 ( -1이라면 ) 전위순회를 시행하면 안된다.