이진트리의 순회 (Traversal) - 넓이 우선 순회 (BFT)

넓이 우선 순회 (Breadth First Traversal)

• 수준(level)이 낮은 노드를 우선으로 방문
• 같은 수준의 노드들 사이에서는 부모 노드의 방문 순서에 따라 방문, 왼쪽 자식 노드를 오른쪽 자식보다 먼저 방문
• 한 노드를 방문했을 때, 나중에 방문할 노드들을 순서대로 기록해 두어야 함

노드의 수준에 따라 순서를 정하여 노드들을 방문하는 순회 방식이다. 이 방식은 하나의 노드를 방문했을 때 나중에 그 노드의 자식 노드들을 방문하기로 해 두고 같은 수준에 있는 다른 노드들(직접 연결된 노드말고) 을 우선 방문해야하기 때문에 재귀적인 성질을 갖지 않는다.

나중에 다시 방문하기로 하고 그 순서를 기억해두자! 에 적합한 자료구조는 큐가 있다. 먼저 넣은 원소가 먼저 나오는 선입선출 성질을 가지고 있기 때문에 큐는 이러한 종류의 응용에 적합하다.

 

 

 

넓이 우선 순회 흐름 설계

수준이 낮은 노드부터 방문해서 큐에 enqueue

A를 dequeue(A를 방문함)

A의 자식노드 왼쪽->오른쪽으로 

B를 dequeue (B방문)

B의 자식노드 enqueue

C 를 dequeue (C 방문)

C의 자식노드 enqueue

D를 방문 (D enqueue)

D의 자식노드 enqueue

E를 방문 (dequeue) E의 자식노드 없음

F를 방문 (dequeue)

F의 자식노드 enqueue

G를 방문 (enequeue) G의 자식노드 없음

노드 H 방문 (enequeue) H의 자식노드 없음

노드 I방문 (dequeue) I의 자식노드 없음 큐가 비면 순회 끝 

 

 

 

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

1. traversal에는 빈 리스트를 초기화, q에는 빈 큐를 초기화한다.
2. 빈 트리가 아니면, root node를 큐에 추가(enqueue)한다.
3. q가 비어있지 않는 동안 q의 원소를 추출하여(dequeue) node에 저장한다
4. node를 방문 처리 (traversal에 append)한다.
5. node의 왼쪽, 오른쪽 자식 노드가 있으면 q에 추가한다.
6. q가 빈큐가 되면 모든 노드 방문 완료되었으므로 traversal을 리턴한다.

 

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 = []
        # 빈 큐 초기화
        visitQueue = ArrayQueue()

        # 빈 트리가 아니면 루트 노드가 있는 것 -> 큐에 루트 노드를 인큐
        if self.root:
            visitQueue.enqueue(self.root)

        # 큐가 비어있지 않는 동안 반복
        while visitQueue.isEmpty()==False:
            # 큐에서 꺼내서 node에 저장
            node = visitQueue.dequeue()
            # 꺼낸 노드를 방문 리스트에 저장
            traversal.append(node.data)

            # 노드에 왼쪽 자식 노드가 존재하는경우 큐에 저장
            if node.left:
                visitQueue.enqueue(node.left)
            # 노드에 오른쪽 자식 노드가 존재하는 경우 큐에 저장
            if node.right:
                visitQueue.enqueue(node.right)
            
        return traversal


def solution(x):
    return 0