[알고리즘] 트리 순회 ( Tree Traversal )

 

◇  설명

  ∎  전위 순회 ( Pre-order Traversal )  --  루트 노드 -> 왼쪽 서브 트리 -> 오른쪽 서브 트리

  ∎  중위 순회 ( In-order Traversal )  --  왼쪽 서브 트리 -> 루트 노드 -> 오른쪽 서브 트리

  ∎  후위 순회 ( Post-order Traversal )  --  왼쪽 서브 트리 -> 오른쪽 서브 트리 -> 루트 노드

 

◇  코드

  Q) 이진 트리를 입력받아 전위 순회, 중위 순회, 후위 순회한 결과를 출력

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

public class Main {  // 백준 1991
	
	static List<List<Node>> e;
	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() );
	}
}