[Java] 백준 1991번 문제 (트리 순회)

문제설명

 

소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main
{
	static StringBuilder sb = new StringBuilder();
	static Node root = new Node(null, null, null); //루트노드
	static class Node //노드 클래스
	{
		String value; //현재 노드의 값을 저장
		Node left; //왼쪽 자식 노드의 레퍼런스를 저장
		Node right; //오른쪽 자식 노드의 레퍼런스를 저장
		Node(String value, Node left, Node right)
		{
			this.left = left;
			this.right = right;
			this.value = value;
		}
	}
	
	static void insertNode(Node node, String value, String left, String right)
	{
        if(node == null) return; //재귀 종료조건, 리프 노드를 만나면 종료
        if(root.value == null) //루트노드 값이 null이라면
        {
        	root.value = value; //루트노드 값을 저장
        	 if(!left.equals(".")) root.left = new Node(left, null, null); //왼쪽 노드를 생성하고 가리킴
             if(!right.equals(".")) root.right = new Node(right, null, null); //오른쪽 노드를 생성하고 가리킴
        }
        else if(node.value.equals(value)) //삽입할 위치라면
        {
            if(!left.equals(".")) node.left = new Node(left, null, null); //왼쪽 노드를 생성하고 가리킴
            if(!right.equals(".")) node.right = new Node(right, null, null); //오른쪽 노드를 생성하고 가리킴
        } 
        else //삽입할 위치가 아니라면
        {
            insertNode(node.left, value, left, right); //왼쪽 자식노드로 이동(재귀)
            insertNode(node.right, value, left, right); //오른쪽 자식노드로 이동(재귀)
        }
    }
	
	public static void preOrder(Node node) //전위 순회
	{
		if(node == null) return; //재귀 종료조건, 리프 노드라면 종료
		sb.append(node.value); //현재 노드 방문(출력)
		preOrder(node.left); //왼쪽 노드로 이동(재귀)
		preOrder(node.right); //오른쪽 노드로 이동(재귀)
	}
	
	public static void inOrder(Node node) //중위 순회
	{
		if(node == null) return; //재귀 종료조건, 리프 노드라면 종료
		inOrder(node.left); //왼쪽 노드로 이동(재귀)
		sb.append(node.value); //현재 노드 방문(출력)
		inOrder(node.right); //오른쪽 노드로 이동(재귀)
	}
	
	public static void postOrder(Node node) //후위 순회
	{
		if(node == null) return; //재귀 종료조건, 리프 노드라면 종료
		postOrder(node.left); //왼쪽 노드로 이동(재귀)
		postOrder(node.right); //오른쪽 노드로 이동(재귀)
		sb.append(node.value); //현재 노드 방문(출력)
	}
	
	public static void main(String[] args) throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		for(int i = 0; i < N; ++i)
		{
			StringTokenizer st = new StringTokenizer(br.readLine());
			String value = st.nextToken();
			String left = st.nextToken();
			String right = st.nextToken();
			insertNode(root, value, left, right); //노드 삽입, 루트 노드부터 삽입 위치를 재귀적으로 찾아감
		}
		preOrder(root); //전위 순회 메소드 호출
		sb.append("\n");
		inOrder(root); //중위 순회 메소드 호출
		sb.append("\n");
		postOrder(root); //후위 순회 메소드 호출
		sb.append("\n");
		System.out.print(sb.toString());
	}
}

 

설명

• 재귀를 이용한 방법
• 자세한 코드 설명은 주석 참고