Tree에서 non-leaf 노드의 개수를 구해야 하는 경우 'Tree_structure' 클래스를 생성하고 루트 값을 설정하고 다른 값을 추가하는 메소드를 정의합니다. 사용자가 선택할 수 있는 다양한 옵션이 제공됩니다. 사용자의 선택에 따라 Tree 요소에 대해 작업을 수행합니다.
아래는 동일한 데모입니다 -
예시
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'를 True로 설정하고 빈 목록을 트리의 자식으로 설정합니다.
-
트리의 루트 값을 설정하는 데 도움이 되는 'set_root' 기능이 있습니다.
-
트리에 요소를 추가하는 데 도움이 되는 'add_vals'라는 메서드가 정의되어 있습니다.
-
트리에서 요소를 검색하는 데 도움이 되는 'search_val'이라는 또 다른 메서드가 정의되어 있습니다.
-
'count_non_leaf_nodes'라는 또 다른 메소드가 정의되어 트리의 리프가 아닌 노드의 수를 얻는 데 도움이 됩니다.
-
재귀 함수입니다.
-
'루트에 추가', '아래에 추가', '카운트' 및 '종료'와 같은 4가지 옵션이 제공됩니다.
-
사용자가 부여한 옵션에 따라 각각의 작업을 수행합니다.
-
이 출력은 콘솔에 표시됩니다.