[BAEKJOON] 백준 그래프1991 :: 트리 순회

 

💬  문제 설명

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.

예를 들어 위와 같은 이진 트리가 입력되면,
전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트) 가 된다.

 

🔨  입출력 예

입력 

• 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다.
• 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다.
• 노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며, 항상 A가 루트 노드가 된다.
• 자식 노드가 없는 경우에는 .으로 표현한다.

출력

• 첫째 줄에 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력한다.
• 각 줄에 N개의 알파벳을 공백 없이 출력하면 된다.

 

예제 입력 1)

7
A B C
B D .
C E F
E . .
F . G
D . .
G . .

 

예제 출력 1)

ABDCEFG
DBAECFG
DBEGFCA

 

​

💻  Main.java

• 트리의 기초를 다루는 문제!
• 트리 문제를 너무 오랜만에 풀어서 조금 헤멨지만, 다시 트리를 익힐 수 있는 좋은 문제였다~

/* 백준 그래프 - 1991 :: 트리 순회 */

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

// 노드
class Node { 
	public char data; 
	Node lt, rt;
	
	Node (char data){ 
		this.data = data;
	} 
}
	
class Tree{
	Node root;
	
	// 트리 입력
	void add(char data, char left, char right) {
		// 루트가 비어있으면 데이터 입력
		if(root == null) {
			if(data != '.')
				root = new Node(data);
			if(left != '.')
				root.lt = new Node(left);
			if(right != '.')
				root.rt = new Node(right);
		}
		else // 루트 외에는 자기 자리를 찾아줌
			search(root, data, left, right);
	}
	
	// 검색
	void search(Node root, char data, char left, char right) {
		// 노드가 비어있으면 종료
		if(root == null) return;
		else if(root.data == data) { // 찾고 있던 노드를 찾으면 정보 입력
			if(left != '.') 
				root.lt = new Node(left);
			if(right != '.')
				root.rt = new Node(right);
		}
		else { // 왼쪽 포인터, 오른쪽 포인터로 노드 찾기
			search(root.lt, data, left, right);
			search(root.rt, data, left, right);
		}
	}
	
	
	// 전위순회
	void preOrder(Node root) {
		//root -> left -> right
		System.out.print(root.data);
		if(root.lt != null) preOrder(root.lt);
		if(root.rt != null) preOrder(root.rt);
	}
	
	// 중위순회
	void inOrder(Node root) {
		// left -> root -> right
		if(root.lt != null) inOrder(root.lt);
		System.out.print(root.data);
		if(root.rt != null) inOrder(root.rt);
	}
	
	// 후위순회
	void postOrder(Node root) {
		// left -> right -> root
		if(root.lt != null) postOrder(root.lt);
		if(root.rt != null) postOrder(root.rt);
		System.out.print(root.data);
	}
}

public class Main {		
	public static void main(String[] args) throws IOException{
		Scanner sc = new Scanner (System.in);
		int n = sc.nextInt();
		
		// 트리 정보 입력
		Tree tree = new Tree();
		for(int i = 0; i < n; i++) {
			tree.add(sc.next().charAt(0), sc.next().charAt(0), sc.next().charAt(0));
		}
			
		tree.preOrder(tree.root);
		System.out.println();
		tree.inOrder(tree.root);
		System.out.println();
		tree.postOrder(tree.root);
		
		sc.close();
	}
}