[백준] 1991: 트리순회

'1991- 트리 순회' 문제로 이동!

👉문제

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

예를 들어 위와 같은 이진 트리가 입력되면,

• 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
• 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
• 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)
  가 된다.

👉입력

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

예시 -
7
A B C
B D .
C E F
E . .
F . G
D . .
G . .

👉출력

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

예시 -
ABDCEFG
DBAECFG
DBEGFCA

---

✍내 풀이

import java.util.*;

public class Main {		
	static ArrayList<Character> preorder;
	static ArrayList<Character> inorder;
	static ArrayList<Character> postorder;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int num = sc.nextInt();
		ArrayList<Node> nodes = new ArrayList();
		preorder = new ArrayList();
		inorder = new ArrayList();
		postorder = new ArrayList();
		for( int i = 0 ; i < num ; i++ ) {			
			Node node = new Node();
			node.name = (char) (i + 65);
			nodes.add(node);
		}
		for( int i = 0 ; i < num ; i++ ) {
			char node = (sc.next()).charAt(0);
			char left = (sc.next()).charAt(0);
			char right = (sc.next()).charAt(0);
			Node thisnode = nodes.get(node-65);
			if( left != '.') {
				Node leftnode = nodes.get(left-65);
				thisnode.left = leftnode;
			}
			if(right != '.') {
				Node rightnode = nodes.get(right-65);
				thisnode.right = rightnode;
			}
		}
		preorder(nodes.get(0));
		inorder(nodes.get(0));
		postorder(nodes.get(0));
		for( char c : preorder ) {
			System.out.print(c);
		}
		System.out.println();
		for( char c : inorder ) {
			System.out.print(c);
		}
		System.out.println();
		for( char c : postorder ) {
			System.out.print(c);
		}
	}	
	
	static void preorder(Node node) {
		preorder.add(node.name);
		if(node.left != null) {
			preorder(node.left);
		}
		if(node.right!= null) {
			preorder(node.right);
		}
	}
	
	static void inorder(Node node) {
		if(node.left != null) {
			inorder(node.left);
		}
		inorder.add(node.name);
		if(node.right!= null) {
			inorder(node.right);
		}
	}
	
	static void postorder(Node node) {
		if(node.left != null) {
			postorder(node.left);
		}
		if(node.right!= null) {
			postorder(node.right);
		}
		postorder.add(node.name);
	}
}

class Node{
	char name;
	Node left;
	Node right;
}

---

✍Note

( 가독성을 위해 순회한 결과를 저장하는 ArrayList를 여러개 두었다. )
문제에 주어진 그대로,

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

가 각 순회에서 노드를 거치는 순서이다.

Node클래스를 두어 각 노드는 왼쪽 자식과 오른쪽 자식을 갖도록 하였다. 왼쪽 자식이 있을 때, 왼쪽 자식으로의 접근은 왼쪽 자식의 노드를 인자로 해당 순회의 함수를 재귀호출하는 방식으로 한다.
오른쪽 자식이 있을 경우도 마찬가지로 재귀의 방식.
해당 노드를 접근 할 땐, 결과를 저장하는 ArrayList에 해당 노드를 저장한다.