[백준] 단계별로 풀어보기(단계:29, 트리,JAVA)5639번, 이진 검색 트리

문제 링크

5639번: 이진 검색 트리

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

트리

서로 다른 두 노드를 잇는 길이 하나뿐인 그래프

트리 구조 - 위키백과, 우리 모두의 백과사전

 

이 문제에 핵심은

1. 어떤 트리에 대하여 중위, 후위 순회한 결과를 통해 전위 순회한 결과를 출력해야 한다.

2. 노드의 정점은 1..n까지 중복이 없이 주어진다.

 

전위 순회

(루트)(왼쪽 자식)(오른쪽 자식)

 

후위 순회

(왼쪽 자식)(오른쪽 자식)(루트)

 

전위 순회에 대한 값들을 이용하여 트리에 대한 구조를 얻습니다.

 

루트 노드에 대한 숫자보다 작은 숫자를 받으면 왼쪽 자식 노드

 

루트 노드에 대한 숫자보다 큰 숫자를 받으면 오른쪽 자식 노드

 

예제입력1에 대하여 알아보면

전위 순회 : 50 30 24 5 28 45 98 52 60

 

50(루트 노드)

30

루트 노드 50보다 작아서 왼쪽 자식 노드

 24

루트 노드 50보다 작아서 왼쪽 자식노드로 이동

왼쪽 자식 노드의 루트 노드 30보다 작으므로 왼쪽 자식노드

5

루트 노드 50보다 작아서 왼쪽 자식노드로 이동

노드 30보다 작아서 왼쪽 자식 노드로 이동

노드 24보다 작아서 왼쪽 자식 노드

28

루트 노드 50보다 작아서 왼쪽 자식노드로 이동

노드 30보다 작아서 왼쪽 자식 노드로 이동

노드 24보다 커서 오른쪽 자식 노드

45

루트 노드 50보다 작아서 왼쪽 자식노드로 이동

노드 30보다 커서 오른쪽 자식 노드로 이동

98

루트 노드 50보다 커서 오른쪽 자식노드로 이동

52

루트 노드 50보다 커서 오른쪽 자식노드로 이동

노드 98보다 작아서 왼쪽 자식 노드

60

루트 노드 50보다 커서 오른쪽 자식노드로 이동

노드 98보다 작아서 왼쪽 자식 노드로 이동

노드 52보다 커서 오른쪽 자식 노드

 

위 과정으로 트리의 구조를 파악한 뒤 재귀를 통해서 후위 순회을 진행하여 결과를 얻습니다.

 

후위 순회의 결과를 출력합니다.

 

문제에 해결알고리즘은

1. 전위 순회에 대한 값을 가지고 순차대로 노드의 값을 비교하면서 트리의 구조를 얻습니다.

2. 트리의 구조에서 재귀를 통해 후위 순회를 진행합니다.

3. 후위 순회로 얻은 결과값을 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 저장하였습니다.
• 전위 순회의 값으로 트리의 구조를 만드는 treeInsert함수를 실행하였습니다.
• 트리의 구조로 후위 순회를 진행하는 postOrder 재귀함수를 실행하였습니다.
• BufferedWriter에 후위 순회한 결과를 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• treeInsert는 전위순회의 값을 받아 노드들을 비교하여 트리의 구조를 만듭니다.
• postOrder는 후위 순회를 진행하는 재귀함수입니다.

 

결과 코드

import java.io.*;
import java.util.*;
public class Main {
	//트리에 관한 클래스
	static class tree{
		int root;
		tree left, right;
		public tree(int root) {
			this.root = root;
		}
		
	}
	static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
    	tree root = new tree(Integer.parseInt(br.readLine()));
        //전위 순회 값을 이용하여 트리의 구조 만들기
    	while(true) {
    		String input = br.readLine();
    		if(input == null || input.equals("")) 
    			break;
    		treeInsert(root,Integer.parseInt(input));
    	}
    	postOrder(root);	//후위 순회 진행
    	bw.write(sb.toString());	//후위 순회 결과 BufferedWriter 저장
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    }
    //후위 순회 진행
    static void postOrder(tree cur) {
    	if(cur.left!=null)	//왼쪽 자식 노드
    		postOrder(cur.left);
    	if(cur.right!=null)	//오른쪽 자식노드
    		postOrder(cur.right);
    	sb.append(cur.root + "\n");	//루트 노드
    }
    //트리의 구조 만들기
    static void treeInsert(tree root, int num) {
    	if(root.root>num) {
    		if(root.left==null)	//왼쪽 자식 노드로 이동
    			root.left = new tree(num);
    		else
    			treeInsert(root.left,num);	//왼쪽 자식노드로 설정
    	}else {
    		if(root.right==null)	//오른쪽 자식 노드로 이동
    			root.right = new tree(num);
    		else		//오른쪽 자식 노드로 설정
    			treeInsert(root.right,num);
    	}
    }
}