[백준 1991] 트리 순회 (JAVA)

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

1991번: 트리 순회

 

 

이번 문제는 지난 포스팅에서 다루었던 이진 트리에 대해 복습하기 좋은 문제를 다뤄보도록 하겠다.

 

만약 이진 트리의 개념에 대해 숙지가 되어있지 않거나, 혹여 잘 기억이 나지 않는다면

 

하단의 링크를 참조하면 된다.

 

https://0bliviat3.tistory.com/32

[자료구조] 이진 트리와 순회의 구현(JAVA)

 

 

문제 분석을 하자면 문제의 조건에 따라 입력된 이진트리를 코드상으로 구현하고,

이를 전위순회, 중위 순회, 후위 순회 한 결과를 차례로 출력해주기만 하면 되는 문제이다.

 

그럼 바로 코드로 구현 해보도록 하겠다.

 

먼저 노드에 대해 클래스로 먼저 정의를 하고 시작하겠다.

 

각 노드엔 현재 노드의 데이터, 그리고 이진트리이므로 왼쪽 자식노드의 데이터, 오른쪽자식 노드의 데이터를

갖고 있어야 하기에 이를 멤버변수로서 선언해주고,

또 이런 노드에 데이터를 넣어줄 생성자를 하나 만들어주어야 한다.

 

class Node {
	
	char data;
	Node left;
	Node right;
	
	Node(char data){
		this.data = data;
	}
}

 

 

이제 각 노드에 대해 표현할 클래스를 만들어 주었으니 트리를 구성하고 트리에 대해 순회할 메소드를 갖는

클래스를 만들어주도록 하겠다.

 

이 클래스의 멤버변수로는 이진트리의 루트,

그리고 순회한 결과를 순차적으로 저장할 StringBuilder 객체를 선언하도록 하겠다.

 

	private Node root;
	private StringBuilder sb = new StringBuilder();

 

 

이제 입력조건에 따라 이진 트리를 입력받기 위한 init 메소드를 만들어 주도록 하겠다.

 

먼저 현재 노드의 데이터와 현재노드의 왼쪽자식노드, 오른쪽 자신노드의 데이터를 인자로 받도록 하고,

 

문제 조건에서 루트노드는 무조건 'A'에서 시작한다고 했으므로

 

'A'인 경우 루트에 Node 객체를 생성해 저장 후 입력받은 왼쪽,오른쪽 노드의 데이터를 각각 객체를 만들어

입력받을수 있도록 한다.

 

이때 문제 조건에서 노드가 비어있는 경우는 '.'으로 주어지므로 조건문으로 걸러주도록 한다.

 

	public void init(char data, char left, char right) {
		if(data == 'A') {
			root = new Node(data);
			if(left != '.') root.left = new Node(left);
			if(right != '.') root.right = new Node(right);
		}
	}

 

이때 init 메소드에서 루트노드가 아닌 다른 노드에 대해 입력받는 경우

재귀적으로 다른 노드를 찾아야 하므로 노드를 찾아 입력한단 의미의 search 메소드도 하나 만들어주고

init 메소드에서 호출 할수 있도록 해주겠다.

 

	public void init(char data, char left, char right) {
		if(data == 'A') {
			root = new Node(data);
			if(left != '.') root.left = new Node(left);
			if(right != '.') root.right = new Node(right);
		}else {
			search(root, data, left, right);
		}
	}
    
   private void search(Node node,char data,char left,char right){
   }

 

이제 search 메소드를 작성하겠다.

 

먼제 이 메소드는 class로 선언된 노드에 대해 재귀 호출의 반복을 통해 현재노드를 찾아

데이터를 입력해주어야하는 메소드이므로,

재귀호출의 종료조건을 먼저 작성해주도록 하겠다.

 

종료조건은 현재 찾으려는 노드가 존재하지 않는경우 이므로

현재 노드가 null인 경우 리턴해주도록 한다.

 

	private void search(Node node, char data, char left, char right) {
		if(node == null) return;

	}

 

그리고 현재 노드와 입력받은 현재노드의 데이터가 일치하는 경우

문제에서 비어있는 노드의 조건인  '.' 아닌 경우 Node 객체를 생성해 저장해주도록 하고,

현재 노드의 데이터와 입력받은 데이터가 일치하지 않다면

왼쪽 노드부터 재귀호출, 그리고 오른쪽노드로 재귀호출해서 노드를 탐색하도록 한다.

 

	private void search(Node node, char data, char left, char right) {
		if(node == null) return;
		if(node.data == data) {
			if(left != '.') node.left = new Node(left);
			if(right != '.') node.right = new Node(right);
		}else {
			search(node.left,data,left,right);
			search(node.right,data,left,right);
		}
	}

 

 

이제 트리의 데이터를 입력받아 트리를 구성하는 메소드의 구현이 완료되었으니,

 

순회할 메소드를 작성해주도록 하겠다.

 

순회 또한 재귀호출의 반복을 통해 순회 순서에 따른 현재 정점의 위치만 멤버변수로 선언해 두었던,

StirngBuilder 객체에 저장해줄수 있도록 하면된다.

 

전위순회, 중위순회, 후위순회 순으로 작성했다.

 

	private void preOrder(Node node) {
		if(node == null) return;
		sb.append(node.data);
		preOrder(node.left);
		preOrder(node.right);
	}
	
	private void inOrder(Node node) {
		if(node == null) return;
		inOrder(node.left);
		sb.append(node.data);
		inOrder(node.right);
	}
	
	private void postOrder(Node node) {
		if(node == null) return;
		postOrder(node.left);
		postOrder(node.right);
		sb.append(node.data);
	}

 

마지막으로 이 모든 순회를 출력형식에 맞게 호출 후 출력하도록 하는 메소드를 하나 작성해주었다.

 

	public void prt() {
		preOrder(root);
		sb.append('\n');
		inOrder(root);
		sb.append('\n');
		postOrder(root);
		System.out.print(sb);
	}

 

그리고 코드를 실행하면,

 

 

예제에 맞는 답을 출력하는것을 확인 할 수 있다.

 

아래는 코드의 전문이다.

 

package boj3;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Boj1991 {
	
	/* 
	 * 제출 完
	 */

	private Node root;
	private StringBuilder sb = new StringBuilder();
	
	public void init(char data, char left, char right) {
		if(data == 'A') {
			root = new Node(data);
			if(left != '.') root.left = new Node(left);
			if(right != '.') root.right = new Node(right);
		}else {
			search(root, data, left, right);
		}
	}
	
	private void search(Node node, char data, char left, char right) {
		if(node == null) return;
		if(node.data == data) {
			if(left != '.') node.left = new Node(left);
			if(right != '.') node.right = new Node(right);
		}else {
			search(node.left,data,left,right);
			search(node.right,data,left,right);
		}
	}
	
	private void preOrder(Node node) {
		if(node == null) return;
		sb.append(node.data);
		preOrder(node.left);
		preOrder(node.right);
	}
	
	private void inOrder(Node node) {
		if(node == null) return;
		inOrder(node.left);
		sb.append(node.data);
		inOrder(node.right);
	}
	
	private void postOrder(Node node) {
		if(node == null) return;
		postOrder(node.left);
		postOrder(node.right);
		sb.append(node.data);
	}
	
	public void prt() {
		preOrder(root);
		sb.append('\n');
		inOrder(root);
		sb.append('\n');
		postOrder(root);
		System.out.print(sb);
	}
	
	
	public static void main(String[] args) throws IOException{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		Boj1991 tree = new Boj1991();
		int n = Integer.parseInt(in.readLine());
		char[] data;
		while(n-- > 0) {
			data = in.readLine().toCharArray();
			tree.init(data[0], data[2], data[4]);
		}
		
		in.close();
		
		tree.prt();
	}
	
}

class Node {
	
	char data;
	Node left;
	Node right;
	
	Node(char data){
		this.data = data;
	}
}