[프로그래머스 강의] 19강 이진 트리(Binary Tree) - BFS

 

---

'어서와! 자료구조와 알고리즘은 처음이지?'

---

이진트리의 넓이 우선 순회(BFS; Breadth First Traversal)

원칙

✔ 수준(level)이 낮은 노드를 우선으로 방문

✔ 같은 수준의 노드들 사이에서는 부모 노드의 방문 순서에 따라 방문

✔ 왼쪽 자식 노드를 오른 쪽 자식 노드보다 먼저 방문

✔ 한 노드를 방문했을 때, 나중에 방문할 노드들을 순서대로 기록(방문한 노드의 자식 노드 기록)

✔ 큐(Queue) 이용

 

 

→ 순회 결과:  A - B - C - D - E - F - G - H - J

 

알고리즘 설계

1. traversal 빈 리스트 초기화

2. 빈 트리가 아니면(root != None) root node를 큐에 추가(enqueue)

3. q 가 비어있지 않는 동안,

    3.1 node  ← q 에서 원소를 추출(dequeue)

    3.2 node를 방문

    3.3 node의 왼쪽, 오른쪽 자식 노드가 존재하는 경우 q에 추가(왼쪽 자식 노드 부터 추가)

 

[ 문1. 이진트리의 넓이 우선 순회 ]

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 = []
        # 큐 초기화
        q = ArrayQueue()
        
        # 루트 노드가 존재하는 경우 
        if self.root:
            q.enqueue(self.root)
            # q가 비어있지 않는동안 반복해서 순회
            while q.size():
                element = q.dequeue()
                traversal.append(element.data)
                if element.left:
                    q.enqueue(element.left)
                if element.right:
                    q.enqueue(element.right)

        return traversal

def solution(x):
    return 0