[Java] 백준 5639번 이진 검색 트리

트리 문제입니다.

노드 클래스를 생성합니다.

static public class Node {
    Node left;
    Node right;
    int value;

    public Node(int value) {
      this.value = value;
    }

노드 클래스는 왼쪽 노드와 오른쪽 노드, 현재 값을 가집니다.

노드 클래스에 자식을 붙이는 함수를 추가해 주었습니다.

public void makeChild(int num) {
  if (num < value) {
    if (this.left != null) {
      this.left.makeChild(num);
    } else {
      this.left = new Node(num);
    }
  } else {
    if (this.right != null) {
      this.right.makeChild(num);
    } else {
      this.right = new Node(num);
    }
  }
}

재귀함수를 통해서 이분탐색형식으로 자신의 위치를 찾아갑니다.

위의 과정을 입력받은 값에 반복하면 루트노드에 입력값들이 전부 각자의 자리에 위치합니다.

여기서 루트노드를 기준으로 postOrder(후위순회)를 진행해줍니다.

static public void postOrder(Node node) {
    if (node.left != null) {
      postOrder(node.left);
    }
    if (node.right != null) {
      postOrder(node.right);
    }
    System.out.print(node);
}

최종 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

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

    String input = "";
    Node rootNode = new Node(Integer.parseInt(br.readLine()));

    while ((input = br.readLine()) != null) {
      rootNode.makeChild(Integer.parseInt(input));
    }

    postOrder(rootNode);
  }

  static public void postOrder(Node node) {
    if (node.left != null) {
      postOrder(node.left);
    }
    if (node.right != null) {
      postOrder(node.right);
    }
    System.out.print(node);
  }

  static public class Node {
    Node left;
    Node right;
    int value;

    public Node(int value) {
      this.value = value;
    }

    public void makeChild(int num) {
      if (num < value) {
        if (this.left != null) {
          this.left.makeChild(num);
        } else {
          this.left = new Node(num);
        }
      } else {
        if (this.right != null) {
          this.right.makeChild(num);
        } else {
          this.right = new Node(num);
        }
      }
    }

    public String toString() {
      return value + "\n";
    }
  }
}