[백준 / Java] 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

---

문제 풀이

 해당 문제는 노드에 대한 이해도와 순회에 대한 이해도를 높이기 좋은 문제이다. 노드를 입력 받아 해당 트리를 전위, 중위, 후위 순회로 출력하면 된다.

 이 때 각 노드는 값이 아니라 문자로 이루어져 있어 각 노드를 Map에 저장해두어 노드를 삽입해야 한다.

 

아래는 Node 클래스이다. 노드는 생성시 노드의 값(알파벳)으로 저장하고 각 노드는 null로 비워둔다.

	public static class Node{
		String val;
		Node left;
		Node right;
		
		public Node() {}
		public Node(String val) {
			this.val = val;
			left = null;
			right = null;
		}
		
		public void setRight(Node r) {
			this.right = r;
		}
        
		public void setLeft(Node l) {
			this.left = l;
		}
	}

 

 해당 노드 클래스를 통해 모든 입력을 받아 트리를 완성하면 된다. 이 때 처음 입력인 A는 root이다. 노드를 삽입하며 Map에 저장 되지 않은 노드를 꼭 저장 해야 한다. 그렇지 않으면 하위 노드의 주소를 알 방법이 없어지기 때문이다.

 

while(T-- > 0) {
			String[] temp = br.readLine().split(" ");
			
			Node tempNode;
			
			if(memo.containsKey(temp[0])) {
				tempNode= memo.get(temp[0]);
			}else {
				tempNode = new Node(temp[0]); 
				memo.put(temp[0],tempNode);
			}
			
			if(!temp[1].equals(".")) {
				if(memo.containsKey(temp[1])) {
					tempNode.setLeft(memo.get(temp[1]));
				}else {
					Node leftNode = new Node(temp[1]); 
					tempNode.setLeft(leftNode);
					memo.put(temp[1],leftNode);
				}
			}
			if(!temp[2].equals(".")) {
				if(memo.containsKey(temp[2])) {
					tempNode.setRight(memo.get(temp[2]));
				}else {
					Node rightNode = new Node(temp[2]); 
					tempNode.setRight(rightNode);
					memo.put(temp[2],rightNode);
				}
			}
		}

 

 이제 입력 받은 트리를 각 순회로 출력을 해야 한다. 이 때 각 순회는 아래 방법과 같다.

• 전위 순회 :  (루트) (왼쪽 자식) (오른쪽 자식)
• 중위 순회 :  (왼쪽 자식) (루트) (오른쪽 자식)
• 후위 순회 :  (왼쪽 자식) (오른쪽 자식) (루트)

해당 순서별로 재귀 함수를 생성해준다.

public static void preorderTraversal(Node root) throws IOException {
		bw.write(root.val);
		if(root.left != null)preorderTraversal(root.left);
		if(root.right != null)preorderTraversal(root.right);
}
	
public static void inorderTraversal(Node root) throws IOException {
    if(root.left != null)inorderTraversal(root.left);
    bw.write(root.val);
    if(root.right != null)inorderTraversal(root.right);
}
	
public static void postorderTraversal(Node root) throws IOException {
    if(root.left != null)postorderTraversal(root.left);
    if(root.right != null)postorderTraversal(root.right);
    bw.write(root.val);
}

---

풀이 코드

import java.util.*;
import java.io.*;
public class Main {
	public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
	public static Map<String,Node> memo = new HashMap<>();
	
	public static class Node{
		String val;
		Node left;
		Node right;
		
		public Node() {}
		
		public Node(String val) {
			this.val = val;
			left = null;
			right = null;
		}
		
		public void setRight(Node r) {
			this.right = r;
		}
		
		public void setLeft(Node l) {
			this.left = l;
		}
	}
	
	public static void main(String[] args) throws IOException{

		int T = Integer.parseInt(br.readLine());
		
		
		
		while(T-- > 0) {
			String[] temp = br.readLine().split(" ");
			
			Node tempNode;
			
			if(memo.containsKey(temp[0])) {
				tempNode= memo.get(temp[0]);
			}else {
				tempNode = new Node(temp[0]); 
				memo.put(temp[0],tempNode);
			}
			
			if(!temp[1].equals(".")) {
				if(memo.containsKey(temp[1])) {
					tempNode.setLeft(memo.get(temp[1]));
				}else {
					Node leftNode = new Node(temp[1]); 
					tempNode.setLeft(leftNode);
					memo.put(temp[1],leftNode);
				}
			}
			if(!temp[2].equals(".")) {
				if(memo.containsKey(temp[2])) {
					tempNode.setRight(memo.get(temp[2]));
				}else {
					Node rightNode = new Node(temp[2]); 
					tempNode.setRight(rightNode);
					memo.put(temp[2],rightNode);
				}
			}
		}
		
		preorderTraversal(memo.get("A"));
		bw.write("\n");
		inorderTraversal(memo.get("A"));
		bw.write("\n");
		postorderTraversal(memo.get("A"));
		bw.flush();
		bw.close();
	}
	
	public static void preorderTraversal(Node root) throws IOException {
		bw.write(root.val);
		if(root.left != null)preorderTraversal(root.left);
		if(root.right != null)preorderTraversal(root.right);
	}
	
	public static void inorderTraversal(Node root) throws IOException {
		if(root.left != null)inorderTraversal(root.left);
		bw.write(root.val);
		if(root.right != null)inorderTraversal(root.right);
	}
	
	public static void postorderTraversal(Node root) throws IOException {
		if(root.left != null)postorderTraversal(root.left);
		if(root.right != null)postorderTraversal(root.right);
		bw.write(root.val);
	}
}