트리 / 넓이 우선 탐색

 

넓이 우선 탐색의 원칙

• 수준 (level) 이 낮은 노드를 우선으로 방문한다.
• 같은 수준의 노드 사이에서는
  1. 부모 노드의 방문 순서에 따라 방문
  2. 왼쪽 자식 노드를 오른쪽 자식보다 먼저 방문

 

 

한 노드를 방문했을 때, 나중에 방문할 노드들을 순서대로 기록해두어야한다. → 큐(queue)를 이용해보자.

넓이 우선 순회 알고리즘 설계

1. A를 큐에 넣고 dequeue()
2. A의 자식 노드를 왼쪽에서 부터 enqueue() | B , C |
3. B를 dequeue()
4. B의 자식 노드를 왼쪽 부터 enqueue() | C , D , E |
5. C를 dequeue() | D , E |
6. C의 자식 노드를 왼쪽 부터 enqueue() | D , E , F , G |
7. … 반복 , 큐에 남은 노드가 없으면 종료

• 결과

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

1. (빈 리스트 초기화) traversal , (빈 큐 초기화) q
2. 빈 트리가 아니라면 , rood node를 q에 enqueue()
3. q가 비어 있지 않은 동안
   • 3-1) q에서 node를 dequeue()
   • 3-2) node를 방문
   • 3-3) node의 왼쪽 , 오른쪽을 방문 시 존재하면 q에 enqueue
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):
        traversal = []
        q = ArrayQueue()
        
        if(self.root):
            q.enqueue(self.root)
            
        while(q.size() != 0 ):
            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