[5639] 이진 검색 트리

 

트리 문제를 풀기 위한 기본적인 틀, Node와 Tree 작성을 익히기 위해서 어제에 이어 트리 문제를 한번 더 풀었다. 이 문제에서 어려웠던 점은.. 입력을 마치는 방법이었다. 그건 검색을 통해서 Ctrl + z로 입력을 마칠 수 있다고 찾았다.

Node와 Tree의 기본적인 생성을 마치고,

키 값이 들어오면 root부터 시작해서

작으면 왼쪽, 갈 곳이 없으면 왼쪽 노드로 생성

크면 오른쪽, 갈 곳이 없으면 오른쪽 노드로 생성

이라는 간단한 원리로 문제를 풀 수 있었다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		Tree t = new Tree();
		String a;
		while((a = br.readLine()) != null) {
			t.addNode(t, Integer.valueOf(a));
		}
        
        // 후위 순회
		t.postOrder(t.root);
	}
}

class Node{
	int data;
	Node left;
	Node right;
	
	public Node(int data) {
		this.data = data;
	}
}

class Tree{
	Node root;
	
	public void addNode(Tree t, int data) {
    	// root 생성
		if(t.root == null) {
			root = new Node(data);
		} else {
        // data가 들어갈 자리 찾기
			searchNode(t.root, data);
		}
	}
	
	public void searchNode(Node node, int data) {
   		// data가 노드의 키값보다 작을 경우
		if(data < node.data) {
 			// 노드의 왼쪽 자식이 있을 경우, 왼쪽 노드로 이동
			if(node.left != null)
				searchNode(node.left, data);
            // 노드의 왼쪽 자식이 없을 경우, data를 왼쪽 자식 노드로
			else
				node.left = new Node(data);
        // data가 노드의 키값보다 클 경우
		} else if(data > node.data) {
        	// 노드의 오른쪽 자식이 있을 경우, 오른쪽 노드로 이동
			if(node.right != null)
				searchNode(node.right, data);
            // 노드의 오른쪽 자식이 없을 경우, data를 오른쪽 자식 노드로
			else
				node.right = new Node(data);
		}
	}
	
	public void postOrder(Node node) {
		if(node.left != null) {
			postOrder(node.left);
		}
		if(node.right != null) {
			postOrder(node.right);
		}
		System.out.println(node.data);
	}
}