[백준 5639 자바] 이진 검색 트리

[백준 5639 자바] 이진 검색 트리

문제

이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진트리이다.

• 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
• 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
• 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.

전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50이다.

이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.

입력

트리를 전위 순회한 결과가 주어진다. 노드에 들어 있는 키의 값은 10^6보다 작은 양의 정수이다.

모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다. 

출력

입력으로 주어진 이진 검색 트리를 후위 순회한 결과를 한 줄에 하나씩 출력한다.

 

풀이

이걸 풀기 위해서는 이진트리를 만들 수 있어야 한다.

 

이진트리란?

각 노드가 최대 2개의 자식 노드를 가지는 트리 자료 구조이다.

이진트리의 기본 구조

• 루트 노드(Root Node) : 트리의 최상단에 있는 노드 (시작점)
• 자식 노드(Child Node) : 특정 노드에 연결된 하위 노드
• 부모 노드(Parent Node) : 자식 노드를 가진 노드
• 서브트리(Subtree) : 하나의 노드를 루트로 하는 하위 트리

        10
       /  \
      5    15
     / \     \
    2   7     20

 

이런 형태로  이진트리는 구성된다.

 

 이걸 자바코드로 작성하면

class BinaryTree {
    static class Node {
        int key;
        Node left, right;

        public Node(int item) {
            key = item;
            left = right = null;
        }
    }

    Node root;

    // 노드 삽입 (BST 기준)
    public Node insert(Node root, int key) {
        if (root == null) {
            return new Node(key);
        }
        if (key < root.key) {
            root.left = insert(root.left, key);
        } else {
            root.right = insert(root.right, key);
        }
        return root;
    }

 }

이문제에서는 후위 순회한 결과를 출력해야 한다.

후위 순회는 이진트리를 순회하는 방법 중 하나로, 왼쪽 → 오른쪽 → 루트(부모 노드)의 순서로 노드를 방문하는 방식이다.

        10
       /  \
      5    15
     / \     \
    2   7     20

이 트리는 후위 순회를 하면

2 → 7 →5 →20 →15 →10 순으로 순회하면서 방문한다.

이걸 코드로 작성하면

		public void postorder(Node node) {
			if(node!=null) {
				postorder(node.left);
				postorder(node.right);
				
				System.out.println(node.key);
				
			}
		}

위의 이진트리 코드와 후위순회 코드를 합치면  코드를 사용하면 이 문제를 풀 수 있다.

코드

public class Main {
	
	static class Node{
		int key;
		Node left,right;
		
		public Node(int item) {
			key=item;
			left=right=null;
		}
		
		Node root;
	
		

		
		public Node insert(Node root,int key) {
			if(root==null) {
				return new Node(key);
			}
			if(key<root.key) {
				root.left=insert(root.left,key);
			}
			else {
				root.right=insert(root.right,key);
			}
			
			return root;
			
		}
		
		
		//후위 순회 왼쪽 오른쪽 루트
		public void postorder(Node node) {
			if(node!=null) {
				postorder(node.left);
				postorder(node.right);
				
				System.out.println(node.key);
				
			}
		}
		
	
	}
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		
		ArrayList<Integer> arr = new ArrayList<Integer>();
		arr.add(Integer.parseInt(br.readLine()));
        String input;
        while (true) {
            input = br.readLine();
            if (input == null || input.equals(""))
                break;
            arr.add(Integer.parseInt(input));
        }
        
        Node node=new Node(arr.get(0));
        node.root=node;
        for(int i=1;i<arr.size();i++) {
        	node.root=node.insert(node.root, arr.get(i));
        }
        
        node.postorder(node.root);
		
		
		
		

	}

}