(Python/이진트리)이진트리(2)

2) 넓이 우선 순회

원칙 

• - 수준이 낮은 노드를 우선으로 방문
• - 같은 수준의 노드들 사이에는 부모 노드 방문순서에 따라 방문 왼쪽이 오른쪽보다 우선
• dfs 와 유사

재귀적 비효율

 

한 노드를 방문할때 나중에 방문할 노드들은 순서대로 기록해둬야함  >>  큐(queue) 사용

 

스택에 a ,b, c 순서로 들어가고 내려갈 자식노드가 없으면 큐에스 팝해주고 하는식

 

구현 문제

 

import queue
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):
        traverse = []
        q = ArrayQueue()

        if self.root:
            q.enqueue(self.root)

        while q.size()!=0:
            information = q.dequeue()
            traverse.append(information.data)

            if information.left:
                q.enqueue(information.left)
            if information.right:
                q.enqueue(information.right)
        return traverse



def solution(x):
    return 0