19강 요약

전,중,후위 탐색과 다르게 트리의 level별로, 또 같은 level에선 좌측노드부터 우측노드로 탐색 한다.

19강 내용

큐를 이용하여 트리의 노드를 level별 순으로 방문 한다.

bft()

순서에 맞게 정의 하면
1. 큐와 출력순서를 저장할 리스트 선언
2. 빈 트리일 경우 빈 리스트 출력
3. 빈 트리가 아닐 경우 루트를 큐에 enqueue
4. 큐가 빌 때 까지 dequeue해 노드를 순서대로 뽑음
5. 노드의 좌 자식, 우 자식 을 큐에 저장
6. 현재노드를 출력 리스트에 추가

문제

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()
                if node.left: # 좌
                    q.enqueue(node.left)
                if node.right: # 우
                    q.enqueue(node.right)
                traversal.append(node.data) #본인 출력
            return traversal
        else:
            return []


def solution(x):
    return 0

GitHub

https://github.com/ds02168/Study_Algorithm/blob/master/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/%EC%96%B4%EC%84%9C%EC%99%80%20%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%99%80%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%80%20%EC%B2%98%EC%9D%8C%EC%9D%B4%EC%A7%80/19%EA%B0%95/19%EA%B0%95.py