BOJ.1991

#BOJ1991

트리

PS에서 자료 구조 자체를 선호하는 편은 아니라서 파이썬으로 트리를 다루는 경험은 진짜 1-2때 데이터구조 수업을 배운 후 처음인 것 같다. 물론 개념적으로는 계속해서 학습했었지만 이를 활용해서 알고리즘 문제를 해결하는 것은 또 다른 일이기 때문에 팔자에도 없는 파이썬으로 트리 구현하기를 시작했다. 클래스 자체가 익숙하지 않아 이거 보고 저거 보고 하면서 잘 만들어서 돌긴 하는데 아직도 저게 왜 제대로 나오지에 대해서 의문이 있다... 나 천잰가? 코드는 작성하고 언제나와 같이 GPT에게 주석을 도와달라고 했다. 오늘은 좀 찝찝한 풀이 같긴 한다.

import sys

class TreeNode:
    def __init__(self, data):
        self.data = data  # 노드의 데이터
        self.left = None  # 왼쪽 자식 노드
        self.right = None  # 오른쪽 자식 노드

class BinaryTree:
    def __init__(self):
        self.nodes = {}  # 모든 노드를 저장하는 딕셔너리

    def insert(self, parent, left, right):
        # 부모 노드가 아직 없으면 생성
        if parent not in self.nodes:
            self.nodes[parent] = TreeNode(parent)
        node = self.nodes[parent]

        # 왼쪽 자식 노드 처리
        if left != ".":
            if left not in self.nodes:
                self.nodes[left] = TreeNode(left)
            node.left = self.nodes[left]

        # 오른쪽 자식 노드 처리
        if right != ".":
            if right not in self.nodes:
                self.nodes[right] = TreeNode(right)
            node.right = self.nodes[right]

    def get_root(self):
        return self.nodes['A']  # 'A'를 루트 노드로 가정

    # 전위 순회 함수
    def preorder(self, node, result=[]):
        if node:
            result.append(node.data)  # 현재 노드 방문
            self.preorder(node.left, result)  # 왼쪽 서브트리 순회
            self.preorder(node.right, result)  # 오른쪽 서브트리 순회
        return result

    # 중위 순회 함수
    def inorder(self, node, result=[]):
        if node:
            self.inorder(node.left, result)  # 왼쪽 서브트리 순회
            result.append(node.data)  # 현재 노드 방문
            self.inorder(node.right, result)  # 오른쪽 서브트리 순회
        return result

    # 후위 순회 함수
    def postorder(self, node, result=[]):
        if node:
            self.postorder(node.left, result)  # 왼쪽 서브트리 순회
            self.postorder(node.right, result)  # 오른쪽 서브트리 순회
            result.append(node.data)  # 현재 노드 방문
        return result