[백준] 1991 트리 순회 Python

1. 문제

이진 트리를 입력 받아, 전위 순회 Preorder, 중위 순회 Inorder, 후위 순회 Postorder Traversal 한
결과를 출력하는 프로그램을 작성하시오 (이진 트리 노드의 개수 1 <= N <= 26)

* 전위 순회 - 루트 - 왼쪽 자식 - 오른쪽 자식
* 중위 순회 - 왼쪽 자식 - 루트 - 오른쪽 자식
* 후위 순회 - 왼쪽 자식 - 오른쪽 자식 - 루트
입력 순서는 각 노드와 왼쪽 자식 노드, 오른쪽 자식 노드 순이고
노드 이름은 A 부터 차례대로 알파벳 대문자로 매겨진다 
항상 A 가 루트 노드이고, 자식 노드가 없는 경우 . 으로 표현한다 

https://www.acmicpc.net/problem/1991

2. 알고리즘 분류 

는 없었고, 정글에서 [다루는 주제: 그래프 탐색 기본] 로 기재해줬다

 

3. 접근 방식

이진 트리와 이진 트리 순회에 대한 개념을 먼저 정리했다

그리고 def __init__(self) 을 쓰는 법은 알았지만 쓰는 법만 알고 왜 쓰는지, 어떻게 쓰는지는

확실하게 이해하지 못 했기 때문에 클래스와 객체 개념도 정리했다

 

4. 전체 코드

# 이진 트리를 입력 받아, 전위 순회 Preorder, 중위 순회 Inorder,
# 후위 순회 Postorder Traversal 한 결과를 출력하는 프로그램을 작성하시오
# 전위 순회 - 루트 - 왼쪽 자식 - 오른쪽 자식
# 중위 순회 - 왼쪽 자식 - 루트 - 오른쪽 자식
# 후위 순회 - 왼쪽 자식 - 오른쪽 자식 - 루트 

# 이진 트리 노드의 개수 1 <= N <= 26
# 입력 순서는 각 노드와 왼쪽 자식 노드, 오른쪽 자식 노드 순
# 노드 이름은 A 부터 차례대로 알파벳 대문자로 매겨지고
# 항상 A 가 루트 노드, 자식 노드가 없는 경우 . 으로 표현 

class Node:
    def __init__(self, value):
        # 노드 값 저장, Left/ Right 는 초기화
        self.value = value
        self.left = None
        self.right = None

    # Preorder Root L R 
    def preorder(self):
        result = [self.value] # 현재 노드를 먼저 추가 
        if self.left:
            result += self.left.preorder()
        if self.right:
            result += self.right.preorder()
        return result

    # Inorder L Root R
    def inorder(self):
        result = [] # 결과 리스트를 빈 리스트로 초기화 
        if self.left:
            result += self.left.inorder()
        result.append(self.value) # 현재 노드 추가 
        if self.right:
            result += self.right.inorder()
        return result

    # Postorder L R Root
    def postorder(self):
        result = [] # 결과 리스트를 빈 리스트로 초기화 
        if self.left:
            result += self.left.postorder()
        if self.right:
            result += self.right.postorder()
        result.append(self.value) # 현재 노드 추가 
        return result
    
if __name__ == '__main__':
    # 트리의 각 노드를 저장하는 딕셔너리
    # 노드 이름을 Key 키로, Node 객체를 Value 값으로 저장
    nodes = {}

    # 노드의 개수 
    n = int(input())

    # 각 노드와 자식 노드 정보 입력 
    for _ in range(n):
        root, left, right = input().split()
        # root 노드가 아직 nodes 에 없으면
        # 새롭게 Node 객체를 생성하여 저장
        if root not in nodes:
            nodes[root] = Node(root)
        # '.' 가 아닌 경우 (자식 노드가 있는 경우)
        # 새로운 노드를 생성하고 root 의 자식으로 연결하기 
        if left != '.':
            nodes[left] = Node(left)
            nodes[root].left = nodes[left]
        if right != '.':
            nodes[right] = Node(right) # 새로운 노드 생성 
            nodes[root].right = nodes[right] # 루트의 자식으로 연결 

    # 루트 노드 A 를 기준으로 pre/ in/ postorder 결과 출력 
    print(''.join(nodes['A'].preorder()))   # 전위 순회
    print(''.join(nodes['A'].inorder()))    # 중위 순회
    print(''.join(nodes['A'].postorder()))  # 후위 순회

5. 추가

Node 는 (), node 는 [], nodes 는 {} 를 다시 정리해 보면,

1. Node, Node 클래스 ( )

이진 트리의 각 노드를 정의한 클래스

각 노드는 자신의 값 (Value), 왼쪽 자식 (Left), 오른쪽 자식 (Right) 을 속성으로 가진다

여기서 Node() 는 새로운 노드를 생성할 때 사용하는 생성자를 의미하고

이를 통해 Node 의 클래스 인스턴스를 생성한다

Node('A') 와 같은 형태로 노드를 만들 수 있다

2. node, 노드 인스턴스 [ ]

node 는 Node 클래스의 인스턴스를 가리킨다 

특정 노드에 대한 개체이며, node.left, node.right 와 같이

해당 노드의 왼쪽이나 오른쪽 자식에 접근할 수 있다

(특정 노드의 자식 노드에 접근하는 방식)

이 인스턴스는 트리의 노드 간 연결을 관리하는 역할을 한다

3. nodes, 노드 딕셔너리 { } [ ]

nodes 는 딕셔너리 자료 구조로, 각 노드를 키로 접근할 수 있도록 관리한다

키는 알파벳 문자이고, 값은 각 노드의 인스턴스 (Node 클래스의 인스턴스)

{} 딕셔너리 자료형을 선언할 때 사용

[] 딕셔너리에서 특정 키에 접근하거나 값을 추가할 때 사용 

ex. nodes['A'] 는 Node('A') 의 인스턴스를 의미하며, 이를 통해 'A' 노드에 접근할 수 있다

 

+ 클래스는 설계도, 인스턴스는 그 설계도를 기반으로 만든 실제 객체