트리 순회 [백준 1991][JAVA][실버1][트리][Tree]

 

[광고 누르면 오늘의 행운 상승!!]

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

1991번: 트리 순회

이진트리 - 순회(traversal)

• 순회란?

  순회(traversal) : 트리의 노드들을 체계적으로 방문하는 것

  순회란 트리의 각 노드를 중복되지 않게 전부 방문(visit) 하는 것을 말하는데
  트리는 비 선형 구조이기 때문에 선형구조에서와 같이 선후 연결 관계를 알 수 없다.

• 트리의 순회방법 3가지

  전위순회(preorder traversal) : VLR

  • 부모노드 방문 후, 자식노드를 좌,우 순서로 방문

  중위순회(inorder traversal) : LVR

  • 왼쪽 자식노드, 부모노드, 오른쪽 자식노드 순으로 방문한다.

  후위순회(postorder traversal) : LRV

  • 자식노드를 좌우 순서로 방문한 후, 부모노드로 방문한다.

 

package Study0319;

import java.io.*;
import java.util.*;

class Node{
	int index;
	Node parent;
	Node leftchild;
	Node rightchild;

	public Node(int index) {
		super();
		this.index = index;
	}
}
public class 트리순회 {
	static Node[] graph;
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		graph = new Node[N];
		
		for (int i = 0; i < N; i++) {
			graph[i] = new Node(i);
		}
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			
			int node = st.nextToken().charAt(0)-'A';
			int left = st.nextToken().charAt(0)-'A';
			int right = st.nextToken().charAt(0)-'A';
			
			if(left >= 0)graph[node].leftchild = graph[left];
			if(right >= 0)graph[node].rightchild = graph[right];
			
			if(left >= 0) graph[left].parent = graph[node];
			if(right >= 0)graph[right].parent = graph[node];
		}
		
		preOrder(0);
		System.out.println();
		inOrder(0);
		System.out.println();
		PostOrder(0);
	}

	private static void PostOrder(int cur) {
		//왼쪽 노드 확인
		if(graph[cur].leftchild != null)
		PostOrder(graph[cur].leftchild.index);
		
		//오른쪽 노드 확인
		if(graph[cur].rightchild != null)
		PostOrder(graph[cur].rightchild.index);
		
		//자신 노드 확인
		System.out.print((char)(graph[cur].index+'A'));
	}

	private static void inOrder(int cur) {
		//왼쪽 노드 확인
		if(graph[cur].leftchild != null)
		inOrder(graph[cur].leftchild.index);
		
		//자신 노드 확인
		System.out.print((char)(graph[cur].index+'A'));
				
		//오른쪽 노드 확인
		if(graph[cur].rightchild != null)
		inOrder(graph[cur].rightchild.index);
	}

	private static void preOrder(int cur) {
		//자신 노드 확인
		System.out.print((char)(graph[cur].index+'A'));
		
		//왼쪽 노드 확인
		if(graph[cur].leftchild != null)
		preOrder(graph[cur].leftchild.index);
		
		//오른쪽 노드 확인
		if(graph[cur].rightchild != null)
		preOrder(graph[cur].rightchild.index);
	}
}