[백준(Baekjoon)][자바(java)] 5639 : 이진 검색 트리 / 트리

728x90

 

www.acmicpc.net/problem/5639

 

5639번: 이진 검색 트리

트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다

www.acmicpc.net

 

문제 풀이

 

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Scanner;

public class Main {
	
	static HashMap<Integer, Node> hm = new HashMap<>();
	static StringBuilder sb = new StringBuilder();
	
	static class Node {
		private int val;			// parant/root node value
		private Node left, right;	// child/sub left node, child 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 postOrder( Node root ) {
		Node l = root.getLeft(), r = root.getRight();
		if( l != null )  postOrder( hm.get( l.getVal() ) );
		if( r != null )  postOrder( hm.get( r.getVal() ) );
	    sb.append( root.getVal() + "\n" );
	}
								// start, end, len, order
	public static void createTree( int s, int e, int l, Integer o[] ) {	
		if( l <= 1 )
			return;
		int root, left, right, i;
		int sl = -1, el = -1, sr = -1, er = -1;  // start/end post-order left/right
		int cl = 0, cr = 0;						 // calculate len left/right
		root = o[s];					// 루트 구하기
		for( i = s+1; i <= e; i++ )		// 서브 트리 구하기
			if( root < o[i] )
				break;
		sl = l > 0 && root > o[s+1] ? s+1 : -1;
		sr = l > 0 && i <= e && root < o[i] ? i : -1;
		el = sl == -1 ? -1 : sr == -1 ? e : sr-1;
		er = sr == -1 ? -1 : e;
		cl = el-sl+1;
		cr = er-sr+1;
		left = sl == -1 ? -1 : o[sl];
		right = sr == -1 ? -1 : o[sr];
		if( left != -1 )	hm.get( root ).setLeft( hm.get( left ) );
		if( right != -1 )	hm.get( root ).setRight( hm.get( right ) );
		if( cl > 0 )	createTree( sl, el, cl, o );
		if( cr > 0 )	createTree( sr, er, cr, o );
	}

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		List<Integer> order = new ArrayList<>();  // pre-order
		int n;
		while( sc.hasNext() ) {
			n = sc.nextInt();
			order.add( n );
			hm.put( n, new Node( n ) );
		}
		sc.close();
		
		int l = order.size();
		Integer o[] = (Integer[])order.toArray( new Integer[l] );
		
		createTree( 0, l-1, l, o );
		
		postOrder( hm.get( o[0] ) );  // root node
		System.out.println( sb.toString() );
        
	}
}

 

* 이진 탐색 트리( BST : Binary Search Tree )의 순회( traversal )

이진 탐색 트리의 특징
  -  루트 노드를 기준으로, 좌측의 노드들은 모두 루트 노드 값보다 작고, 우측의 노드들은 모두 루트 노드 값보다 크다

-  Node 클래스 작성  
  -  field  =>  노드의 값, 왼쪽 자식 노드, 오른쪽 자식 노드
  -  method  =>  노드의 값을 파라미터로 받는 생성자, fieldsetter, getter

-  postOrder( root ) 함수 작성
  -  post-order  :  left child  ->  right child  ->  root

-  createTree() 함수 작성
  -  pre-order  :  제일 앞 순서가 루트 노드 이다  =>  루트 노드를 구함
  -  이진 탐색 트리  루트 값보다 작은 값들은 왼쪽 서브 트리에, 루트 값보다 큰 값들은 오른쪽 서브 트리에 있다
                                    =>  /오 서브 노드들의 각각의 개수를 구함

-  노드의 개수가 미리 주어지지 않으므로 입력값이 없을 때까지 입력을 받아야 하는데, Scanner로 입력을 받고, Scanner.hasNext() 함수를 이용하여 입력 받기를 반복함

-  또한 노드의 번호가 연속되지 않기 때문에 HashMap을 생성하여 key는 노드의 값, value는 노드가 되도록 한다

 

 

반응형