알고리즘/백준(BOJ)
[백준][BOJ-1991][자바] 트리 순회
NineOne
2021. 4. 19. 21:30
1991번: 트리 순회
첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자
www.acmicpc.net
import java.util.*;
import java.io.*;
public class Main {
static Node root;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
HashMap<String, Node> hm = new HashMap<>();
StringTokenizer st;
String parents = "";
String left = "";
String right = "";
hm.put("A", new Node("A",null,null));
for(int i=0; i<T; i++) {
st = new StringTokenizer(br.readLine());
parents = st.nextToken();
left = st.nextToken();
right = st.nextToken();
Node leftNode = new Node(left, null, null);
Node rightNode = new Node(right, null, null);
if(!left.equals(".")) {
hm.get(parents).left = leftNode;
hm.put(left, leftNode);
}
if(!right.equals(".")) {
hm.get(parents).right = rightNode;
hm.put(right, rightNode);
}
}
preOrder(hm.get("A"));
System.out.println();
inOrder(hm.get("A"));
System.out.println();
postOrder(hm.get("A"));
}
public static void inOrder(Node node) {
if(node != null) {
inOrder(node.left);
System.out.print(node.data);
inOrder(node.right);
}
}
//전위순회 Preorder = Root -> Left -> Right
public static void preOrder(Node node) {
if(node != null) {
System.out.print(node.data);
preOrder(node.left);
preOrder(node.right);
}
}
//후위순회 Postorder = Left -> Right -> Root
public static void postOrder(Node node) {
if(node != null) {
postOrder(node.left);
postOrder(node.right);
System.out.print(node.data);
}
}
static class Node {
String data;
Node left;
Node right;
public Node(String data, Node left, Node right) {
super();
this.data = data;
this.left = left;
this.right = right;
}
}
}