[Algorithm] 이진 트리의 넓이 우선 순회(BFS)_TIL Day3-5

이진 트리의 넓이 우선 순회

넓이 우선 순회(Breadth First Trabersal)

• 원칙
  - 수준(level)이 낮은 노드를 우선으로 방문
  - 같은 수준의 노드들 사이에는, 부모 노드의 방문 순서에 따라 방문, 왼쪽을 먼저 방문
• 한 노드를 방문했을 때, 나중에 방문할 노드(자식노드) 순서를 기록해 둬야 함 (큐를 이용해야 함)

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

• 알고리즘 순서
  1. traversal에 빈 리스트, q에 빈 큐를 초기화
  2. 빈 트리가 아니면, root node를 큐에 추가 (enqueue)
  3. q가 비어 있지 않는 동안
    3.1. q에서 원소를 추출 및 node에 저장 (dequeue)
    3.2. node를 방문처리 (traversal에 append)
    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):
        traverse = []
        q = ArrayQueue()
        
        if self.root: 
            q.enqueue(self.root)
        
        while q.size() > 0:
            el = q.dequeue()
            traverse.append(el.data)
            if el.left:
                q.enqueue(el.left)
            if el.right:
                q.enqueue(el.right)
            
        return traverse


def solution(x):
    return 0