백준 - 1991번 - 트리 순회

1991번

import java.util.*;
import java.io.*;

class Node {
	char data;
	Node left, right;

	public Node(char data) {
		this.data = data;
	}
}
class Tree {
	Node Root;
	public void Add(char Data, char left_Data, char right_Data) {
		if (Root == null) {
			if (Data != '.') {
				Root = new Node(Data);
			}
			if (left_Data != '.') {
				Root.left = new Node(left_Data);
			}
			if (right_Data != '.') {
				Root.right = new Node(right_Data);
			}
		}
		else {
			search(Root, Data, left_Data, right_Data);
		}
	}

	public void search(Node Root, char Data, char left_Data, char right_Data) {
		if (Root == null) {
			return;
		}
		else if (Root.data == Data) {
			if (left_Data != '.') {
				Root.left = new Node(left_Data);
			}
			if (right_Data != '.') {
				Root.right = new Node(right_Data);
			}
		}
		else {
			search(Root.left, Data, left_Data, right_Data);
			search(Root.right, Data, left_Data, right_Data);
		}
	}

	public void preOrder(Node Root) {
		System.out.print(Root.data);
		if (Root.left != null) {
			preOrder(Root.left);
		}
		if (Root.right != null) {
			preOrder(Root.right);
		}
	}

	public void inOrder(Node Root) {
		if (Root.left != null) {
			inOrder(Root.left);
		}
		System.out.print(Root.data);
		if (Root.right != null) {
			inOrder(Root.right);
		}
	}

	public void postOrder(Node Root) {
		if (Root.left != null) {
			postOrder(Root.left);
		}
		if (Root.right != null) {
			postOrder(Root.right);
		}
		System.out.print(Root.data);
	}
}

public class Main{

	public static void main(String[] args) throws IOException {

		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int num = Integer.parseInt(bf.readLine());

		Tree tree = new Tree();
		for (int i = 0; i<num; i++) {
			StringTokenizer st = new StringTokenizer(bf.readLine());
			tree.Add(st.nextToken().charAt(0), st.nextToken().charAt(0), st.nextToken().charAt(0));
		}

		tree.preOrder(tree.Root);
		System.out.println();
		tree.inOrder(tree.Root);
		System.out.println();
		tree.postOrder(tree.Root);
	}
}

풀이

---

이진트리를 입력받고 전위 순회, 중위 순회, 후위 순회하여 출력하는 문제다.

Node 클래스를 만들고 변수와 왼쪽, 오른쪽 변수를 만든다.

메인에서 입력받은 값을 Tree 클래스에 add메서드를 통해서 트리에 저장한다.
여기서 맨처음에 입력받은값에 루트가 있으면 트리에 저장하게 된다.

이제 두번째 입력부터 루트 값이 있는 상태이기 때문에 add메서드의 else를 타게 되고 search메서드를 타게 된다. 여기서 처음 루트값은 A이기 때문에 당연히 루트값이 null이 아니고 두번째 입력받은 루트자리놈하고 다르다.

그래서

search(Root.left, Data, left_Data, right_Data);
search(Root.right, Data, left_Data, right_Data);

이 코드가 실행이되고 A의 왼쪽값인 B가 루트가 되고 두번째 입력받은 (B, D, . )가 search메서드를 돌면 루트가 입력받은 루트와 같아 B, D, . 가 트리에 저장이 된다.

이렇게 쭉쭉 저장되다가 맨 밑에 자식 노드가 루트가 되면 왼쪽값 오른쪽값이 없기때문에 루트가 null인 경우도 나와준다.

정리를 하면 위의 예제를 탐색할때 루트가 되보는 순서는 A, B, D, C, E, F, G 순이고 루트를 먼저보고 왼쪽으로 쭉쭉내려가고 오른쪽 체크해주고 이런식이다.


이 과정을 한줄을 입력받을때마다 반복해주면서 트리에 저장한다. 뭔가 비효율적인것 같다고 생각하지만 다른방법은 모르겠으니 한동안 이 방법을 사용해야겠다.

다시 문제로 돌아와서 이렇게 add와 search메서드를 사용해서 트리를 만들었으면 세가지 메서드로 탐색해서 각각 출력해주면된다.

전위 순회는 루트를 출력하고 계속 왼쪽이 없을때까지 재귀를 타주고 오른쪽을 확인해준다.

중위는 왼쪽 파고 루트 출력, 오른쪽파기

후위는 왼쪽파고, 오른쪽파고 루트출력이다.

재귀를 공부하고 나중에 문제를 풀어볼 필요성이 느껴진다.