algorithm-python/5639.py at main · letsjo/algorithm-python · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
# 이진 검색 트리

# import sys
# MAX_NUM = 10000

# input = sys.stdin.readline

# tree = [None] * (MAX_NUM*4)


# def pushNumber(index, number):
#     if tree[index] is None:
#         tree[index] = number
#         return
#     if tree[index] > number:
#         return pushNumber(2*index+1, number)
#     if tree[index] <= number:
#         return pushNumber(2*index+2, number)


# def postOrder(index):
#     if tree[2*index+1] is not None:
#         postOrder(2*index+1)
#     if tree[2*index+2] is not None:
#         postOrder(2*index+2)
#     print(tree[index])
#     return


# n = 0
# while True:
#     try:
#         number = int(input())
#         pushNumber(n, number)
#     except:
#         break

# postOrder(0)

import sys
sys.setrecursionlimit(10000)


class Node:
    def __init__(self, key, value, left, right):
        self.key = KeyboardInterrupt
        self.value = value
        self.left = left
        self.right = right


class BinarySearchTree():
    def __init__(self) -> None:
        self.root = None

    def add(self, key, value) -> bool:
        def add_node(node, key, value) -> None:
            if key < node.key:
                if node.left is None:
                    node.left = Node(key, value, None, None)
                else:
                    add_node(node.left, key, value)
            else:
                if node.right is None:
                    node.right = Node(key, value, None, None)
                else:
                    add_node(node.right, key, value)
            return True

        if self.root is None:
            self.root = Node(key, value, None, None)
            return True
        else:
            return add_node(self.root, key, value)

    def dump(self):
        def print_subtree(node):
            if node is not None:
                print_subtree(node.left)
                print_subtree(node.right)
                print(f'{node.value}')
        root = self.root
        print_subtree(root)

    def remove(self, key) -> bool:
        node = self.root
        parent = None
        is_left_child = True

        while True:
            if node is None:
                return False
            if key == node.key:
                break
            else:
                parent = node
                if key < node.key:
                    node = node.left
                    is_left_child = True
                else:
                    node = node.right
                    is_left_child = False

        if node.left is None:
            if node is self.root:
                self.root = node.right
            elif is_left_child:
                parent.left = node.right
            else:
                parent.right = node.right

        elif node.right is None:
            if node is self.root:
                self.root = node.left
            elif is_left_child:
                parent.left = node.left
            else:
                parent.right = node.left

    def search(self, key) -> int:
        node = self.root
        while True:
            if node is None:
                return -1
            if key == node.key:
                return node.value
            elif key < node.key:
                node = node.left
            else:
                node = node.right


input = sys.stdin.readline

tree = BinarySearchTree()

while True:
    try:
        number = int(input())
        tree.add(number, number)
    except:
        break

tree.dump()