traversal에는 빈 리스트를 초기화, q에는 빈 큐를 초기화한다.
빈 트리가 아니면, root node를 큐에 추가(enqueue)한다
q가 비어있지 않는 동안 q의 원소를 추출하여(dequeue) node에 저장한다
node를 방문 처리(traversal에 append)한다
node의 왼쪽, 오른쪽 자식 노드가 있으면 q에 추가한다
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] 코드 실행 을 눌렀을 때 통과하는 것은 아무런 의미가 없습니다.
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