자료구조와 알고리즘 19강

자료구조와 알고리즘 19강

Posted by 동식이 블로그 on September 30, 2019

넓이 우선 순회

  • 수준(level)이 낮은 노드를 우선으로 방문
  • 같은 수준의 노드들 사이에는
    • 부모 노드의 방문 순서에 따라 방문
    • 왼쪽 자식 노드를 오른쪽 자식보다 먼저 방문
  • 재귀적 방법이 적합하지 않다

bfs

  • 한 노드를 방문했을 때
    • 나중에 방문할 노드들을 순서대로 기록해 두어야 한다.
    • 를 이용한다


넓이 우선 순회 알고리즘 구현

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

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

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

    3-1. node <– q에서 원소를 추출(dequeue)

    3-2. node를 방문

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def bft(self):
        traversal = []
        q = ArrayQueue()

        if self.root:
            q.enqueue(self.root)

        while q.size() != 0:
            mov = q.dequeue()
            traversal.append(mov.data)
            if mov.left:
                q.enqueue(mov.left)
            if mov.right:
                q.enqueue(mov.right)

        return traversal


본 문서는 프로그래머스 어서와! 자료구조와 알고리즘 강의를 수강하고 정리했습니다.

출처 : 프로그래머스 : 어서와! 자료구조와 알고리즘은 처음이지?