전위 순회는 루트-왼쪽-오른쪽
중위 순회는 왼쪽-루트-오른쪽
후위 순회는 왼쪽-오른쪽-루트
위와 같은 순서로 트리의 노드를 방문하여 출력하는 문제이다.
이진트리이기 때문에 왼쪽, 오른쪽의 노드만을 가지며 이를 구현하는 class를 만들어 활용하면 문제를 쉽게 풀 수 있다.
다음은 Java로 작성한 코드이다.
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Scanner;
public class traversal {
static class node{
String value;
String left;
String right;
public node(String v, String l, String r) {
value = v;
left = l;
right = r;
}
public node() {
}
public String toString() {
return value + " " + left + " " + right;
}
}
static ArrayList<node> tree;
public static void main(String[] args) {
tree = new ArrayList<node>();
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
for (int i = 0; i < n; i++) {
tree.add(new node(scan.next(),scan.next(),scan.next()));
}
preorder("A");
System.out.println();
inorder("A");
System.out.println();
postorder("A");
}
public static void preorder(String root) {
System.out.print(root);
Iterator<node> itr = tree.iterator();
node n = new node();
while(itr.hasNext()) {
n = itr.next();
if(n.value.equals(root)) {
break;
}
}
if(!n.left.equals(".")) {
preorder(n.left);
}
if(!n.right.equals(".")) {
preorder(n.right);
}
}
public static void inorder(String root) {
Iterator<node> itr = tree.iterator();
node n = new node();
while(itr.hasNext()) {
n = itr.next();
if(n.value.equals(root)) {
break;
}
}
if(!n.left.equals(".")) {
inorder(n.left);
}
System.out.print(root);
if(!n.right.equals(".")) {
inorder(n.right);
}
}
public static void postorder(String root) {
Iterator<node> itr = tree.iterator();
node n = new node();
while(itr.hasNext()) {
n = itr.next();
if(n.value.equals(root)) {
break;
}
}
if(!n.left.equals(".")) {
postorder(n.left);
}
if(!n.right.equals(".")) {
postorder(n.right);
}
System.out.print(root);
}
}
전위, 중위, 후위 순회를 구현하는 함수를 정의하여 깊이 우선 탐색을 진행하면 된다.
세 가지 순회 방식은 방식은 똑같지만 출력하는 처리를 언제 하느냐에 따라 구분된다.
(출력을 언제하는지 보면 무슨 순회인지 알 수 있다)
"."은 자식 노드가 없는 것 이기 때문에 "."이 아닐 시에만 순회를 진행하게 하였다.
