(Java)백준 1991. 트리 순회

1. 문제 조건

N개의 노드를 가진 트리가 노드 자신과 그 노드에 대한 왼쪽, 오른쪽 자식 주어지는 형태로 입력값이 들어옴.

주어진 트리를 전위, 중위, 후위 순회한 결과를 출력해야 함

 

2. 아이디어

문제에 대한 특별한 아이디어보다는 트리의 구현이 필요했던 문제.

입력되는 노드 값이 A ~ Z만 가능하므로 크기가 26인 배열을 활용해도 괜찮음(메모리 낭비 크지 않을 것이기 때문)

 

하지만 트리 구현 공부를 할 겸, 노드 클래스와 트리 클래스를 필요에 맞게 직접 만들어 구현해 봄.

 

 

3. 구현

- 아쉬운 점 : 트리 클래스의 search 부분 구현이 탐색과 삽입의 기능을 모두 하고 있어 아쉬움이 남음. search는 해당 data를 찾는 노드를 Root부터 찾기 시작해서 최종적으로 새로 들어갈 data가 들어갈 자리의 부모 노드를 반환하는 데에서 그치고, add에서 이를 삽입할 수 있도록 코드를 구현했다면 좋았을 것 같음. 아래 코드를 다른 문제에서 활용한다면 따로 분리를 해야 search의 활용도가 더 높아질 것 같기 때문.

package Silver1;

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

public class Main_1991트리순회 {

	//노드 클래스
	public static class Node<Character> {
		private final char data;
		private Node<Character> leftChild;
		private Node<Character> rightChild;

		public Node(char data) {
			this.data = data;
		}

		public char getData() {
			return data;
		}

		public Node<Character> getLeftChild() {
			return leftChild;
		}

		public void setLeftChild(Node<Character> leftChild) {
			this.leftChild = leftChild;
		}

		public Node<Character> getRightChild() {
			return rightChild;
		}

		public void setRightChild(Node<Character> rightChild) {
			this.rightChild = rightChild;
		}

	}
    
    //트리 클래스
	public static class Tree {
		static Node Root;
		
        //트리에 노드를 더하는 멤서드
		public static void add(char data, char left, char right) {
			if (Root == null) { //루트가 없으면 루트로 넣기
				if (data != '.')
					Root = new Node(data);
				if (left != '.') //왼쪽, 오른쪽 자식이 NULL이 아니면 노드 생성해서 넣기
					Root.setLeftChild(new Node(left));
				if (right != '.')
					Root.setRightChild(new Node(right));
			} else {
            	//Root가 존재하면 가장 밑단 부분을 찾아가 넣기 
				search(Root, data, left, right);
			}
		}
		
	
		//가장 밑단 부분을 찾아가 add하는 메서드
		public static void search(Node Root, char data, char left, char right) {
			if (Root == null)
				return;
			else if (Root.data == data) {
				if (left != '.')
					Root.setLeftChild(new Node(left));
				if (right != '.')
					Root.setRightChild(new Node(right));
			}else {
				search(Root.getLeftChild(), data, left, right);
				search(Root.getRightChild(), data, left, right);
			}

		}
		
		//전위순회
		public static void preOrder(Node root) {
			sb.append(root.getData());
			if(root.getLeftChild()!=null) preOrder(root.getLeftChild());
			if(root.getRightChild()!=null) preOrder(root.getRightChild());
		}
		//중위순회
		public static void inOrder(Node root) {
			if(root.getLeftChild()!=null) inOrder(root.getLeftChild());
			sb.append(root.getData());
			if(root.getRightChild()!=null) inOrder(root.getRightChild());
		}
		//후위순회
		public static void postOrder(Node root) {
			if(root.getLeftChild()!=null) postOrder(root.getLeftChild());
			if(root.getRightChild()!=null) postOrder(root.getRightChild());
			sb.append(root.getData());
		}

	}


	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int N = Integer.parseInt(br.readLine());
		Tree tree = new Tree();
		
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			char data = st.nextToken().charAt(0);
			char left = st.nextToken().charAt(0);
			char right = st.nextToken().charAt(0);
			
			tree.add(data, left, right);

		}
		
		tree.preOrder(tree.Root);
		sb.append("\n");
		tree.inOrder(tree.Root);
		sb.append("\n");
		tree.postOrder(tree.Root);
		sb.append("\n");
		
		
		System.out.println(sb.toString());
	}

	



}