작성 코드

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

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

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

        Node(int num, Node left, Node right) {
            this.num = num;
            this.left = left;
            this.right = right;
        }

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

    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;
            }
            root.insert(Integer.parseInt(input));
        }

        postOrder(root);
    }

    static void postOrder(Node node) {
        if (node == null) {
            return;
        }

        postOrder(node.left);
        postOrder(node.right);
        System.out.println(node.num);
    }
}

설명

해당 코드는 이진 탐색 트리(Binary Search Tree)를 구현하고, 후위 순회(Post-order traversal)를 수행하는 코드입니다. 아래에 자료구조와 로직을 리스트 형태로 설명해드리겠습니다:

자료구조:

• Node: 이진 탐색 트리의 노드를 나타내는 클래스입니다. 각 노드는 정수형 num 값을 가지며, 왼쪽 자식 노드 left와 오른쪽 자식 노드 right를 가질 수 있습니다.
• root: 이진 탐색 트리의 루트 노드입니다.

로직:

• Node 클래스:

  • Node(int num): num 값을 받아 새로운 노드를 생성합니다.
  • Node(int num, Node left, Node right): num, left, right 값을 받아 새로운 노드를 생성합니다.
  • void insert(int nodeNum): 주어진 nodeNum 값을 이진 탐색 트리에 삽입합니다. 작은 값은 왼쪽 서브트리로, 큰 값은 오른쪽 서브트리로 이동하여 재귀적으로 삽입합니다.

• main 함수:

  • BufferedReader를 사용하여 표준 입력에서 첫 번째 노드의 값을 읽고, 이를 이진 탐색 트리의 루트로 설정합니다.
  • 반복문을 사용하여 표준 입력에서 숫자를 읽어들여 이진 탐색 트리에 삽입합니다. 빈 문자열이 입력되면 반복문을 종료합니다.
  • postOrder 함수를 호출하여 후위 순회를 수행합니다.

• postOrder 함수:

  • 주어진 노드가 null이면 함수를 종료합니다.
  • 왼쪽 서브트리를 후위 순회합니다.
  • 오른쪽 서브트리를 후위 순회합니다.
  • 현재 노드의 값을 출력합니다.

이진 탐색 트리는 작은 값은 왼쪽에, 큰 값은 오른쪽에 위치시키는 특성을 가지며, 후위 순회는 왼쪽 자식 노드, 오른쪽 자식 노드, 그리고 현재 노드의 값을 순서대로 출력하는 순회 방식입니다.

파이썬

import sys

class Node:
    def __init__(self, num):
        self.num = num
        self.left = None
        self.right = None

    def insert(self, nodeNum):
        if nodeNum < self.num:
            if self.left is None:
                self.left = Node(nodeNum)
            else:
                self.left.insert(nodeNum)
        else:
            if nodeNum > self.num:
                if self.right is None:
                    self.right = Node(nodeNum)
                else:
                    self.right.insert(nodeNum)

def postOrder(node):
    if node is None:
        return

    postOrder(node.left)
    postOrder(node.right)
    print(node.num)

if __name__ == '__main__':
    root = Node(int(sys.stdin.readline().strip()))
    while True:
        input_val = sys.stdin.readline().strip()
        if not input_val:
            break
        root.insert(int(input_val))

    postOrder(root)

자바스크립트

class Node {
  constructor(num) {
    this.num = num;
    this.left = null;
    this.right = null;
  }

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

function postOrder(node) {
  if (node === null) {
    return;
  }

  postOrder(node.left);
  postOrder(node.right);
  console.log(node.num);
}

function main() {
  const readline = require('readline');
  const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
  });

  let root = null;
  let firstLine = true;

  rl.on('line', (input) => {
    if (firstLine) {
      root = new Node(parseInt(input));
      firstLine = false;
    } else {
      if (input !== '') {
        root.insert(parseInt(input));
      } else {
        rl.close();
      }
    }
  }).on('close', () => {
    postOrder(root);
    process.exit(0);
  });
}

main();