[백준알고리즘/1991번/파이썬] 트리순회

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

1991번: 트리 순회

문제: 이진 트리가 주어졌을 때, 전위 순회 / 중위 순회 / 후위 순회 결과를 출력하는 문제 입니다.

 

풀이 방법: 3가지 트리 순회

 

풀이 코드:

import sys

n = int(input())
binaryTree = dict()

for _ in range(n):
    root,left,right = sys.stdin.readline().rstrip().split()
    binaryTree[root] = [left,right]

def preorderTraversal(node):
    if node != '.':
        print(node,end='')
        for newNode in binaryTree[node]:
            preorderTraversal(newNode)

def inorderTraversal(node):
    if node != '.':
        newNode1, newNode2 = binaryTree[node]
        inorderTraversal(newNode1)
        print(node,end='')
        inorderTraversal(newNode2)

def postorderTraversal(node):
    if node != '.':
        for newNode in binaryTree[node]:
            postorderTraversal(newNode)
        print(node,end='')

preorderTraversal('A')
print()
inorderTraversal('A')
print()
postorderTraversal('A')

 

풀이 설명:

binaryTree = dict()

for _ in range(n):
    root,left,right = sys.stdin.readline().rstrip().split()
    binaryTree[root] = [left,right]

해당 노드를 직접 방문하여 어떠한 처리를 해주는 것이 아닌 노드의 위치만 구분 할 수 있으면 되므로 dictionary를 사용해주었습니다.

 

A의 왼쪽 노드가 B, 오른쪽 노드가 C라고 했을 때 A,B,C를 입력하게 되면

binaryTree[A] = [ B , C ]가 되어  binaryTree[A][0]는 왼쪽 노드를 binaryTree[A][1]은 오른쪽 노드를 의미하게 됩니다.

 

 

 

문제에서 주어진 트리는 다음과 같습니다.

 

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

 

 

def preorderTraversal(node):
    if node != '.':
        print(node,end='')
        for newNode in binaryTree[node]:
            preorderTraversal(newNode)

전위 순회는 현재 노드 - 왼쪽 서브 트리 - 오른쪽 서브 트리 순으로 순회하는 방식을 말합니다.

따라서, node에 대한 출력을 먼저 해준 후, 왼쪽 트리부터 순회를 시작합니다.

 

다음과 같이 탐색을 하게 된다면, binaryTree[node][0]가 왼쪽 노드를 의미하므로 왼쪽 먼저 탐색을 진행한 후, 오른쪽 노드를 탐색하게 됩니다.

 

문제에서 주어진 트리를 예시로 보자면,  A - B -D - C - E - F -G 순으로 탐색하게 됩니다.

 

 

 

def inorderTraversal(node):
    if node != '.':
        newNode1, newNode2 = binaryTree[node]
        inorderTraversal(newNode1)
        print(node,end='')
        inorderTraversal(newNode2)

다음은 중위 순회입니다. 중위 순회는 왼쪽 서브트리 - 현재 노드 - 오른쪽 서브트리 순으로 순회하는 방식입니다.

다음과 같이 코드를 구성해 왼쪽 서브 트리 순회 후 현재 노드를 출력되게 한 후, 오른쪽 서브트리를 순회 하도록 코드를 구성하였습니다.

 

def postorderTraversal(node):
    if node != '.':
        for newNode in binaryTree[node]:
            postorderTraversal(newNode)
        print(node,end='')

마지막으로 후위 순회 입니다. 후위 순회는 왼쪽 서브트리 - 오른쪽 서브 트리 - 현재 노드 순으로 순회하는 방식입니다.

따라서 다음과 같이 왼쪽 - 오른쪽 서브 트리를 모두 순회한 후 현재노드를 출력하는 방식으로 코드를 구현하였습니다.