본문으로 건너뛰기
실습하기

트리 구현 방법

1. 트리 노드 클래스 정의​

  • 트리는 노드들이 부모-자식 관계를 가지며 연결된 계층적 자료구조입니다.

  • TreeNode 클래스는 각 노드의 데이터와 왼쪽 및 오른쪽 자식에 대한 참조를 포함합니다.


트리 노드 클래스 정의
class TreeNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

2. 이진 탐색 트리 클래스 정의​

  • 이진 탐색 트리는 각 노드가 최대 두 개의 자식을 가지며, 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큰 특성을 갖습니다.

  • BinarySearchTree 클래스는 트리의 루트 노드를 저장합니다.


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

3. 키 삽입 메소드​

  • insert 메소드는 새로운 키를 트리에 삽입합니다.

  • 삽입 과정은 노드를 적절한 위치에 배치하여 이진 탐색 트리의 속성을 유지합니다.


키 삽입 메소드 예시
def insert(self, key):
    if self.root is None:
        self.root = TreeNode(key)
    else:
        self._insert_recursive(self.root, key)

def _insert_recursive(self, node, key):
    if key < node.key:
        if node.left is None:
            node.left = TreeNode(key)
        else:
            self._insert_recursive(node.left, key)
    elif key > node.key:
        if node.right is None:
            node.right = TreeNode(key)
        else:
            self._insert_recursive(node.right, key)

4. 이진 탐색 트리 객체 생성 및 사용​

  • BinarySearchTree 클래스의 인스턴스를 생성하고, 키를 삽입하여 트리를 구성합니다.
이진 탐색 트리 객체 생성 및 사용 예시
# 이진 탐색 트리 객체 생성
bst = BinarySearchTree()

# 키 삽입
bst.insert(50)
bst.insert(30)
bst.insert(70)
bst.insert(20)
bst.insert(40)

다음 내용이 궁금하다면?

코드프렌즈 PLUS 멤버십 가입 or 강의를 등록해 주세요!