이진트리(BinaryTree)란?

자료구조 중의 하나로, 여러 트리 구조가 있지만, 여기에서 사용할 트리는 크기를 기준으로 나누는 이진트리를 볼 것이다.

이진 트리를 이용하면, 좀 더 효율적으로 데이터 값을 찾을 수 있다.

예를 들어,

50, 100, 150, 250, 300이 무작위로 섞여있을때 이를 이진트리에 넣으면

위 그림처럼 데이터가 담긴다. 트리의 노드보다 큰 수면 오른쪽, 작으면 왼쪽으로 이동한다.

    def search(self, target):
        if target == self.node:
            return True
        elif target > self.node:
            if self.right:
                self.right.search(target)
            else:
                return False
        else:
            if self.left:
                self.left.search(target)
            else:
                return False

#delete def
def deleteNode(tree, elem):
    if tree is None:
        print("No Number")
        return tree
    if tree.node > elem:
        tree.left = deleteNode(tree.left, elem)
    elif tree.node < elem:
        tree.right = deleteNode(tree.right, elem)
    else:
        print("Success")
        if tree.right is None:
            tmp = tree.left
            tree = None
            return tmp
        elif tree.left is None:
            tmp = tree.right
            tree = None
            return tmp
        elif tree.left and tree.right:
            l_tmp = tree.left
            r_tmp = tree.right
            while r_tmp.left:
                r_tmp = r_tmp.left
            r_tmp.left = l_tmp
            return tree.right
        else:
            print("Success")
            return None
    return tree

tree = deleteNode(tree, 292)
tree.descending()

#target = int(input(" what delete num ?"))
print("-----------")
tree = deleteNode(tree, 254)
tree = deleteNode(tree, 100)
tree.descending()
tree = deleteNode(tree, 33)
tree = deleteNode(tree, 250)
tree = deleteNode(tree, 61)
tree = deleteNode(tree, 123)
tree.descending()

이진트리를 파이썬으로 구현

Insert 구현

"""
   Program: Binary Tree
   Date: 2021. 10.  29
   Author: Lee Seung   Ju
"""
from random import *
# class part
class BinTree:
    # 생성자
    def __init__(self, elem):
        self.node = elem
        self.left = None
        self.right = None
    # 값을 넣으면 노드와 값을 비교한 후 다른 행동을 합니다.
    def insert(self, elem):
        if elem > self.node:
            if self.right:
                self.right.insert(elem)
            else: # -> elif self.right == None:
                self.right = BinTree(elem)
        else:
            if self.left:
                self.left.insert(elem)
            else: # -> elif self.left == None:
                self.left = BinTree(elem)
# main part
seed(1)
tree = BinTree(250)
for i in range(10):
    tree.insert(randint(1, 500))

insert를 했을 때, 처음에 elem은 트리의 node와 비교를 한다. 크면 오른쪽 노드에 값이 있는지 검사하고 있을 경우 오른쪽 노드의 insert로 이동하고 값이 없을 경우 오른쪽 노드로 새로 만드는 모습을 볼 수 있다. 왼쪽도 마찬가지로 실행을 한다.

그렇다면, 아래 그림처럼 형성이 된다.

이렇게 각 노드들은 왼쪽 트리와 오른쪽 트리에 None을 넣어놓는다. 그래야 트리가 None인지 아닌지 알 수 있기 때문이다.

올림 출력, 내림 출력 구현

"""
   Program: Binary Tree
   Date: 2021. 10.  29
   Author: Lee Seung   Ju
"""
from random import *
# class part
class BinTree:
    # 생성자
    def __init__(self, elem):
        self.node = elem
        self.left = None
        self.right = None
    # 값을 넣으면 노드와 값을 비교한 후 다른 행동을 합니다.
    def insert(self, elem):
        if elem > self.node:
            if self.right:
                self.right.insert(elem)
            else: # -> elif self.right == None:
                self.right = BinTree(elem)
        else:
            if self.left:
                self.left.insert(elem)
            else: # -> elif self.left == None:
                self.left = BinTree(elem)
    # 오름차순 출력
    def ascending(self):
        if self.left:
            self.left.ascending()
        print(self.node)
        if self.right:
            self.right.ascending()
    # 내림차순 출력
    def descending(self):
        if self.right:
            self.right.descending()
        print(self.node)
        if self.left:
            self.left.descending()
# main part
seed(1)
tree = BinTree(250)
for i in range(10):
    tree.insert(randint(1, 500))
print("--- 오름차순 출력 ---")
tree.ascending()
print("--- 내림차순 출력 ---")
tree.descending()

결과

사실 코드는 간단하지만 내용은 심오한 것 같다. 크기비교를 하는것이 아니라 트리의 None 유무로 출력을 결정한다는 점이 좀 인상깊은 코드이다. 올림은 간단하게 작은 수가 가장먼저 출력되어야 하므로, 왼쪽 트리먼저 확인 후 자신의 노트 출력, 마지막으로 오른쪽 트리확인을 한다.

그리고 있으면 그 트리의 올림 메서드를 다시 호출을 하니 재귀로 이어져 차근차근 출력이 되는 형태이다.