ভূমিকা
লিফ নোড (Leaf node) হলো যেসব নোডের কোনো চাইল্ড নেই। এই নিবন্ধে একটি হেল্পার ফাংশন ব্যবহার করে লিফ নোড গুনার পদ্ধতি দেখানো হয়েছে।
উদাহরণ কোড
class Tree_structure:
def __init__(self, data=None):
self.key = data
self.children = []
def set_root_node(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_leaf_node(self):
leaf_nodes = []
self.count_leaf_node_helper_fun(leaf_nodes)
return len(leaf_nodes)
def count_leaf_node_helper_fun(self, leaf_nodes):
if self.children == []:
leaf_nodes.append(self)
else:
for child in self.children:
child.count_leaf_node_helper_fun(leaf_nodes)
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)
sub_op = my_input[2].strip().lower()
if sub_op == 'at':
tree = newNode
elif sub_op == 'below':
my_pos = my_input[3].strip().lower()
key = int(my_pos)
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_leaf_node()
print('The number of 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 78 at root What operation would you like to perform ? add 90 below 78 What operation would you like to perform ? add 8 below 78 What operation would you like to perform ? count The number of leaf nodes are : 2 What operation would you like to perform ? quit
ব্যাখ্যা
count_leaf_nodeএকটি খালি লিস্ট তৈরি করে এবং হেল্পার ফাংশন কল করে।count_leaf_node_helper_funরিকার্সিভলি ট্রিভার্স করে। যদি নোডের চাইল্ড না থাকে, তবে সেটি লিফ নোড হিসেবে লিস্টে যোগ করা হয়।শেষে লিস্টের দৈর্ঘ্য (
len(leaf_nodes)) রিটার্ন করা হয়।উদাহরণে ট্রি: 78 (রুট) → 90 এবং 8 (দুই চাইল্ড)। লিফ নোড: 90, 8 = ২টি।
সরলীকৃত সংস্করণ
হেল্পার ফাংশন ছাড়া সরাসরি রিটার্ন করা যায়:
def count_leaf_node(self):
if not self.children:
return 1
return sum(child.count_leaf_node() for child in self.children)
