[백준.1991 - Python] 트리 순회

📌 1991. 트리 순회

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.

예를 들어 위와 같은 이진 트리가 입력되면,

 

- 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)

- 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)

- 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)

 

 

✏️ 입력. 

첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현한다.

 

📋 출력. 

첫째 줄에 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력한다. 각 줄에 N개의 알파벳을 공백 없이 출력하면 된다.

 

 

✍️  Python : Node()

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

 

✍️  Python : 전위 순회 

def preorder(node):  # 전위 순회
    print(node.item, end='')         # 현재 노드 
    if node.left != '.':
        preorder(tree[node.left])    # 왼쪽 노드
    if node.right != '.':
        preorder(tree[node.right])   # 오른쪽 노드

- left, right 노드가 . 이면 해당 노드에 자식노드가 없는 것이므로 재귀함수가 진행되지 않는다

- 전위 순회의 순서는 현재 노드 → 왼쪽 노드 →  오른쪽 노드

- 재귀에 빠지면 해당 코드라인 이하는 실행이 미뤄지므로, 순회의 순서대로 코드를 위와 같이 작성한다

 

 

✍️  Python : 중위 순회

def inorder(node):  # 중위 순회 
    if node.left != '.':            # 왼쪽 노드
        inorder(tree[node.left])    
    print(node.item, end='')        # 현재 노드
    if node.right != '.':           # 오른쪽 노드
        inorder(tree[node.right])

- left, right 노드가 . 이면 해당 노드에 자식노드가 없는 것이므로 재귀함수가 진행되지 않는다

- 중위 순회의 순서는 왼쪽 노드 → 현재 노드 →  오른쪽 노드

- 재귀에 빠지면 해당 코드라인 이하는 실행이 미뤄지므로, 순회의 순서대로 코드를 위와 같이 작성한다

 

 

✍️  Python : 후위 순회

def postorder(node):  # 후위 순회
    if node.left != '.':              # 왼쪽 노드
        postorder(tree[node.left])
    if node.right != '.':             # 오른쪽 노드
        postorder(tree[node.right])    
    print(node.item, end='')          # 현재 노드

- left, right 노드가 . 이면 해당 노드에 자식노드가 없는 것이므로 재귀함수가 진행되지 않는다

- 후위 순회의 순서는 왼쪽 노드 → 오른쪽 노드 →  현재 노드

- 재귀에 빠지면 해당 코드라인 이하는 실행이 미뤄지므로, 순회의 순서대로 코드를 위와 같이 작성한다

 

 

✍️  Python : 실행

if __name__ == "__main__":
    cnt = int(input())
    tree = {}
    root = ""

    for _ in range(cnt):
        node, left, right = map(str, input().split())
        tree[node] = Node(item=node, left=left, right=right)
        if root == "":
            root = node

    preorder(tree[root])
    print()
    inorder(tree[root])
    print()
    postorder(tree[root])

- 이진 트리를 구현하지않고, 딕셔너리를 활용했다

 

 

✍️  Python : 최종 제출 코드

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

def preorder(node):  # 전위 순회
    print(node.item, end='')
    if node.left != '.':
        preorder(tree[node.left])
    if node.right != '.':
        preorder(tree[node.right])

def inorder(node):  # 중위 순회
    if node.left != '.':
        inorder(tree[node.left])
    print(node.item, end='')
    if node.right != '.':
        inorder(tree[node.right])

def postorder(node):  # 후위 순회
    if node.left != '.':
        postorder(tree[node.left])
    if node.right != '.':
        postorder(tree[node.right])
    print(node.item, end='')

if __name__ == "__main__":
    N = int(input())
    tree = {}
    root = ""

    for _ in range(N):
        node, left, right = map(str, input().split())
        tree[node] = Node(item=node, left=left, right=right)
        if root == "":
            root = node

    preorder(tree[root])
    print()
    inorder(tree[root])
    print()
    postorder(tree[root])