[프로그래머스 알고리즘] 19강: 이진 트리의 넓이 우선 순회 (BFS; Breadth First Traversal)

넓이 우선 순회의 원칙 

• 수준이 낮은 노드를 우선으로 방문
• 같은 수준의 노드들 사이에서는, 부모노드의 방문 순서에따라 방문, 왼쪽 자식 노드 우선
  • 따라서 재귀적 방법이 적합하지 않음!

한 노드를 방문했을때, 나중에 방문할 노드들을 순서대로 기록해 두어야 함 --> queue를 이용

 

구현 방법

1. (초기화) traversal <- empty list, q <- empty queue
2. 빈 트리가 아니면, 루트 노드를 q에 추가
3. q가 비어있지 않은 동안
   • node <- q에서 원소 추출
   • node 방문
   • node의 왼쪽, 오른쪽 자식 있으면 q에 추가
4. q가 빈 큐가 되면 모든 노드 방문 완료

---

19강 실습: 이진 트리의 넓이 우선 순회

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 = []
        queue = ArrayQueue()
        if self.root:
            queue.enqueue(self.root)
            while not queue.isEmpty():
                parent = queue.dequeue()
                traversal.append(parent.data)
                if parent.left:
                    queue.enqueue(parent.left)
                if parent.right:
                    queue.enqueue(parent.right)
        return traversal