[백준] 단계별로 풀어보기(단계:29, 트리,JAVA)1991번, 트리 순회

문제 링크

1991번: 트리 순회

---

주의사항

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

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

---

문제 설명

---

접근 방법

트리

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

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

 

이 문제에 핵심은

1. 트리에 대한 정보를 가지고 전위, 중위, 후위 순회한 결과를 출력한다.

2. 노드의 이름은 A~... 알파벳으로 정해진다.

3. 루트 노드는 항상 A이며 자식 노드가 없을 때는 .으로 입력이 주어진다.

 

 

전위 순회

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

 

중위 순회

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

 

후위 순회

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

 

전위, 중위, 후위가 진행되는대로 재귀를 진행하면 간단하게 구현할 수 있습니다.

 

 

문제에 해결알고리즘은

1. 트리에 대한 정보를 저장합니다.

2. 전위 순회시 현재 노드 출력, 왼쪽 자식 노드 이동, 오른쪽 자식 노드 이동 순차적으로 수행

3. 중위 순회시 왼쪽 자식 노드 이동, 현재 노드 출력, 오른쪽 자식 노드 이동 순차적으로 수행

4. 후위 순회시 왼쪽 자식 노드 이동, 오른쪽 자식 노드 이동, 현재 노드 출력 순차적으로 수행

5. 모든 순회한 결과를 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 저장하였습니다.
• StringTokenizer를 이용하여 트리에 대한 정보를 저장하였습니다.
• 전위/중위/후위 순회를 진행하는 preOrder/InOrder/postOrder 함수를 실행하였습니다.
• BufferedWriter에 전위/중위/후위 순회한 결과들을 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• preOrder/InOrder/postOrder는 순회하는 순서대로 재귀를 진행합니다.
• leafNodeCheck는 현재 노드가 2개의 자식노드를 갖는지 확인하는 함수입니다.

 

 

결과 코드

import java.io.*;
import java.util.*;
public class Main {
	//트리 관련 클래스
	static class tree{
		int left, right;

		public tree(int left, int right) {
			super();
			this.left = left;
			this.right = right;
		}
	}
	static int N;
	static tree[] tree;		//트리 관련 정보
	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
    	StringTokenizer st;
    	N = Integer.parseInt(br.readLine());
    	tree = new tree[N];
        //트리에 대한 정보 저장
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine()," ");
    		int root = st.nextToken().charAt(0) - 65;
    		int left = st.nextToken().charAt(0) - 65;
    		int right = st.nextToken().charAt(0) - 65;
    		tree[root] = new tree(left,right);
    	}
    	preOrder(0);		//전위 순회 실행
    	sb.append("\n");
    	inOrder(0);		//중위 순회 실행
    	sb.append("\n");
    	postOrder(0);		//후위 순회 실행
    	bw.write(sb.toString() + "\n");	//순회 결과 BufferedWriter 저장
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    }
    //전위 순회 함수
    static void preOrder(int cur) {
    	char alphbet = (char) ('A' + cur);
		sb.append(alphbet);		//현재 노드 출력
    	if(leafNodeCheck(cur))	//자식 노드 없을 때
    		return;
    	if(!(tree[cur].left==-19) && tree[cur].right==-19)	//왼쪽 자식노드만 존재
        	preOrder(tree[cur].left);	//왼쪽 노드 이동
    	else if(tree[cur].left==-19 && !(tree[cur].right==-19))	//오른쪽 자식노드만 존재
    		preOrder(tree[cur].right);	//오른쪽 노드 이동
    	else {		//왼쪽, 오른쪽 자식 노드 존재
    		preOrder(tree[cur].left);	//왼쪽 노드 이동
    		preOrder(tree[cur].right);	//오른쪽 노드 이동
    	}
    	return;
    }
    //중위 순회 함수
    static void inOrder(int cur) {
    	char alphbet = (char) ('A' + cur);
    	if(leafNodeCheck(cur)) {	//자식노드 존재 X
    		sb.append(alphbet);	//현재 노드 출력
    		return;
    	}
    	if(!(tree[cur].left==-19) && tree[cur].right==-19) {	//왼쪽 자식 노드만 존재
        	inOrder(tree[cur].left);	//왼쪽 자식 노드 이동
        	sb.append(alphbet);		//현재 노드 출력
    	}else if(tree[cur].left==-19 && !(tree[cur].right==-19)) {	//으른쪽 자식 노드만 존재
    		sb.append(alphbet);	//현재 노드 출력
    		inOrder(tree[cur].right);		//오른쪽 자식 노드 출력
    	}else {		//왼쪽, 오른쪽 자식 노드만 존재
    		inOrder(tree[cur].left);	//왼쪽 자식 노드 출력
    		sb.append(alphbet);		//현재 노드 출력
    		inOrder(tree[cur].right);	//오른쪽 자식 노드 출력
    	}
    	return;
    }
    //후위 순회 함수
    static void postOrder(int cur) {
    	char alphbet = (char) ('A' + cur);
    	if(leafNodeCheck(cur)) {	//자식 노드 존재 X
    		sb.append(alphbet);	//현재 노드 출력
    		return;
    	}
    	if(!(tree[cur].left==-19) && tree[cur].right==-19) {	//왼쪽 자식 노드만 존재
        	postOrder(tree[cur].left);		//왼쪽 자식 노드 이동
        	sb.append(alphbet);		//현재 노드 출력
    	}else if(tree[cur].left==-19 && !(tree[cur].right==-19)) {	//오른쪽 자식 노드만 존재
    		postOrder(tree[cur].right);	//오른쪽 자식 노드 이동
    		sb.append(alphbet);		//현재 노드 출력
    	}else {
    		postOrder(tree[cur].left);	//왼쪽 자식 노드 이동
    		postOrder(tree[cur].right);	//오른쪽 자식 노드 이동
    		sb.append(alphbet);		//현재 노드 출력
    	}
    	return;
    }
    //자식 노드 2개가 모두 존재하는지 확인하는 함수
	static boolean leafNodeCheck(int cur) {
    	if(tree[cur].left==-19 && tree[cur].right==-19)
    		return true;
    	
    	return false;
    }
}