[python] Tree 순회하기

1. python으로 트리를 구현할 때 dictionary를 사용하여 루트노드와 left, right를 저장한다.

2. 전위/ 중위/ 후위 순회는 재귀함수로 코드의 순서를 바꿔 구현한다.

 

 

다음과 같은 이진트리가 존재할 때 각각 전위/중위/후위 순회를 해본다면 다음과 같다.

 

1. 전위순회 : [루트 - 왼쪽 자식 - 오른쪽 자식] 순으로 순회

     A - B - D - G - C - E - F

 

2. 중위순회 : [왼쪽 자식 - 루트 - 오른쪽 자식] 순으로 순회

     G - D - B - A - E - C - F

 

3. 후위순회 : [왼쪽 자식 - 오른쪽 자식 - 루트] 순으로 순회

     G - D - B - E - F - C - A

 

 

python으로 트리 순회 구현

1991번: 트리 순회 (acmicpc.net)

1991번: 트리 순회

import sys

input = sys.stdin.readline
n = int(input())
tree={}

for i in range(n):
    root, left, right = map(str, input().split())
    tree[root] = [left, right]


def preorder(root):
    if root != '.':
        print(root, end='')
        preorder(tree[root][0])
        preorder(tree[root][1])

def inorder(root):
    if root != '.':
        inorder(tree[root][0])
        print(root, end='')
        inorder(tree[root][1])
        
def postorder(root):
    if root != '.':
        postorder(tree[root][0])
        postorder(tree[root][1])
        print(root, end='')

preorder('A')
print()
inorder('A')
print()
postorder('A')