[python] 이진 탐색 트리 (binary Search tree) - 1. 클래스 정의, 초기화, 노드 추가

📗 이진 트리 (binary Search tree)

 

🔵 이진 탐색 트리 클래스 정의 및 초기화

 

 먼저  Node  클래스를 정의해 보자.   Node  클래스는 노드값인  self.val  와 왼쪽 노드  self.left  오른쪽  노드   self.right  의 속성을 가진다. 초기화 시 Node값만 주어지고 왼쪽, 오른쪽 노드는 비어있다.

 

- 노드 구성

# 노드 만들기
#       A(val)
#      /      \
# B(left)     C(right)

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

 

 Node  클래스를 만들었다면,  BinaryTree  를 만들어보자. 처음에는 Node의 값이 없는, 노드 하나를 가진 트리로 초기화한다.

- 트리 구성

 

class BinaryTree:
    # 초기값 head는 None
    def __init__(self):
        self.head = Node(None)

        self.preorder_list=[]
        self.inorder_list=[]
        self.postorder_list=[]
        

 

이제 여기에 노드를 추가하거나 삭제, 탐색할 수 있도록 메소드를 정의 주어야 한다.

 

🔵 추가 / add

 

 노드를 추가하는 메소드는 재귀를 이용해서 구현하면 된다.  item  값을 추가했을 때 노드의 값이  None  이라면 노드의 값을  item  으로 한다. 노드의 값이 있다면 대소 비교를 통해 노드의 왼쪽으로 갈 것인지, 오른쪽으로 갈 것인지 결정하며, 재귀적으로 끝에 도달하여 값을 추가하게 된다.

class BinaryTree:
    # 초기값 head는 None
    def __init__(self):...

    # 값 추가하기 head가 없을 경우
    def add(self, item):
        if self.head.val is None:
            self.head.val = item

        # head가 있으면 왼쪽배치 or 오른쪽배치
        else:
            self.__add_node(self.head, item)

    # head가 있는 경우
    def __add_node(self, cur, item):
        print('부모:', cur.val, '자식:', item)
        # head 값이 크면 왼쪽으로
        if cur.val >= item:
            if cur.left is not None:
                self.__add_node(cur.left, item)
            else:
                cur.left = Node(item)
        # head 값이 작으면 오른쪽으로
        else:
            if cur.right is not None:
                self.__add_node(cur.right, item)
            else:
                cur.right = Node(item)