[백준 1991] 트리순회(java) - 전위,중위,후위 순회

문제 보러 가기

1991번: 트리 순회

이 문제는 기본 트리구조를 생성하고 트리의 순회 방법인 전위, 중위, 후위 순회를 해보는 트리 자료구조의 기본 문제라고 볼 수 있다. 재귀를 사용하여 구현하였다.

 

트리는 다양한 방법으로 구현할 수 있다. 나의 경우 트리 클래스를 따로 만들어서 사용하였다. Node [] 배열로 만들어서 구현하는 방법도 존재한다.

 

 

 

문제풀이

 

-tree 자료구조에 입력받은 각 노드를 위치에 맞게 insert()한다.

 

-전위 순회(preOrder) : 루트 -> 왼쪽 자식 -> 오른쪽 자식

-중위 순회(inOrder) : 왼쪽 자식 -> 루트 -> 오른쪽 자식

-후위 순회(postOrder) : 왼쪽 자식 -> 오른쪽 자식 -> 루트

<루트의 순서로 기억하면 편하다>

 

-트리를 위의 순회 방법으로 돌면서 노드의 값을 출력한다.

 

 

 

 

 

package baekjoon;

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


public class Ex_1991 {

	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub

		//트리 트리순회
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int n = Integer.parseInt(br.readLine());
		Tree tree = new Tree();
		
		while(n-- > 0) {
			st = new StringTokenizer(br.readLine());
			char node = st.nextToken().charAt(0);
			char left = st.nextToken().charAt(0);
			char right = st.nextToken().charAt(0);
			tree.insert(node, left, right);
		}
		tree.preOrder(tree.root);
		System.out.println();
		tree.inOrder(tree.root);
		System.out.println();
		tree.postOrder(tree.root);
	}

}
class NodeT{
	char data;
	NodeT left;
	NodeT right;
	
	NodeT(char data){
		this.data = data;
	}
}
class Tree{
	NodeT root;
	
    //root가 없으면 입력받은 NodeT를 root로 지정 후 리턴
    //root가 존재한다면, 트리 탐색을 진행해서 적절한 위치에 삽입
	void insert(char data, char leftData, char rightData){
		if(root == null) {
			if(data!='.') 
				root = new NodeT(data);
			if(leftData!='.')
				root.left = new NodeT(leftData);
			if(rightData!='.')
				root.right = new NodeT(rightData);
		}else {
			search(root,data,leftData,rightData);
		}
	}
    //해당 data가 위치하는 곳(data가 서브트리의 root가 되는 위치)을 찾아 삽입
	void search(NodeT root, char data, char leftData, char rightData) {
		if(root == null) 
			return;
		if(root.data == data) {
			if(leftData!='.')
				root.left = new NodeT(leftData);
			if(rightData!='.')
				root.right = new NodeT(rightData);
		}else {
			search(root.left,data,leftData,rightData);
			search(root.right,data,leftData,rightData);
		}
	}
	//루트 -> 왼-> 오
	void preOrder(NodeT root) {
		System.out.print(root.data);
		if(root.left!=null)
			preOrder(root.left);
		if(root.right!=null)
			preOrder(root.right);
	}
	//왼-> 루트-> 오
	void inOrder(NodeT root) {
		if(root.left!=null) 
			inOrder(root.left);
		System.out.print(root.data);
		if(root.right!=null)
			inOrder(root.right);
	}
	//왼-> 오른-> 루트
	void postOrder(NodeT root) {
		if(root.left!=null)
			postOrder(root.left);
		if(root.right!=null)
			postOrder(root.right);
		System.out.print(root.data);
	}
}