[백준] 트리순회_1991 - 공룡 루디

[백준] 트리순회_1991 - 공룡 루디

트리순회 1991번 solved.ac 실버 1

https://www.acmicpc.net/problem/1991

문제 해석 및 풀이

이진트리를 입력받아 전위 순회, 중위 순회, 후위 순회한 결과를 출력해야 하는 문제입니다.

이진트리는 최대 차수가 2로

하나의 노드는 최대 2개의 자식노드를 가지는 트리입니다.

문제의 예시에서 순회에 대한 힌트가 있습니다.

전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)

중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)

후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)

전위 순회는 자기자신->왼쪽->오른쪽

중위 순회는 왼쪽-> 자기 자신-> 오른쪽

후위 순회는 왼쪽-> 오른쪽-> 자기 자신입니다.

이 문제에서 핵심은 트리를 구성하는 방법과

전위, 중위, 후위 순위를 구현하는 것입니다.

저는 2가지 방법으로 문제를 풀었는데

첫 번째는 Node Class를 만들어서 풀고

두 번째는 ArrayList를 활용하여 풀었습니다.

첫 번째 풀이 방법에서 Node Class는

3 가지 멤버 변수를 갖습니다.

1. char val

2. Node left

3. Node right

즉 자기 자신의 밸류와 왼쪽 자식의 링크, 오른쪽 자식의 링크를 갖습니다.

이를 토대로 Node [] tree를 만들어 링크를 연결해주고 순회를 해주면 됩니다.

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; class Node{ char val; Node left; Node right; public Node(char val, Node left, Node right) { super(); this.val = val; this.left = left; this.right = right; } } public class Main { static StringBuilder sb = new StringBuilder(); public static void preorder(Node node) { if(node==null) return; sb.append(node.val); preorder(node.left); preorder(node.right); } public static void inorder(Node node) { if(node==null) return; inorder(node.left); sb.append(node.val); inorder(node.right); } public static void postorder(Node node) { if(node==null) return; postorder(node.left); postorder(node.right); sb.append(node.val); } public static void main(String[] args) throws NumberFormatException, IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = null; int N=Integer.parseInt(br.readLine()); Node [] tree=new Node[N]; for(int i=0;i

"); inorder(tree[0]); sb.append("

"); postorder(tree[0]); sb.append("

"); System.out.println(sb.toString()); } }

두 번째 방법은 ArrayList를 활용한 구현입니다.

Node Class를 따로 만들지 않고

ArrayList >를 활용하여 각 노드가 왼쪽 자식과 오른쪽 자식을 가질 수 있게 하였고

이렇게 하지 않고 ArrayList 을 통해 정수배열을 element로 갖는 리스트를 만드는 방법도 있습니다.

여기서 왼쪽 자식과 오른쪽 자식을 구분하기 위해서 왼쪽 자식이 없는 경우, 오른쪽 자식이 없는 경우는

-1을 넣어 주었습니다.

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer; public class Main2 { static StringBuilder sb = new StringBuilder(); static ArrayList> tree=new ArrayList<>(); public static void preorder(int n) { if (n == -1) return; sb.append((char)(n+'A')); preorder(tree.get(n).get(0)); preorder(tree.get(n).get(1)); } public static void inorder(int n) { if (n == -1) return; inorder(tree.get(n).get(0)); sb.append((char)(n+'A')); inorder(tree.get(n).get(1)); } public static void postorder(int n) { if (n == -1) return; postorder(tree.get(n).get(0)); postorder(tree.get(n).get(1)); sb.append((char)(n+'A')); } public static void main(String[] args) throws NumberFormatException, IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = null; int N=Integer.parseInt(br.readLine()); for(int i=0;i()); //리스트를 생성해서 넣어주어야함 for(int i=0;i

"); inorder(0); sb.append("

"); postorder(0); sb.append("

"); System.out.println(sb.toString()); } }

from http://dino-rudy.tistory.com/36 by ccl(A) rewrite - 2021-09-07 01:00:19