깊이 우선 탐색(Depth First Search, DFS)을 후위 순회(Post-order Traversal) 방식으로 구현하려면, 트리 클래스를 정의하고 그 안에 노드 추가, 특정 키 검색, 후위 순회 수행 등의 메서드를 작성해야 합니다. 이후 클래스의 인스턴스를 생성하면 각 메서드에 접근하여 원하는 연산을 수행할 수 있습니다.
아래에서 실제 구현 예시를 확인해 보겠습니다.
예제 코드
class Tree_Struct:
def __init__(self, key=None):
self.key = key
self.children = []
def add_elem(self, node):
self.children.append(node)
def search_elem(self, key):
if self.key == key:
return self
for child in self.children:
temp = child.search_elem(key)
if temp is not None:
return temp
return None
def postorder_traversal(self):
for child in self.children:
child.postorder_traversal()
print(self.key, end=' ')
my_instance = None
print('Menu (this assumes no duplicate keys)')
print('add <data> at root')
print('add <data> below <data>')
print('dfs')
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
else:
position = my_input[3].strip().lower()
key = int(position)
ref_node = None
if my_instance is not None:
ref_node = my_instance.search_elem(key)
if ref_node is None:
print('No such key exists')
continue
ref_node.add_elem(new_node)
elif operation == 'dfs':
print('The post-order traversal is : ', end='')
my_instance.postorder_traversal()
print()
elif operation == 'quit':
break실행 결과
Menu (this assumes no duplicate keys) add <data> at root add <data> below <data> dfs quit What operation would you do ? add 5 at root What operation would you do ? insert 9 below 5 What operation would you do ? insert 2 below 9 What operation would you do ? dfs The post-order traversal is : 5 What operation would you do ? quit
코드 설명
필요한 속성들을 가진 Tree_Struct 클래스가 생성됩니다.
클래스 내부에는 빈 리스트를 초기화하는 __init__ 생성자가 정의되어 있으며, 이 리스트는 자식 노드들을 저장하는 데 사용됩니다.
add_elem 메서드는 트리에 새로운 노드(요소)를 추가하는 역할을 합니다.
search_elem 메서드는 재귀적으로 자식 노드들을 탐색하여 특정 키에 해당하는 노드를 찾아 반환합니다.
postorder_traversal 메서드는 후위 순회를 수행합니다. 즉, 모든 자식 노드를 먼저 순회한 뒤 마지막에 현재 노드의 키 값을 출력합니다.
트리 인스턴스는 처음에 None으로 초기화되며, 루트 노드가 추가될 때 할당됩니다.
사용자로부터 수행할 연산을 입력받습니다.
입력된 명령어에 따라 노드 추가, DFS 순회, 프로그램 종료 등의 동작이 분기 처리됩니다.
연산 결과는 콘솔 화면에 출력됩니다.
후위 순회란?
후위 순회(Post-order Traversal)는 트리 순회 방식 중 하나로, 자식 노드를 모두 방문한 후 현재(부모) 노드를 방문하는 방법입니다. 일반적으로 '왼쪽 자식 → 오른쪽 자식 → 부모' 순서로 진행되며, 트리의 삭제 작업이나 하위 노드부터 결과를 계산해야 하는 상황에서 유용하게 활용됩니다.