[Java] 1991번 : 트리 순회

[peppermintt0504]

원본

문제 풀이

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

이 때 각 노드는 값이 아니라 문자로 이루어져 있어 각 노드를 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);
}
[풀이 코드](https://pepperminttt.tistory.com/79#%ED%--%--%EC%-D%B-%--%EC%BD%--%EB%--%-C)
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);
	}
}