트리의 순회

트리 구조를 순회하는 방법은 일반적으로 전위, 중위, 후위 순회 세가지 방법이 있다. 방법이 복잡하지는 않지만 정리해두지 않으면 헷갈리니 기회가 되면 한번 정리해보고 직접 코드로 구현해보는 것이 좋을 것같다.

전위 순회는 루트 노드부터 시작해서 왼쪽 서브트리를 타기 전에 노드의 자료를 확인하고 그다음 왼쪽 서브트리로 이동해서 마찬가지로 전위 순회를 하게 되어있고, 왼쪽 서브트리에 대한 전위 순회를 마친 후 우측 서브트리의 전위 순회가 일어난다.

중위 순회는 루트 노드에서 시작해서 좌측 서브트리에 대한 중위 순회가 먼저 일어나고, 중위 순회가 더이상 일어날 수 없는 지점에서 노드의 자료를 확인하면서 좌측 서브트리의 중위 순회를 종료시킨다. 그다음 우측 서브트리의 중위 순회가 일어나게 된다.

후위 순회는 루트 노드에서 시작해서 좌측 서브트리의 후위 순회를 반복하다가 좌측 서브트리의 후위 순회가 불가능해지면 우측 서브트리에 대한 후위 순회가 진행된다. 순회가 종료되는 시점에 노드의 자료를 확인하게 된다.

말로만 풀어쓰면 헷갈리니 구체적인 예시를 보는게 좋을 것같다. 예시는 위키백과의 트리 순회와 백준 알고리즘 저지의 트리 순회 문제를 참고하자.

트리 순회 - 위키백과

https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EC%88%9C%ED%9A%8C

1991번: 트리 순회 - Baekjoon Online Judge

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		char root, left, right;
		int N = Integer.parseInt(br.readLine().trim());

		Node[] tree = new Node[26];
		for (int i = 0; i < 26; i++) {
			tree[i] = new Node();
		}

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine().trim());

			root = st.nextToken().charAt(0);
			left = st.nextToken().charAt(0);
			right = st.nextToken().charAt(0);

			tree[root - 'A'].left = left;
			tree[root - 'A'].right = right;
		}

		preorder(0, tree);
		System.out.print("\n");
		inorder(0, tree);
		System.out.print("\n");
		postorder(0, tree);
	}

	private static void preorder(int i, Node[] tree) {
		System.out.print((char) (i + 'A'));
		if (tree[i].left != '.') {
			preorder(tree[i].left - 'A', tree);
		}
		if (tree[i].right != '.') {
			preorder(tree[i].right - 'A', tree);
		}
	}

	private static void inorder(int i, Node[] tree) {
		if (tree[i].left != '.') {
			inorder(tree[i].left - 'A', tree);
		}
		System.out.print((char) (i + 'A'));
		if (tree[i].right != '.') {
			inorder(tree[i].right - 'A', tree);
		}
	}

	private static void postorder(int i, Node[] tree) {
		if (tree[i].left != '.') {
			postorder(tree[i].left - 'A', tree);
		}
		if (tree[i].right != '.') {
			postorder(tree[i].right - 'A', tree);
		}
		System.out.print((char) (i + 'A'));
	}
}

class Node {
	char left;
	char right;
}