যখন একটি বাইনারি ট্রির ইনঅর্ডার ট্রাভার্সাল ব্যবহার করে 'n'তম নোড বের করা প্রয়োজন হয়, তখন একটি বাইনারি ট্রি ক্লাস তৈরি করা হয় যাতে রুট উপাদান সেট করা, লেফট বা রাইটে উপাদান যোগ করা, ইনঅর্ডার ট্রাভার্সাল করা ইত্যাদি মেথড থাকে। ক্লাসের একটি ইনস্ট্যান্স তৈরি করা হয় এবং এটি মেথডগুলো অ্যাক্সেস করতে ব্যবহার করা হয়।
নিচে এর একটি উদাহরণ দেওয়া হলো:
উদাহরণ
class BinaryTree_struct:
def __init__(self, key=None):
self.key = key
self.left = None
self.right = None
def set_root(self, key):
self.key = key
def inorder_nth(self, n):
return self.inorder_nth_helper_fun(n, [])
def inorder_nth_helper_fun(self, n, in_ord):
if self.left is not None:
temp = self.left.inorder_nth_helper_fun(n, in_ord)
if temp is not None:
return temp
in_ord.append(self)
if n == len(in_ord):
return self
if self.right is not None:
temp = self.right.inorder_nth_helper_fun(n, in_ord)
if temp is not None:
return temp
def insert_t0_left(self, new_node):
self.left = new_node
def insert_to_right(self, new_node):
self.right = new_node
def search_elem(self, key):
if self.key == key:
return self
if self.left is not None:
temp = self.left.search_elem(key)
if temp is not None:
return temp
if self.right is not None:
temp = self.right.search_elem(key)
return temp
return None
btree_instance = None
print('Menu (this assumes no duplicate keys)')
print('insert at root')
print('insert left of ')
print('insert right of ')
print('inorder ')
print('quit')
while True:
do = input('What would you like to do? ').split()
operation = do[0].strip().lower()
if operation == 'insert':
data = int(do[1])
new_node = BinaryTree_struct(data)
suboperation = do[2].strip().lower()
if suboperation == 'at':
btree_instance = new_node
else:
position = do[4].strip().lower()
key = int(position)
ref_node = None
if btree_instance is not None:
ref_node = btree_instance.search_elem(key)
if ref_node is None:
print('No such key.')
continue
if suboperation == 'left':
ref_node.insert_t0_left(new_node)
elif suboperation == 'right':
ref_node.insert_to_right(new_node)
elif operation == 'inorder':
if btree_instance is not None:
index = int(do[1].strip().lower())
node = btree_instance.inorder_nth(index)
if node is not None:
print('nth term of inorder traversal: {}'.format(node.key))
else:
print('The index exceeds maximum possible index.')
else:
print('The tree is empty...')
elif operation == 'quit':
breakআউটপুট
Menu (this assumes no duplicate keys) insert at root insert left of insert right of inorder quit What would you like to do? insert 5 at root What would you like to do? insert 6 left of 5 What would you like to do? insert 8 right of 5 What would you like to do? inorder 5 The index exceeds maximum possible index. What would you like to do? 6 6
ব্যাখ্যা
প্রয়োজনীয় অ্যাট্রিবিউটসহ 'BinaryTree_struct' ক্লাস তৈরি করা হয়েছে।
এতে একটি 'init' ফাংশন আছে যা লেফট এবং রাইট নোডকে 'None' সেট করতে ব্যবহৃত হয়।
এতে একটি 'set_root' মেথড আছে যা বাইনারি ট্রির রুট সেট করতে সাহায্য করে।
'inorder_nth' নামে আরেকটি মেথড আছে যা রিকার্শন ব্যবহার করে ইনঅর্ডার ট্রাভার্সাল করে।
সেজন্য এর পাশাপাশি একটি হেল্পার ফাংশন নির্ধারণ করা হয়েছে।
'insert_to_right' নামে আরেকটি মেথড নির্ধারণ করা হয়েছে যা রুট নোডের ডানে উপাদান যোগ করতে সাহায্য করে।
'insert_to_left' নামে একটি মেথড নির্ধারণ করা হয়েছে, যা রুট নোডের বামে উপাদান যোগ করতে সাহায্য করে।
'search_elem' নামে একটি মেথড নির্ধারণ করা হয়েছে, যা নির্দিষ্ট উপাদান সার্চ করতে সাহায্য করে।
'BinaryTree_struct' ক্লাসের একটি অবজেক্ট তৈরি করা হয়েছে।
যে অপারেশনটি করতে হবে তার জন্য ইউজার ইনপুট নেওয়া হয়েছে।
ইউজারের পছন্দ অনুযায়ী অপারেশনটি সম্পাদন করা হয়েছে।
প্রাসঙ্গিক আউটপুট কনসোলে প্রদর্শিত হয়েছে।
