프로그래머스 강의_19

이진 트리(Binary Trees)

넓이 우선 순회(breadth first traversal)

(1) 원칙

• 수준(level)이 낮은 노드를 우선으로 방문
• 같은 수준의 노드들 사이에서는 부모 노드의 방문 순서에 따라 방문
• 왼쪽 자식 노드를 오른쪽 자식보다 먼저 방문한다.
  ==> 재귀적(recursive)방법이 적합한가?
• 한 노드를 방문했을 때 나중에 방문할 노드들을 순서대로 기록해두어야 한다.
  ==> 큐(queue)를 이용하면 어떨까?

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

• root노드를 queue에 먼저 넣고 시작
• 각 노드에 대한 자식노드가 있는지 확인하고 있다면 왼쪽부터 넣어준다.
• 큐가 비어있다면 종료

(3) 넓이 우선 순회 알고리즘 구현
① (초기화) traversal <- 빈 리스트, q <- 빈큐
② 빈 리스트가 아니면, root node를 큐에 추가 (enqueue)
③ q가 비어 있지 않은 동안
node <- q에서 원소를 추출(dequeue)
node를 방문
node의 왼쪽, 오른쪽 자식(있으면) 들을 q에 추가

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

===> while문 활용이 핵심!!

class Binary Tree:
   def bft(self):
       traversal = []
       q = ArrayQueue()
       
       if self.root == None:
           return traversal
       else :
           q.enqueue(self.root) 
           
       while not q.isEmpty() :
           x = q.dequeue()
           traversal.append(x.data)
           if x.left :
               q.enqueue(x.left)
           if x.right:
               q.enqueue(x.right)        
       return traversal