[백준 1991] 트리 순회

1. 문제

1991번: 트리 순회

 

⭐문제요약

1. 첫째줄 - 이진 트리 노드의 개수 N (1<=N<=26)
2. 둘째줄 - N개의 줄에 걸쳐 각 노드와 그의 왼쪽, 오른쪽 자식 노드가 주어짐. 자식노드 없으면 .으로 표현
3. 출력 - 첫째줄에 전위순회, 둘째줄에 중위 순회, 셋째줄에 후위 순회한 결과를 출력

 

2. 풀이

class Node:
    #생성자 함수에는 left, right속성이 None이다.
    def __init__(self,key):
        self.key = key
        self.left = None
        self.right = None

#이 함수에서 각 노드에 left, right속성을 부여한다.
def insert_node(nodes,key,left_key,right_key):
    if key != '.':
        #부모노드
        node = nodes[key]
        #왼쪽 자식노드
        if left_key !='.':
            node.left = nodes[left_key]
        #오른쪽 자식노드
        if right_key !='.':
            node.right = nodes[right_key]

n = int(input())

#아스키코드A부터 시작하는 n개의 노드 생성 및 딕셔너리에 저장
nodes = {chr(i+65) : Node(chr(i+65)) for i in range(n)}

for _ in range(n):
    key, left, right = input().split()
    insert_node(nodes,key,left,right)

#전위순회
def preorder(node):
    if not node: return
    print(node.key,end='')
    preorder(node.left)
    preorder(node.right)

#중위순회
def inorder(node):
    if not node: return
    inorder(node.left)
    print(node.key,end='')
    inorder(node.right)

#후위순회
def postorder(node):
    if not node: return
    postorder(node.left)
    postorder(node.right)
    print(node.key, end='')

preorder(nodes['A'])
print()
inorder(nodes['A'])
print()
postorder(nodes['A'])

 

*전위순회

 

1. A를 방문 (A) A 출력
2. A의 왼쪽 자식인 B를 방문 (A → B) B 출력
3. B의 왼쪽 자식인 D를 방문 (A → B → D) D 출력
4. D의 왼쪽 자식이 없으므로 (None), D의 오른쪽 자식도 없으므로 (None) 다시 B로 돌아감
5. B의 오른쪽 자식이 없으므로 (None), 다시 A로 돌아감
6. A의 오른쪽 자식인 C를 방문 (A → B → D → C) C 출력
7. C의 왼쪽 자식인 E를 방문 (A → B → D → C → E) E 출력
8. E의 왼쪽 자식이 없으므로 (None), E의 오른쪽 자식도 없으므로 (None) 다시 C로 돌아감
9. C의 오른쪽 자식인 F를 방문 (A → B → D → C → E → F) F 출력
10. F의 왼쪽 자식인 G를 방문 (A → B → D → C → E → F → G) G 출력
11. G의 왼쪽 자식이 없으므로 (None), G의 오른쪽 자식도 없으므로 (None) 다시 F로 돌아감
12. F의 오른쪽 자식이 없으므로 (None), 다시 C로 돌아감
13. C의 모든 자식 노드를 방문했으므로, 다시 A로 돌아감

*중위순회

 

*후위순회