boj 5639 이진 검색 트리

www.acmicpc.net/problem/5639

5639번: 이진 검색 트리

자바로 트리를 처음 구현해보았습니다..

 

입력이 전위순회이므로 들어오는 대로 트리에 넣어줍니다.

이진 검색 트리는 x가 들어오면 트리의 루트노드의 값부터 비교를 합니다.

노드의 값보다 작으면 왼쪽 서브트리이고,

노드의 값보다 크면 오른쪽 서브트리로 이동하면 되고

 

이동하려는 서브트리가 null이면 그곳에 newnode를 삽입하면 됩니다.

출력은 후위순회로 출력입니다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuffer sb = new StringBuffer();
 
    static class tree {
        int x;
        tree llink;
        tree rlink;
 
        tree() {
        }
 
        tree(int x, tree llink, tree rlink) {
            this.x = x;
            this.llink = llink;
            this.rlink = rlink;
        }
    }
 
    static tree node = new tree();
 
    static void addnode(int x) {
        tree newnode = new tree(x, null, null);
 
        if (node.x == 0) {
            node.x = x;
            return;
        }
 
        tree p = node;
 
        while (p != null) {
            if (p.x > x) {
                if (p.llink == null) {
                    p.llink = newnode;
                    break;
                } else
                    p = p.llink;
            } else {
                if (p.rlink == null) {
                    p.rlink = newnode;
                    break;
                } else
                    p = p.rlink;
            }
        }
    }
 
    static void postorder(tree t) {
        if (t.llink != null)
            postorder(t.llink);
        if (t.rlink != null)
            postorder(t.rlink);
        sb.append(t.x + "\n");
    }
 
    static void input() throws Exception {
        String st;
        while (true) {
            st = br.readLine();
            if (st == null || st.length() == 0)
                break;
 
            int x = Integer.parseInt(st);
            addnode(x);
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        postorder(node);
        System.out.println(sb.toString());
    }
}