트리의 노드를 너비 우선 탐색(BFS, Breadth First Search) 방식으로 출력해야 하는 경우에는 먼저 클래스를 정의하고, 그 안에 루트 노드 설정, 트리에 요소 추가, 특정 요소 검색, 'bfs' 순회 수행 등의 메서드를 구현하면 됩니다. 이렇게 만든 클래스의 인스턴스를 생성하면 해당 메서드들을 자유롭게 호출하여 사용할 수 있습니다.
아래는 이를 구현한 예제입니다.
예제
class Tree_struct:
def __init__(self, data=None):
self.key = data
self.children = []
def set_root(self, data):
self.key = data
def add_node(self, node):
self.children.append(node)
def search_node(self, key):
if self.key == key:
return self
for child in self.children:
temp = child.search_node(key)
if temp is not None:
return temp
return None
def bfs_operation(self):
queue = [self]
while queue != []:
popped = queue.pop(0)
for child in popped.children:
queue.append(child)
print(popped.key, end=' ')
my_instance = None
print('Menu (assume no duplicate keys)')
print('add <data> at root')
print('add <data> below <data>')
print('bfs')
print('quit')
while True:
my_input = input('What operation would you do ? ').split()
operation = my_input[0].strip().lower()
if operation == 'add':
data = int(my_input[1])
new_node = Tree_struct(data)
suboperation = my_input[2].strip().lower()
if suboperation == 'at':
my_instance = new_node
elif suboperation == 'below':
position = my_input[3].strip().lower()
key = int(position)
ref_node = None
if my_instance is not None:
ref_node = my_instance.search_node(key)
if ref_node is None:
print('No such key')
continue
ref_node.add_node(new_node)
elif operation == 'bfs':
if my_instance is None:
print('The tree is empty')
else:
print('Breadth First Search traversal is : ', end='')
my_instance.bfs_operation()
print()
elif operation == 'quit':
break출력 결과
Menu (assume no duplicate keys) add <data> at root add <data> below <data> bfs quit What operation would you do ? add 6 at root What operation would you do ? add 4 below 6 What operation would you do ? add 9 below 4 What operation would you do ? bfs Breadth First Search traversal is : 6 4 9 What operation would you do ? quit
설명
필요한 속성을 갖춘 'Tree_struct' 클래스가 정의됩니다.
'__init__' 함수는 객체 생성 시 데이터와 빈 children 리스트를 초기화하는 데 사용됩니다.
'set_root' 메서드는 트리의 루트 값을 설정하는 역할을 합니다.
'add_node' 메서드는 트리에 새로운 노드를 추가할 때 사용됩니다.
'search_node' 메서드는 재귀적으로 하위 노드를 탐색하며 특정 키를 가진 노드를 찾습니다.
'bfs_operation' 메서드는 큐를 활용해 트리 전체를 너비 우선 순서로 순회합니다.
인스턴스 변수는 처음에 'None'으로 초기화됩니다.
사용자로부터 수행할 작업을 입력받습니다.
사용자의 선택에 따라 노드 추가, BFS 순회 등 해당 작업이 수행됩니다.
실행 결과가 콘솔에 출력됩니다.
BFS(너비 우선 탐색)란?
너비 우선 탐색은 트리나 그래프를 순회하는 대표적인 알고리즘으로, 루트 노드에서 시작해 같은 깊이에 있는 노드들을 모두 방문한 후 다음 깊이로 내려가는 방식입니다. 일반적으로 큐(Queue) 자료구조를 활용해 구현되며, 위 코드의 'bfs_operation' 메서드에서도 리스트를 큐처럼 사용해 앞에서부터 노드를 꺼내고(pop), 그 자식 노드들을 뒤에 추가하는(append) 방식으로 동작합니다.
덕분에 위 예제에서 루트 6 아래에 4를 추가하고, 다시 4 아래에 9를 추가한 뒤 BFS를 실행하면 6 → 4 → 9 순서로 노드가 출력되는 것을 확인할 수 있습니다.