트리순회

트리순회

트리를 순회할 때 어떤 노드를 먼저 탐색하느냐에 따라 전위,중위,후위로 나눌 수 있다.

각각의 순회를 알아 본다.

 

전위순회

부모 -> 왼쪽자식 -> 오른쪽자식

더이상 부모노드가 없을때 그 다음 노드(왼쪽자식)을 탐색한다

 

중위순회

왼쪽자식 -> 부모 -> 오른쪽자식

더이상 왼쪽자식이 없을때 그다음 노드(부모)를 탐색한다

 

후위순회

왼쪽자식 -> 오른쪽자식 -> 부모

그다음 왼쪽자식이 없을때 그다음 노드(오른쪽자식)을 탐색한다

*출처 : https://hongku.tistory.com/160

 

예시코드 (백준 1991 트리순회)

def preorder(N):
    global graph
    if N in graph:
        print(N, end="")
        preorder(graph[N][0])
        preorder(graph[N][1])


def inorder(N):
    global graph
    if N in graph:
        inorder(graph[N][0])
        print(N, end="")
        inorder(graph[N][1])


def postorder(N):
    global graph
    if N in graph:
        postorder(graph[N][0])
        postorder(graph[N][1])
        print(N, end="")


N = int(input())

graph = {}

for _ in range(N):
    p, c1, c2 = input().split()

    graph[p] = [c1, c2]

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