[알고리즘 강의] 파트19. 이진 트리 - 넓이 우선 순회(breadth first traversal)

넓이 우선 순회 (breadth first traversal)

원칙

- 수준(level)이 낮은 노드를 우선으로 방문

- 같은 수준의 노드들 사이에는,

  ㄴ 부모 노드의 방문 순서에 따라 방문

  ㄴ왼쪽 자식 노드를 오른쪽 자식보다 먼저 방문

- 재귀적(recursive) 방법이 적합한가? X

 

 

한 노드를 방문했을 때,

나중에 방문할 노드들을 순서대로 기록해 두어야 함

-> 큐(queue)를 이용하자

 

넓이 우선 순회 알고리즘 설계

1. (초기화) traversal <- 빈 리스트, q <- 빈 큐

2. 빈 트리가 아니면, root node를 큐에 추가 (enqueue)

3. q가 비어 있지 않은 동안

  3.1 node <- q 에서 원소를 추출 (dequeue)

  3.2 node 를 방문

  3.3 node의 왼쪽, 오른쪽 자식 (있으면) 들을 q에 추가

4. q가 빈 큐가 되면 모든 노드 방문 완료

 

실습 과제 - 이진 트리의 넓이 우선 순회 구현

class ArrayQueue:

    def __init__(self):
        self.data = []

    def size(self):
        return len(self.data)

    def isEmpty(self):
        return self.size() == 0

    def enqueue(self, item):
        self.data.append(item)

    def dequeue(self):
        return self.data.pop(0)

    def peek(self):
        return self.data[0]


class Node:

    def __init__(self, item):
        self.data = item
        self.left = None
        self.right = None


class BinaryTree:

    def __init__(self, r):
        self.root = r


    def bft(self):
        traversal = []
        arr_queue = ArrayQueue()
        if self.root:
            arr_queue.enqueue(self.root)
            while arr_queue.isEmpty() != True:
                pop_t = arr_queue.dequeue()
                traversal.append(pop_t.data)
                if pop_t.left:
                    arr_queue.enqueue(pop_t.left)
                if pop_t.right:
                    arr_queue.enqueue(pop_t.right)
        return traversal
        


def solution(x):
    return 0

 

* 프로그래머스의 '어서와! 자료구조와 알고리즘은 처음이지?' 강의를 듣고 정리하였습니다.