[트리] 트리의 순회

트리의 순회(Tree Traversal)

• 트리의 모든 노드를 방문하는 순서
• 트리 내에 어떠한 자료가 담겨있는지를 알기 위함
• 그래프의 경우 DFS와 BFS가 있음
• 트리에서도 위의 두 방법을 사용가능 하지만, 트리에서만 사용할 수 있는 방법이 3가지 있음
• 1) 프리오더 = 전위 순회
• 2) 인오더 = 중위 순회
• 3) 포스트오더 = 후위 순회
• 세 방법의 차이는 노드 방문을 언제 하냐의 차이임

전위 순회, 프리오더(Pre-order)

• Root - L - R
• 노드 방문 - 왼쪽 서브 트리 순회 - 오른쪽 서브 트리 순회
• 순서 : A-B-D-E-C-F-G
• 그래프의 DFS의 순서와 같음

노드 방문

왼쪽 서브 트리 순회

오른쪽 서브 트리 순회

중위 순회, 인오더(In-order)

• L - Root - R
• 왼쪽 서브 트리 순회 - 노드 방문 - 오른쪽 서브 트리 순회
• 순서 : D-B-E-A-F-C-G

후위 순회, 포스트오더(Post-order)

• L - R - Root
• 왼쪽 서브 트리 순회 - 오른쪽 서브 트리 순회 - 노드 방문
• 순서 : D-E-B-F-G-C-A

코드

import java.util.Scanner;

public class treeTraversal {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(); //node
		sc.nextLine();
		
		int[][] a = new int[n][2];
		for(int i=0; i<n; i++){
			String[] line = sc.nextLine().split(" ");
			int x = Integer.parseInt(line[0]);
			a[x][0] = Integer.parseInt(line[1]);
			a[x][1] = Integer.parseInt(line[2]);
		}
		
		preorder(a,0);
		System.out.println();
		inorder(a,0);
		System.out.println();
		postorder(a,0);
		System.out.println();
	}

	private static void preorder(int[][] a, int x) {
		if(x == -1) return;
		System.out.print(x+ " ");
		preorder(a, a[x][0]);
		preorder(a, a[x][1]);
	}
	
	private static void inorder(int[][] a, int x) {
		if(x == -1) return;
		inorder(a, a[x][0]);
		System.out.print(x+ " ");
		inorder(a, a[x][1]);
	}
	
	private static void postorder(int[][] a, int x) {
		if(x == -1) return;
		postorder(a, a[x][0]);
		postorder(a, a[x][1]);
		System.out.print(x+ " ");
	}
}