반응형
https://www.acmicpc.net/problem/1991
1991번: 트리 순회
첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자
www.acmicpc.net
package com.ji.beakjoon;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class TreeTraversal {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
Tree tree = new Tree();
for(int i = 0; i < N; i++) {
char[] data;
data = br.readLine().replaceAll(" ", "").toCharArray();
tree.createNode(data[0], data[1], data[2]);
}
//전위 순회
tree.preorder(tree.root);
System.out.println();
//중위 순회
tree.inorder(tree.root);
System.out.println();
//후위 순회
tree.postorder(tree.root);
br.close();
}
}
class Node {
char data;
Node left;
Node right;
Node(char data) {
this.data = data;
}
}
class Tree {
Node root; //루트 노드 처음엔 null 상태
public void createNode(char data, char leftData, char rightData) {
if(root == null) { //아무것도 없는 초기 상태 - A 루트 노드 생성
root = new Node(data);
//좌우 값이 있는 경우에만 노드 생성
if(leftData != '.') {
root.left = new Node(leftData);
}
if(rightData != '.') {
root.right = new Node(rightData);
}
} else { //초기상태가 아니면 어디에 들어가야할지 찾아야함 - A 루트 노드 이후
searchNode(root, data, leftData, rightData);
}
}
//여기에서 root는 매개 변수로 들어온 로컬변수 root임을 주의
public void searchNode(Node root, char data, char leftData, char rightData) {
if(root == null) { //도착한 노드가 null이면 재귀 종료 - 찾을(삽입할) 노드 X
return;
} else if(root.data == data) { //들어갈 위치를 찾았다면
if(leftData != '.') { //.이 아니라 값이 있는 경우에만 좌우 노드 생성
root.left = new Node(leftData);
}
if(rightData != '.') {
root.right = new Node(rightData);
}
} else { //아직 찾지못했고 탐색할 노드가 남아 있다면
searchNode(root.left, data, leftData, rightData); //왼쪽 재귀 탐색
searchNode(root.right, data, leftData, rightData); //오른쪽 재귀 탐색
}
}
// 전위순회 : 루트 -> 좌 -> 우
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);
}
}728x90
'[개발관련] > 코테준비' 카테고리의 다른 글
| [백준] 알파벳 찾기 (0) | 2021.06.20 |
|---|---|
| [백준] 트리의 부모찾기 (0) | 2021.06.20 |
| [백준] 구슬탈출 4 for JAVA (0) | 2021.06.20 |
| [백준] 문자열 폭발 (0) | 2021.06.13 |
| [백준] 듣보잡 (0) | 2021.06.13 |