트리(Tree) 자료구조에서 리프 노드가 아닌 노드, 즉 비-리프 노드(내부 노드)의 개수를 구해야 하는 경우가 있습니다. 이 글에서는 'Tree_structure' 클래스를 정의하고, 루트 값을 설정하는 메서드와 다른 값을 추가하는 메서드를 구현한 뒤, 사용자가 선택할 수 있는 여러 메뉴 옵션을 제공하여 선택에 따라 트리 요소에 대한 연산을 수행하는 방법을 소개합니다.
예제 코드
class Tree_structure:
def __init__(self, data=None):
self.key = data
self.children = []
def set_root(self, data):
self.key = data
def add_vals(self, node):
self.children.append(node)
def search_val(self, key):
if self.key == key:
return self
for child in self.children:
temp = child.search_val(key)
if temp is not None:
return temp
return None
def count_non_leaf_node(self):
nonleaf_count = 0
if self.children != []:
nonleaf_count = 1
for child in self.children:
nonleaf_count = nonleaf_count + child.count_non_leaf_node()
return nonleaf_count
tree = None
print('Menu (this assumes no duplicate keys)')
print('add <data> at root')
print('add <data> below <data>')
print('count')
print('quit')
while True:
my_input = input('What operation would you like to perform ? ').split()
operation = my_input[0].strip().lower()
if operation == 'add':
data = int(my_input[1])
newNode = Tree_structure(data)
suboperation = my_input[2].strip().lower()
if suboperation == 'at':
tree = newNode
elif suboperation == 'below':
position = my_input[3].strip().lower()
key = int(position)
ref_node = None
if tree is not None:
ref_node = tree.search_val(key)
if ref_node is None:
print('No such key.')
continue
ref_node.add_vals(newNode)
elif operation == 'count':
if tree is None:
print('The tree is empty ')
else:
count = tree.count_non_leaf_node()
print('The number of non-leaf nodes are : {}'.format(count))
elif operation == 'quit':
break실행 결과
Menu (this assumes no duplicate keys) add <data> at root add <data> below <data> count quit What operation would you like to perform ? add 34 at root What operation would you like to perform ? add 78 below 34 What operation would you like to perform ? add 56 below 78 What operation would you like to perform ? add 90 below 56 What operation would you like to perform ? count The number of non-leaf nodes are : 3 What operation would you like to perform ? quit
코드 설명
'Tree_structure' 클래스를 생성합니다.
생성자에서는 노드의 'key' 값과 자식 노드들을 저장할 빈 리스트 'children'을 초기화합니다.
'set_root' 함수는 트리의 루트(root) 값을 설정하는 역할을 합니다.
'add_vals' 메서드는 트리에 새로운 노드(요소)를 추가할 때 사용됩니다.
'search_val' 메서드는 트리 안에서 특정 키 값을 가진 노드를 재귀적으로 탐색합니다.
'count_non_leaf_node' 메서드는 트리에서 비-리프 노드의 개수를 계산합니다.
이 메서드는 재귀(recursion) 방식으로 동작하며, 자식 노드가 하나라도 있으면 자신을 비-리프 노드로 간주하고 1을 더한 뒤, 모든 자식 노드에 대해 재귀적으로 호출하여 합산합니다.
사용자에게는 '루트에 추가(add at root)', '아래에 추가(add below)', '개수 세기(count)', '종료(quit)' 네 가지 옵션이 제공됩니다.
사용자가 입력한 옵션에 따라 해당 연산이 수행되며, 그 결과가 콘솔에 출력됩니다.
위 예제 실행 결과에서 34 → 78 → 56 → 90 순서로 노드를 추가했을 때, 34, 78, 56은 자식 노드를 가지므로 비-리프 노드가 되고, 마지막 노드인 90만 리프 노드입니다. 따라서 비-리프 노드의 개수는 3개로 출력됩니다.