[백준(Baekjoon)][자바(java)] 2263 : 트리의 순회 / 트리

 

www.acmicpc.net/problem/2263

2263번: 트리의 순회

 

문제 풀이

 

import java.io.*;
import java.util.*;

public class Main {
	
	static int n;
	static Node node[];
	static StringBuilder sb = new StringBuilder();
	
	static class Node {
		private int val;			// node value
		private Node left, right;	// sub left/right node
		public Node( int val ) {
			this.val = val;
		}
		public int getVal() {
			return val;
		}
		public void setVal( int val ) {
			this.val = val;
		}
		public Node getLeft() {
			return left;
		}
		public void setLeft( Node left ) {
			this.left = left;
		}
		public Node getRight() {
			return right;
		}
		public void setRight( Node right ) {
			this.right = right;
		}
	}
	
	public static void preOrder( Node root ) {
		if( root == null )
			return;
		sb.append( root.getVal() + " " );
		preOrder( root.getLeft() );
		preOrder( root.getRight() );
	}
									// start, end, len, order
	public static void createTree( int si, int ei, int sp, int ep, int l, int o[][] ) {
		if( l <= 1 )
			return;
		int root, left, right;
		int sil = -1, eil = -1, sir = -1, eir = -1;	// start/end in-order left/right
		int spl = -1, epl = -1, spr = -1, epr = -1;	// start/end post-order left/right
		int cl = 0, cr = 0, i;						// calculate len left/right
		root = o[1][ep];				// 루트 구하기
		for( i = si; i <= ei; i++ ) 	// 서브 트리 구하기
			if( o[0][i] == root )
				break;
		sil = i > si ? si : -1;
		eil = i > si ? i-1 : -1;
		sir = i < ei ? i+1 : -1;
		eir = i < ei ? ei : -1;
		cl = i-si;
		cr = ei-i;
		spl = cl > 0 ? sp : -1;
		epl = cl > 0 ? sp+cl-1 : -1;
		spr = cr > 0 ? ep-cr : -1;
		epr = cr > 0 ? ep-1 : -1;
		left = cl > 0 ? o[1][sp+cl-1] : -1;
		right = cr > 0 ? o[1][sp+cl+cr-1] : -1;
		if( left != -1 )	node[root].setLeft( node[left] );
		if( right != -1 )	node[root].setRight( node[right] );
		if( cl > 0 )	createTree( sil, eil, spl, epl, cl, o );
		if( cr > 0 )	createTree( sir, eir, spr, epr, cr, o );
		
	}

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader(System.in) );
		n = Integer.parseInt( br.readLine() );
		int o[][] = new int[2][n], i, j;  // in-order, post-order
		StringTokenizer st;
		for( i = 0; i < 2; i++ ) {
			st = new StringTokenizer( br.readLine() );
			for( j = 0; j < n; j++ )
				o[i][j] = Integer.parseInt( st.nextToken() );
		}
		br.close();
		
		node = new Node[n+1];
		for( i = 1; i <= n; i++ )
			node[i] = new Node( i );
		
		createTree( 0, n-1, 0, n-1, n, o ); 
		
		preOrder( node[ o[1][n-1] ] );  // root node
		System.out.println( sb.toString() );
        
	}
}

 

*  이진 트리( Binary Tree )의 순회( traversal )

-  Node 클래스 작성
  -  field  =>  노드의 값, 왼쪽 자식 노드, 오른쪽 자식 노드
  -  method  =>  각 field의 setter

-  preOrder( root ) 함수 작성  
  -  pre-order  :  root  ->  left child  ->  right child

-  createTree() 함수 작성
  -  post-order  :  제일 끝 순서가 루트 노드이다  =>  루트 노드를 구함
  -  in-order  :  루트를 기준으로 왼쪽과 오른쪽은 각각 서브트리 이다  =>  왼쪽 서브 노드들과 오른쪽 서브 노드들 각각의 개수를 구함
  -  이를 토대로 트리를 생성 한다  ( 재귀함수, 터미널 노드이면 리턴 )

-  노드의 개수는 n개 이고, 노드 값의 범위는 1~n
  =>  크기가 n인 Node[] 배열 생성 후 Node n개를 생성