5639 자바 - 트리

Sol 1)

입력받은 리스트 내에서 진행하는 방법 (따로 트리 만들지 x)

 

BufferedReader 사용할 때 한줄씩 읽어오는 방법

BufferedReader br= new BufferedReader(InputStreamReader(System.in));
while(br.readLine()!=null){

}

-> br.readLine() : 한 줄을 읽어오는 메소드

(사용자가 엔터 키를 입력할 때까지 대기하며, 사용자가 엔터 키를 입력하면 그때까지의 입력을 읽어옴)

 

 

원리는 앞선 파이썬게시글과 동일해 생략

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



public class Main {
    static ArrayList<Integer> tree=new ArrayList<>();
    static void post(int start, int end){
        if (start>end) return;
        int mid=end+1;
        for(int i=start+1;i<end+1;i++){
            if (tree.get(i)>tree.get(start)){
                mid=i;
                break;
            }
        }
        post(start+1,mid-1);
        post(mid,end);
        System.out.println(tree.get(start));
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String input;
        while(true){
            input=br.readLine();
            if(input==null||input.equals(""))
                break;
            tree.add(Integer.parseInt(input));
        }
        post(0,tree.size()-1);


    }
}

 

 

---

 

sol 2)

노드를 삽입해서 트리를 만들고나서 후위순회 거치는 방법

void insert(int num){
    if(num>this.num){
        if (this.right==null){
            Node inp=new Node(num);
            this.right=inp;
        }
        else{
            this.right.insert(num);
        }
    }
    else if(num<this.num){
        if (this.left==null){
            Node inp=new Node(num);
            this.left=inp;
        }
        else{
            this.right.insert(num);
        }
    }

}

-> 오른쪽 자식노드로 이동해서 얘에서 insert 하려면  this.right.insert(num);

 

최종코드

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



public class Main {
    static class Node{
        int num;
        Node right, left;

        Node(int n){
            this.num=n;
        }

        void insert(int num){
            if(num>this.num){
                if (this.right==null){
                    Node inp=new Node(num);
                    this.right=inp;
                }
                else{
                    this.right.insert(num);
                }
            }
            else if(num<this.num){
                if (this.left==null){
                    Node inp=new Node(num);
                    this.left=inp;
                }
                else{
                    this.left.insert(num);
                }
            }


        }

    }

    static void post(Node root){
        if (root.left!=null)
            post(root.left);
        if (root.right!=null)
            post(root.right);
        System.out.println(root.num);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Node root=new Node(Integer.parseInt(br.readLine()));

        String input;
        while(true){
            input=br.readLine();
            if(input==null||input.equals(""))
                break;
            int inpu=Integer.parseInt(input);
            root.insert(inpu);
        }
        post(root);


    }
}

 

---

sol 2) 가 조금 더 빨랐다!