[BOJ] Python 백준 1991번 트리 순회 실버 1

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

1991번: 트리 순회

 

문제 설명에서도 잘 나와 있듯이 이진 트리를 순서대로 순회하여 출력하는 문제다.

 

만약 이진 트리에 대한 구현이나 순회가 잘 이해되지 않는다면 이전 포스팅을 보고 이해하길 바란다.

 

https://khsung0.tistory.com/24

[자료구조] 트리(Tree) 이진 트리(Binary Tree) 트리 순회 (Tree Traversal) (Python)

 

문제 풀이

---

이진 트리와 순회에 대해 구현한 경험이 있다면 아주 쉽게 풀 수 있는 문제지만 경험이 없다면 아마 상당히 막막하게 느껴질 수 있는 문제라고 생각한다.

 

다행히 파이썬은 딕셔너리란 자료구조를 지원하므로 딕셔너리를 이용해서 아주 쉽게 구현해보겠다.

 

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

def inorder(trees,root):
    if trees[root][0]!=".":
        inorder(trees,trees[root][0])
    print(root,end="")
    if trees[root][1]!=".":
        inorder(trees,trees[root][1])

def postorder(trees,root):
    if trees[root][0]!=".":
        postorder(trees,trees[root][0])
    if trees[root][1]!=".":
        postorder(trees,trees[root][1])
    print(root,end="")

n=int(input())
trees={}
root="A"
for i in range(n):
    temp=input().split()
    trees[temp[0]]=[temp[1],temp[2]]

preorder(trees,root)
print()
inorder(trees,root)
print()
postorder(trees,root)

 

뭔가 코드는 많아 보이지만 하나씩 보면 별 거 없는 문제이다.

 

23번째 줄의 trees는 딕셔너리로 선언했고 문제에서 A가 루트라 했으므로 24번째 줄에서 루트를 A로 지정해준다.

 

그리고 25번째 줄에서 반복문을 돌면서 딕셔너리에 키와 값을 저장하는데 길이가 2인 리스트 형태의 값에서 0번째 인덱스는 왼쪽 자식 노드를 뜻하고 1번째 인덱스는 오른쪽 자식 노드를 뜻한다.

 

이때 자식 노드가 없다면 . 으로 쓴다는거만 주의하면 된다.

 

선언한 3개의 함수는 각 각 전위 순회, 중위 순회, 후위 순회하는 함수인데 이것도 상당히 간단하다.

 

현재 노드의 키를 출력하는 코드의 위치만 변경하면 되기 때문이다.

 

전위 순회를 기준으로 현재 노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드 순이기 때문에 현재 노드의 키 출력, 왼쪽 자식 노드가 있다면 왼쪽 자식 노드로 재귀 호출, 오른쪽 자식 노드가 있다면 오른쪽 자식 노드로 재귀 호출 했다.

 

순서만 바꾸면 되기 때문에 이진 트리만 구현할 수 있다면 상당히 쉬운 문제였다.

 

결과 화면