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();