[이진트리] 순회 & add

정렬되지 않은 이진트리

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

    def __str__(self):
        return f'<Node: value={self.val}, left={self.left}, right={self.right}>'

class BinaryTree:

    def __init__(self,node):
        self.head = node

    # 트리모양 그대로 (root -> left 서브트리 -> right 서브트리)
    def preorder(self):
        if self.head.val is not None:
            self.__preorder_traverse(self.head)

    def __preorder_traverse(self, cur):

        print(cur.val)

        if cur.left is not None:
            self.__preorder_traverse(cur.left)
        if cur.right is not None:
            self.__preorder_traverse(cur.right)

    # 오름차순 대로 (정렬된 이진트리인 경우에만)
    def inOrder(self):
        if self.head.val is not None:
            self.__inOrder(self.head)

    def __inOrder(self,cur):
        if cur.left is not None:
            self.__inOrder(cur.left)

        print(cur.val)

        if cur.right is not None:
            self.__inOrder(cur.right)


    ###############################
    # dfs(스택-FILO, pop()), BFS(큐-FIFO, pop(0))
    ###############################

    def dfs(self):
        if self.head.val is not None:
            self.__dfs(self.head)

    def __dfs(self,cur):
        s = [(cur, cur.val)]

        while s:
            c,v = s.pop()
            print(v)

            if c.left is None and c.right is None:
                print("끝점 !")

            if c.left is not None:
                s.append((c.left, c.left.val))
            if c.right is not None:
                s.append((c.right, c.right.val))

    #
    def bfs(self):
        if self.head.val is not None:
            self.__bfs(self.head)

    def __bfs(self,cur):
        q = [(cur, cur.val)]

        while q:
            c,v = q.pop(0)
            print(v)

            if c.left is None and c.right is None:
                print("끝점!")

            if c.left is not None:
                q.append((c.left, c.left.val))
            if c.right is not None:
                q.append((c.right, c.right.val))

def min_path_sum_dfs(root):
    min = float('inf')
    q = [(root, root.val)]

    while q: #노드값&sum 하나씩 꺼내고 트리 쭈욱 탐색하면서 min_sum 구하기
        node, cur_sum = q.pop()
        print(node.val,cur_sum,sep=' ')
        if node.left is None and node.right is None: # 트리 끝까지 옴
            if min > cur_sum :
                min = cur_sum
            print("끝점!")
            continue

        #왼쪽트리 탐색
        if node.left is not None:
            q.append((node.left, cur_sum + node.left.val))
        #오른쪽트리 탐색
        if node.right is not None:
            q.append((node.right, cur_sum + node.right.val))
    print(min)
    return min

def min_path_sum_bfs(root):
    min = float('inf')
    q = [(root, root.val)]

    while q: #노드값&sum 하나씩 꺼내고 트리 쭈욱 탐색하면서 min_sum 구하기
        node, cur_sum = q.pop(0)
        print(node.val,end=' ')
        if node.left is None and node.right is None: # 트리 끝까지 옴
            if min > cur_sum :
                min = cur_sum
            continue

        #왼쪽트리 탐색
        if node.left is not None:
            q.append((node.left, cur_sum + node.left.val))
        #오른쪽트리 탐색
        if node.right is not None:
            q.append((node.right, cur_sum + node.right.val))

    print(min)
    return min

# val, left, right
node = Node(10, Node(5, None, Node(2)), Node(5, None, Node(1, Node(-1), None)))
print(node)
bt = BinaryTree(node)
print("min_path_num**")
min_path_sum_dfs(node)
min_path_sum_bfs(node)
print("preorder**")
bt.preorder()
print("inorder**")
bt.inOrder()
print("dfs**")
bt.dfs()
print("bfs**")
bt.bfs()

 

정렬된 이진트리 (head 왼쪽은 작은값, 오른쪽은 큰값)

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

class BinaryTree:
    def __init__ (self):
        self.head = Node(None)

        self.preorder_list = []
        self.inorder_list = []
        self.postorer_list = []

    ###################
    # add
    ###################

    def add(self, item):
        if self.head.val is None:
            self.head.val = item
        else:
            self.__add_node(self.head, item)

    def __add_node(self, cur, item):
        if cur.val >= item:
            if cur.left is not None: #왼쪽트리가 비어 있지 않으면 쭈욱 더 가
                self.__add_node(cur.left, item)
            else: #왼쪽트리 비어 있으면 값 집어 넣어
                cur.left = Node(item)
        else:
            if cur.right is not None:
                self.__add_node(cur.right, item)
            else:
                cur.right = Node(item)


    ##################
    # search
    ##################

    def search(self, item): #원하는 값 찾으면 True, 없으면 False
        if self.head.val is None:
            return False
        else:
            return self.__search_node(self.head, item)

    def __search_node(self, cur, item):
        if cur.val == item :
            return True
        else:
            if cur.val >= item:
                if cur.left is not None:
                    self.__search_node(cur.left, item)
                else:
                    return False
            else:
                if cur.right is not None:
                    self.__search_node(cur.right, item)
                else:
                    return False
                    
if __name__ == '__main__':
    bt = BinaryTree()
    arr = list(map(int, input().split()))
    for i in arr:
        bt.add(i)