ভূমিকা
এক ট্রি ডেটা স্ট্রাকচারে নন-লিফ নোড (non-leaf node) হলো যেসব নোডের কমপক্ষে একটি চাইল্ড থাকে। এই নিবন্ধে রিকার্শন ব্যবহার করে নন-লিফ নোডের সংখ্যা গুনার প্রোগ্রাম দেখানো হয়েছে।
উদাহরণ কোড
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 += child.count_non_leaf_node()
return nonleaf_count
tree = None
print('Menu (this assumes no duplicate keys)')
print('add at root')
print('add below ')
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 at root add below 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 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
ব্যাখ্যা
count_non_leaf_nodeমেথড: যদি নোডের চাইল্ড থাকে (self.children != []), তবে এটি নন-লিফ (কাউন্ট ১), তারপর সব চাইল্ডের জন্য রিকার্সিভলি কল করে যোগ করে।উদাহরণে ট্রি: 34 (রুট) → 78 → 56 → 90। নন-লিফ নোড: 34, 78, 56 = ৩টি। 90 লিফ নোড।
মেনু সিস্টেম পূর্বের নিবন্ধের মতো।
