[자료구조] 파이썬으로 이진 트리(Binary tree) 구현하기 | 루트 노드 인덱스 1 케이스

이진 트리

이진 트리(Binary tree)는 각 노드의 자식 노드의 개수가 2개 이하로 구성되어 있는 트리입니다. 이진 트리는 포화 이진 트리, 완전 이진 트리 등이 있습니다. 포화 이진 트리(perfect binary tree)는 트리의 높이가 모두 일정하며 모든 리프 노드가 꽉 찬 이진 트리이며, 완전 이진 트리(complete binary tree)는 마지막 레벨을 제외하고서는 완전하게 노드들이 채워져 있고, 마지막 레벨에는 왼쪽부터 채워진 이진 트리입니다.

 

이진 트리를 구성하는 자료구조의 형태는 리스트를 활용할 수 있습니다. 리스트의 인덱스에 해당 하는 값을 입력해서 트리를 채우는 방식으로 구현이 가능합니다. 

기본 구조 및 데이터 삽입

이진 트리를 만들기 위한 클래스를 선언하고, 리스트에 값을 넣는 함수(insert)와 현재 트리를 반환하는 함수(display)를 작성하였습니다. 다만, 파이썬의 경우 인덱스가 0부터 시작하기 때문에 편의상 1부터 맞춰주기 위해 첫 번째 인덱스는 비워두도록 구성하였습니다. 

 

class BinaryTree:
    def __init__(self):
        # 이진 트리를 위한 리스트, 첫 번째 인덱스(0)는 비워둠
        self.tree = [None]

    def insert(self, value):
        # 리스트 끝에 새 값을 추가하여 트리에 삽입
        self.tree.append(value)
        
     def display(self):
        # 현재 트리의 상태를 출력 (리스트 형태로)
        return self.tree

자식 노드

이진 트리는 두가지 갈래(왼쪽, 오른쪽)로 나뉩니다. 각각의 자식 노드를 가져오기 위해 별도의 인덱스 접근법이 필요합니다. 가장 상단에 있는 루트 노드를 1로 두고 작성하였을 때는 현재 인덱스(index) 기준으로 아래와 같이 접근할 수 있습니다.

• 왼쪽 자식 노드 : 2 * index (제약 조건 : 2 * index 가 노드 개수보다 작거나 같은 경우)
• 오른쪽 자식 노드 : 2 * index + 1 (제약 조건 : 2 * index + 1 가 노드 개수보다 작거나 같은 경우)

이를 파이썬으로 구현하면 아래와 같습니다.

 

    def get_left_child(self, index):
        # 왼쪽 자식의 인덱스 계산 (2 * index)
        left_index = 2 * index
        # 인덱스가 리스트 범위를 넘지 않았을 때만 반환
        if left_index < len(self.tree):
            return self.tree[left_index]
        return None

    def get_right_child(self, index):
        # 오른쪽 자식의 인덱스 계산 (2 * index + 1)
        right_index = 2 * index + 1
        # 인덱스가 리스트 범위를 넘지 않았을 때만 반환
        if right_index < len(self.tree):
            return self.tree[right_index]
        return None

부모 노드

자식 노드는 리스트에서 더 하단에 있기 때문에 인덱스가 커졌다면, 부모 노드는 상단에 위치하기 때문에 나눗셈으로 인덱스를 줄여줍니다. 제약 조건은 현재 노드가 루트 노드가 아니어야 합니다.

 

    def get_parent(self, index):
        # 부모 노드의 인덱스 계산 (index // 2)
        if index == 1:
            return None  # 루트 노드는 부모가 없음
        parent_index = index // 2
        return self.tree[parent_index]

전체 코드

위 내용을 전체 코드로 구현하면 아래와 같이 작성할 수 있습니다.

 

class BinaryTree:
    def __init__(self):
        self.tree = [None]

    def insert(self, value):
        self.tree.append(value)

    def get_left_child(self, index):
        left_index = 2 * index
        if left_index < len(self.tree):
            return self.tree[left_index]
        return None

    def get_right_child(self, index):
        right_index = 2 * index + 1
        if right_index < len(self.tree):
            return self.tree[right_index]
        return None

    def get_parent(self, index):
        if index == 1:
            return None 
        parent_index = index // 2
        return self.tree[parent_index]

    def display(self):
        return self.tree

참고자료

[1] https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%ED%8A%B8%EB%A6%AC#:~:text=%EC%BB%B4%ED%93%A8%ED%84%B0%20%EA%B3%BC%ED%95%99%EC%97%90%EC%84%9C%20%EC%9D%B4%EC%A7%84%20%ED%8A%B8%EB%A6%AC,%EC%98%A4%EB%A5%B8%EC%AA%BD%20%EC%9E%90%EC%8B%9D%20%EB%85%B8%EB%93%9C%EB%9D%BC%EA%B3%A0%20%ED%95%9C%EB%8B%A4.

이진 트리 - 위키백과, 우리 모두의 백과사전

[2] Do it! 알고리즘 코딩 테스트 : 파이썬 편