[코딩테스트] 이진 검색 트리

ㆍ문제

ㆍ내가 생각한 문제핵심

1. 이진 검색 트리를 전위순환 출력값을 후위순환로 출력해야 한다.
   -> 입력값을 이진검색트리로 구현 후 후위순환으로 출력
2. 얼마나 입력받을 지 알려주지 않고 입력만 한다.
   -> Scanner의 hasnext()를 이용해서 while문을 돌린다.

ㆍ나의 코드

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

public class Main {
	// root 노드용 변수
    static NodeA root = null;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        Scanner scan = new Scanner(System.in);
        // root 노드 설정을 위한 입력
        int data = scan.nextInt();
        // root 노드 설정
        root = addNode(null, data);

		// 입력이 끝날 때까지 반복
        while (scan.hasNext()) {
            int a = scan.nextInt();
			// 노드삽입용 함수
            addNode(root, a);
        }

		// 후위순환출력용 함수
        prints(root);
    }

	// 노드삽입 함수
    private static NodeA addNode(NodeA node, int data) {
    	// node가 null -> 이전노드에 하위노드가 없다 or root노드가 없다.
        // node를 생성 후 return
        if (node == null) {
            return new NodeA(data);
        } else {
        	// 만약 노드데이터보다 크면 오른쪽노드 삽입 후 재귀
            // 만약 노드데이터보다 작으면 왼쪽노드 삽입 후 재귀
            if (node.data < data) {
                node.rNode = addNode(node.rNode, data);
            } else {
                node.lNode = addNode(node.lNode, data);
            }
        }

        return node;
    }

	// 출력용 함수
    private static void prints(NodeA node) {
    	// 노드가 null -> 이전 노드의 하위노드가 없다
        if (node == null) {
            return;
        }
        // 왼쪽노드 쭉 탐색 -> 오른쪽 노드 탐색 -> 데이터출력
        prints(node.lNode);
        prints(node.rNode);
        System.out.println(node.data);
    }
}

// 노드클래스
class NodeA {
    int data;
    NodeA lNode;
    NodeA rNode;

	// 노드생성자
    NodeA(int data) {
        this.data = data;
        lNode = null;
        rNode = null;
    }
}

ㆍ느낀점

트리에 대해서 공부하고 이진검색트리를 접하니 구현하는게 상대적으로 쉬웠다.

 

물론 순간순간 헷갈리는 것도 많았어서 좀 더 반복학습하는게 좋을 것 같다.