밍의 기록들😉

[트리] 트리의 순회 본문

자료구조, 알고리즘/기본다지기

[트리] 트리의 순회

민쓰 2018. 9. 9. 21:54

트리의 순회(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+ " ");
	}
}


0 Comments
댓글쓰기 폼