넓이 우선 순회 (Breadth First Traversal)

• 원칙
  • 수준(Level)이 낮은 노드를 우선으로 방문
  • 같은 수준의 노드들 사이에서는 부모 노드의 방문 순서에 따라 방문,
    왼쪽 자식 노드를 오른쪽 자식보다 먼저 방문
  • 한 노드를 방문했을 때, 나중에 방문할 노드들을 순서대로 기록해 두어야함
• 하나의 노드를 방문했을 때 나중에 그 노드의 자식 노드들을 방문하기로 해 두고 같은 수준에 있는 다른 노드들(직접 연결된 노드말고) 을 우선 방문해야하기 때문에 재귀적인 성질을 갖지 않는다.
• 선입선출 성질을 가지고 있기 때문에 자료구조는 큐를 사용

넓이 우선 순회 흐름 설계

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

• A를 방문함(A를 dequeue)

• A의 자식노드 왼쪽 → 오른쪽 으로

• B를 방문(B를 dequeue)

• B의 자식노드(E)를 enqueue

• C를 방문(C를 dequeue)

• C의 자식노드(G)를 enqueue

• D를 방문(D를 dequeue)

• D의 자식노드(H)를 enqueue

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

• F를 방문(F를 dequeue)

• F의 자식노드(I)를 enqueue

• G를 방문(G를 dequeue), G의 자식노드 없음

• H를 방문(H를 dequeue), H의 자식노드 없음

• I를 dequeue(I를 방문), 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

[실습] 이진 트리의 넓이 우선 순회 구현

문제

어서와! 자료구조와 알고리즘은 처음이지?19강 실습: 이진 트리의 넓이 우선 순회

문제 설명

이진 트리를 구현한 클래스인 class BinaryTree 에 대하여 넓이 우선 순회 (breadth first traversal) 를 구현하는 메서드 bft() 를 완성하세요.

class ArrayQueue 는 배열 (python list) 을 이용하여 구현한 큐 (queue) 의 추상적 자료구조입니다. 이것을 이용하여 넓이 우선 순회 알고리즘을 구현하세요.

[참고 1] solution() 함수의 구현은 그대로 두세요. 이것을 없애면 테스트가 되지 않습니다.

[참고 2] 코드 실행 을 눌렀을 때 통과하는 것은 아무런 의미가 없습니다.

---

나의 풀이

solution.py

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):
        q = ArrayQueue()
        traversal = []
        if self.root:
            q.enqueue(self.root)
        while not q.isEmpty():
            node = q.dequeue()
            traversal.append(node.data)
            if node.left:
                q.enqueue(node.left)
            if node.right:
                q.enqueue(node.right)
        
        return traversal

def solution(x):
    return 0