백준 1991. 트리순회 [트리의 정석 문제]

🅰 백준 1991. 트리순회

1991번: 트리 순회

✏️ 문제 풀이

• 전위, 후위, 중위순회를 출력하는 문제이다. 

✏️ 소스코드

package tree;

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

public class Main_실버1_1991_트리순회 {
	private static class Node {
		char data;
		Node left = null;
		Node right = null;

		Node() {
		}

		Node(char data) {
			this.data = data;
		}
	}

	private static class Tree {
		public Node root;

		public Node getRoot() {
			return root;
		}

		public void setRoot(Node node) {
			this.root = node;
		}

		public void makeNode(char left, char data, char right) {
			if (root == null) { // root가 아무것도 없는 상태
				root = new Node(data);
				// 좌측 값이 있는 경우
				if (left != '.') {
					root.left = new Node(left);
				}
				// 우측 값이 있느 경우
				if (right != '.') {
					root.right = new Node(right);
				}
			} else { // 초기 상태가 아니면 어디에 들어가야 할지 찾기 , A 루트 노드 이후
				searchNode(root, data, left, right);
			}
		}

		public void searchNode(Node root, char data, char left, char right) {
			if (root == null) { // 도착한 root가 null이면 재귀 종료 - 삽입할 노드 없음
				return;
			} else if (root.data == data) { // 들어갈 위치를 찾았다면
				// 좌측 값이 있는 경우
				if (left != '.') {
					root.left = new Node(left);
				}
				// 우측 값이 있느 경우
				if (right != '.') {
					root.right = new Node(right);
				}
			} else { // 아직까지 찾지 못했고 탐색할 노드가 남아있다면
				searchNode(root.left, data, left, right);
				searchNode(root.right, data, left, right);
			}
		}

		public void preorder(Node root) {
			System.out.print(root.data);
			if (root.left != null)
				preorder(root.left);
			if (root.right != null)
				preorder(root.right);
		}
		
		public void inorder(Node root) {		
			if (root.left != null)
				inorder(root.left);
			System.out.print(root.data);
			if (root.right != null)
				inorder(root.right);
		}
		
		public void postorder(Node root) {
			if (root.left != null)
				postorder(root.left);
			if (root.right != null)
				postorder(root.right);
			System.out.print(root.data);
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		Tree t = new Tree();

		for (int i = 0; i < N; i++) {
			String str = br.readLine();
			char data = str.charAt(0);
			char left = str.charAt(2);
			char right = str.charAt(4);
			t.makeNode(left, data, right);
		}
		t.preorder(t.root);
		System.out.println();	
		t.inorder(t.root);
		System.out.println();
		t.postorder(t.root);
	}
}

 

✅ 후기

• 트리를 구현하는 것은 아직 복잡한 것 같다. 하지만 순열, 조합, 부분집합 처럼 꾸준히 반복하다 보면 어느순간 자연스럽게 손에서 나오는 때가 있을것이다.
• tree는 처음에 할 때도 직접 구현해야 해서 이해가 안됐었는데, 어느정도 알고리즘을 풀다보니 이제 Node의 역할, Class의 역할 등 코드가 어떻게 동작하는지에 대해 이해가 잘 된다. 이제 내것으로 만드는 노력만 하면 될것이다.

 

 

참고하기 좋은 유튜버