트리 순회

제출코드

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

class Main {


static Node head = new Node('A', null, null);

public static void main(String[] args) throws IOException{
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	
	int n = Integer.parseInt(br.readLine());
	
	for(int i=0;i<n;i++) {
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		char root = st.nextToken().charAt(0);
		char left = st.nextToken().charAt(0);
		char right = st.nextToken().charAt(0);
		
		insertNode(head, root,left,right);
	}
	
	preOrder(head);
	System.out.println();
	inOrder(head);
	System.out.println();
	postOrder(head);
	System.out.println();
	
	
	
}


static class Node{
	char value;
	Node left;
	Node right;
	
	Node(char value, Node left, Node right){
		this.value = value;
		this.left = left;
		this.right = right;
	}
}

public static void insertNode(Node temp, char root, char left, char right) {
	
	
	if (temp.value == root) {
		temp.left = (left == '.' ? null : new Node(left,null,null));
		temp.right = (right == '.' ? null : new Node(right,null,null)); 
	}
	else {
		if(temp.left != null) insertNode(temp.left, root, left, right);
		if(temp.right != null) insertNode(temp.right, root, left, right);
	}
}

public static void preOrder(Node node) {
	if(node ==null) return;
	System.out.print(node.value);
	preOrder(node.left);
	preOrder(node.right);
}

public static void inOrder(Node node) {
	if(node ==null) return;
	inOrder(node.left);
	System.out.print(node.value);
	inOrder(node.right);
}

public static void postOrder(Node node) {
	if(node ==null) return;
	postOrder(node.left);
	postOrder(node.right);
	System.out.print(node.value);
}
}

1. 입력 받기

BufferedReader와 StringTokenizer를 사용하여 입력을 받는다다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());

2. 트리 구성
   입력받은 노드 정보를 이용해 이진 트리를 구성한다. head는 트리의 루트 노드다. 처음에는 'A' 값을 가진 노드로 설정되어 있다.

static Node head = new Node('A', null, null);

insertNode 메소드는 트리에 노드를 삽입하는 역할을 한다.
재귀적으로 트리를 탐색하여 입력받은 부모 노드를 찾고, 해당 노드에 왼쪽 또는 오른쪽 자식 노드를 추가한다. 자식 노드가 '.'인 경우에는 해당 자식 노드를 null로 설정한다.

public static void insertNode(Node temp, char root, char left, char right) {
    if (temp.value == root) {
        temp.left = (left == '.' ? null : new Node(left,null,null));
        temp.right = (right == '.' ? null : new Node(right,null,null)); 
    }
    else {
        if(temp.left != null) insertNode(temp.left, root, left, right);
        if(temp.right != null) insertNode(temp.right, root, left, right);
    }
}

3. 트리 순회
   각각 전위 순회, 중위 순회, 후위 순회를 구현한 메소드가 있다.
   이 메소드들은 node가 null이 아닐 때까지 재귀적으로 자신을 호출하며 노드를 방문한다.

public static void preOrder(Node node) {
    if(node ==null) return;
    System.out.print(node.value);
    preOrder(node.left);
    preOrder(node.right);
}

public static void inOrder(Node node) {
    if(node ==null) return;
    inOrder(node.left);
    System.out.print(node.value);
    inOrder(node.right);
}

public static void postOrder(Node node) {
    if(node ==null) return;
    postOrder(node.left);
    postOrder(node.right);
    System.out.print(node.value);
}

전위 순회는 루트를 먼저 방문하고, 왼쪽 자식, 오른쪽 자식 순으로 순회한다.
중위 순회는 왼쪽 자식을 먼저 방문하고, 루트, 오른쪽 자식 순으로 순회한다.
후위 순회는 왼쪽 자식, 오른쪽 자식을 먼저 방문하고, 마지막으로 루트를 방문한다.

4. 결과 출력
   main 메소드에서 입력받은 노드 정보를 이용하여 트리를 구성한 후, 세 가지 순회 방법을 차례대로 호출하여 결과를 출력한다.

preOrder(head);
System.out.println();
inOrder(head);
System.out.println();
postOrder(head);
System.out.println();