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

 

www.acmicpc.net/problem/1991

1991번: 트리 순회

 

문제 풀이

 

▶  Node[]

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

public class Main {
	
	static StringBuilder sb = new StringBuilder();
	
	static class Node {
		private char val;			// parant(root) node value
		private Node left, right;	// child(sub) left node, child right node
		public char getVal() {
			return val;
		}
		public void setVal( char 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() );
	}
	
	public static void inOrder( Node root ) {
		if( root == null )
			return;
		inOrder( root.getLeft() );
		sb.append( root.getVal() );
		inOrder( root.getRight() );
	}
	
	public static void postOrder( Node root ) {
		if( root == null )
			return;
		postOrder( root.getLeft() );
	    postOrder( root.getRight() );
	    sb.append( root.getVal() );
	}

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader(System.in) );
		int n = Integer.parseInt( br.readLine() ), i, j, r;
		char c[] = new char[3];   // root node value, child left node, child right node
		Node node[] = new Node[26], sl, sr;	// sub left node, sub right node
		for( i = 0; i < 26; i++ ) 
			node[i] = new Node();
		StringTokenizer st;
		for( i = 0; i < n; i++ ) {
			st = new StringTokenizer( br.readLine() );
			for( j = 0; j < 3; j++ )
				c[j] = st.nextToken().charAt(0);
			r = c[0]-'A';
			sl = c[1] == '.' ? null : node[c[1]-'A'];
			sr = c[2] == '.' ? null : node[c[2]-'A'];
			node[r].setVal( c[0] );
			node[r].setLeft( sl );
			node[r].setRight( sr );
		}
		br.close();
		
		preOrder( node[0] );	sb.append( "\n" );
		inOrder( node[0] );		sb.append( "\n" );
		postOrder( node[0] );	sb.append( "\n" );
		
		System.out.println( sb.toString() );
        
	}
}

 

*  이진 트리의 순회( traversal )  --  전위( pre-order ) 순회, 중위( in-order ) 순회, 후위( post-order ) 순회

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

- preOrder( root ), inOrder( root ), postOrder( root ) 함수 작성
  -  pre-order  :  root  ->  left child  ->  right child
  -  in-order  :  left child  ->  root  ->  right child
  -  post-order  :  left child  ->  right child  ->  root

-  노드의 개수는 최대 26개 이고, 노드 값의 범위는 A~Z, 루트 노드는 A 
  =>  크기가 26인 Node[] 배열 생성 후 Node 26개를 미리 생성 

 

▶  HashMap<Character, Node>

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

public class Main {

	static HashMap<Character, Node> node = new HashMap<>();
	static StringBuilder sb = new StringBuilder();
	
	static class Node {
		private char val;			// parant/root node value
		private Node left, right;	// child/sub left node, child right node
		public Node( char val ) {
			this.val = val;
		}
		public char getVal() {
			return val;
		}
		public void setVal( char 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 ) {
		Node l = root.getLeft(), r = root.getRight();
		sb.append( root.getVal() );
		if( l != null )	preOrder( node.get( l.getVal() ) );
		if( r != null )	preOrder( node.get( r.getVal() ) );
	}
	
	public static void inOrder( Node root ) {
		Node l = root.getLeft(), r = root.getRight();
		if( l != null )	inOrder( node.get( l.getVal() ) );
		sb.append( root.getVal() );
		if( r != null )	inOrder( node.get( r.getVal() ) );
	}
	
	public static void postOrder( Node root ) {
		Node l = root.getLeft(), r = root.getRight();
		if( l != null )	postOrder( node.get( l.getVal() ) );
		if( r != null )	postOrder( node.get( r.getVal() ) );
	    sb.append( root.getVal() );
	}

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader(System.in) );
		int n = Integer.parseInt( br.readLine() ), i, j;
		char c[][] = new char[n][3];  // root node value, child left node, child right node					
		StringTokenizer st;
		for( i = 0; i < n; i++ ) {
			st = new StringTokenizer( br.readLine() );
			for( j = 0; j < 3; j++ )
				c[i][j] = st.nextToken().charAt(0);
			node.put( c[i][0], new Node( c[i][0] ) );
		}
		br.close();
		
		char v, l, r;
		for( i = 0; i < n; i++ ) {
			v = c[i][0];
			l = c[i][1];
			r = c[i][2];
			if( l != '.' )	node.get( v ).setLeft( node.get( l ) );
			if( r != '.' )	node.get( v ).setRight( node.get( r ) );
		}
		
		preOrder( node.get('A') );	sb.append( "\n" );
		inOrder( node.get('A') );	sb.append( "\n" );
		postOrder( node.get('A') );	sb.append( "\n" );
		
		System.out.println( sb.toString() );

	}
}