Java 코딩테스트 공부/Java 백준 문제풀이
자바 백준 1991번 문제 : 트리 순회
daramG
2022. 11. 14. 16:14
문제 출처 : https://www.acmicpc.net/problem/1991
1991번: 트리 순회
첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파
www.acmicpc.net
문제 :

소스코드 :
import java.util.*;
import java.io.*;
class Node {
char value;
Node lt, rt;
Node(char value, Node lt, Node rt) {
this.value = value;
this.lt = lt;
this.rt = rt;
}
}
public class Main
{
Node root;
public void toNode(Node node, char value, char lt, char rt) {
if (node.value == value) {
if (lt == '.') node.lt = null;
else node.lt = new Node(lt, null, null);
if (rt == '.') node.rt = null;
else node.rt = new Node(rt, null, null);
}
else {
if (node.lt != null) toNode(node.lt, value, lt, rt);
if (node.rt != null) toNode(node.rt, value, lt, rt);
}
}
// 전위 순회
public void preOrder(Node root) {
if (root == null) return;
else {
System.out.print(root.value);
preOrder(root.lt);
preOrder(root.rt);
}
}
// 중위 순회
public void inOrder(Node root) {
if (root == null) return;
else {
inOrder(root.lt);
System.out.print(root.value);
inOrder(root.rt);
}
}
// 후위 순회
public void postOrder(Node root) {
if (root == null) return;
else {
postOrder(root.lt);
postOrder(root.rt);
System.out.print(root.value);
}
}
public static void main(String[] args) throws IOException {
Main tree = new Main();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
tree.root = new Node('A', null, null);
int n = Integer.parseInt(br.readLine());
while(n-->0) {
StringTokenizer st = new StringTokenizer(br.readLine());
char value = st.nextToken().charAt(0);
char lt = st.nextToken().charAt(0);
char rt = st.nextToken().charAt(0);
tree.toNode(tree.root, value, lt, rt);
}
tree.preOrder(tree.root);
System.out.println();
tree.inOrder(tree.root);
System.out.println();
tree.postOrder(tree.root);
}
}
노드 생성과 순회 모두 재귀를 이용해 해결하였다.