이진트리와 Bread First Traversal

BFT 즉 Bread First Traversal은 한국말로는 너비 우선 순회! 라고 한다. DFT(Depth First Traversal) 과는 다르게 너비, 즉 레벨단위로 순회한다.

어떻게 구현할 수 있을까?

각 노드와 그 자식들을 순서대로 출력하기 위해 큐(Queue)를 사용한다!

노드를 큐에 담고, 큐에 담겨있는 노드를 dequeue 하여 해당 노드의 데이터를 결과물을 담는 배열 result 에 추가하고 그의 자식들은 다시 enqueue 하는 시행을 반복한다. 큐에 모든 노드가 빠져나갔을 때 result에는 우리가 원하는 결과가 남는다.

이를 코드로 표현하면..

class BinaryTree:
	...
	def bft(self):
    	result = []
        
        if self.root:
        	q = Queue()
            	q.enqueue(self.root)
                
                while q.isEmpty() != True: # 큐가 비어있지 않다면..
                	curr = q.dequeue()
                    	if curr.left:
                        	q.enqueue(curr.left)
                        if curr.right:
                        	q.enqueue(curr.right)
                        result.append(curr.data)
                       
    	return result

이렇게 너비우선순회 BFT를 알아보았다!