[백준] 1991번, 트리 순회 | (python,파이썬)

문제 링크

 

1991번: 트리 순회

---

문제

---

문제해결하기

○ 트리의 순회 ?

 

트리의 순회는 세가지 방법으로 preorder, inorder, postorder가 있다.  (M의 위치 기준으로 이름을 지었다.)

▷Preorder: M L R (Middle 노드 출력 → Left subtree 순회 → Right subtree 순회)
▷Inorder: L M R (Left subtree 순회 → Middle 노드 출력 → Right subtree 순회)
▷Postorder: L R M (Left subtree 순회 → Right subtree 순회 → Middle 노드 출력)

 

○ 그림으로 알아보기

○ 코드는 아주 단순하다. 순회 방식에 따라 재귀호출, 출력의 위치만 설정해주면 된다. 

---

정답코드

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

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

n = int(input()) 
tree = {} # tree 생성 
for _ in range(n): 
    root, left, right = input().split() 
    tree[root] = (left, right)

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

▷ 딕셔너리에 대해 익숙하지않아서 문자열 주어진 노드에 대한 정보를 줬을때 항상 헤매는데..

문자열에 대한 정보를 저장할땐 항상 딕셔너리부터 생각해야겠다!

---

[출처]

신찬수 교수 (한국외국어대학교 컴퓨터 공학부), 'Data Structures with Python', p.95~97

Youtube : ‘Chan-Su Shin’

 

Chan-Su Shin