이진 트리 순회

이진 트리(Binary Tree)를 탐색하는 방법에는 크게 다음의 4가지가 있다.

• 전위순회(Preorder Traversal)
• 중위순회(Inorder Traversal)
• 후위순회(Postorder Traversal)
• 레벨순회(Levelorder Traversal) 또는 BFS(Breadth-First Search; 너비 우선 탐색)

레벨순회(;BFS)를 제외한 나머지 순회방식은 DFS(Depth-First Search; 깊이 우선 탐색)으로 분류할 수 있다.

 

 

1. 전위순회(preorder traversal)

전위순회는 루트 노드를 먼저 탐색하고, 자식 노드를 탐색하는 방식이다.

# 전위순회
def preorder(root):
    if root != '.':
        print(root, end='')       # root
        preorder(tree[root][0])   # left
        preorder(tree[root][1])   # right

 

 

2. 중위순회(inorder traversal)

중위순회는 왼쪽 자식 노드를 탐색하고, 루트 노드를 탐색하고, 오른쪽 자식 노드를 탐색하는 방식이다.

# 중위순회 
def inorder(root):
    if root != '.':
        inorder(tree[root][0])    # left
        print(root, end='')       # root
        inorder(tree[root][1])    # right

 

 

3. 후위순회(postorder traversal)

후위순회는 왼쪽 자식 노드를 탐색하고, 오른쪽 자식 노드를 탐색하고, 루트 노드를 탐색하는 방식이다.

 # 후위순회
def postorder(root):
    if root != '.':
        postorder(tree[root][0])  # left
        postorder(tree[root][1])  # right
        print(root, end='')       # root

 

 

4. 레벨순회(levelorder traversal; BFS)

레벨순회는 루트 노드를 먼저 탐색하고, 그 다음 레벨의 노드를 탐색하는 방식이다. queue를 하나 선언해두고, 루트 노드를 넣어준 다음, queue에 넣어준 노드를 하나씩 탐색하면서 자식 노드를 queue에 넣는다. queue가 비어있을 때까지 반복한다.

# BFS 메서드 정의
def bfs (graph, node, visited):
    # 큐 구현을 위한 deque 라이브러리 활용
    queue = deque([node])
    # 현재 노드를 방문 처리
    visited[node] = True
    
    # 큐가 완전히 빌 때까지 반복
    while queue:
        # 큐에 삽입된 순서대로 노드 하나 꺼내기
        v = queue.popleft()
        # 탐색 순서 출력
        print(v, end = ' ')
        # 현재 처리 중인 노드에서 방문하지 않은 인접 노드를 모두 큐에 삽입
        for i in graph[v]:
            if not (visited[i]):
                queue.append(i)
                visited[i] = True

레벨순회의 작동 방식

다른 순회 방식은 재귀로 쉽게 구현이 가능하지만, 레벨 순회(;BFS)는 재귀가 아닌 다른 방식으로 구현해야 한다. 일반적으로 Queue를 사용하는데, 예시를 보며 작동 방식을 익혀보자.

A를 루트로 하는 트리가 있으면, A를 queue에 집어 넣는다.

queue의 가장 앞에 있는 A를 탐색하고, A의 자식 노드 B, C를 queue에 집어 넣는다.

queue의 가장 앞에 있는 B를 탐색하고, B의 자식 노드 D, E를 queue에 집어 넣는다.

queue의 가장 앞에 있는 C를 탐색하고, C는 자식 노드가 없으므로 다음으로 넘어간다.

queue의 가장 앞에 있는 D를 탐색하고, D는 자식 노드가 없으므로 다음으로 넘어간다.

queue의 가장 앞에 있는 E를 탐색하고, E의 자식 노드 F, G를 queue에 집어 넣는다.

queue의 가장 앞에 있는 F를 탐색하고, F는 자식 노드가 없으므로 다음으로 넘어간다.

queue의 가장 앞에 있는 G를 탐색하고, G는 자식 노드가 없으므로 다음으로 넘어간다.

queue가 비었으므로 탐색을 종료한다.

이렇게 탐색을 완료하면 A, B, C, D, E, F, G 순으로 방문하게 된다.

 

출처: https://www.jiwon.me/binary-tree-traversal/