পাইথন প্রোগ্রাম: ইনঅর্ডার বা পোস্টঅর্ডার ট্রাভার্সাল ইনপুট হিসেবে দিয়ে বাইনারি ট্রি নির্মাণ করা

যখন ইনঅর্ডার বা পোস্টঅর্ডার ট্রাভার্সাল ইনপুট হিসেবে নিয়ে বাইনারি ট্রি নির্মাণ করা প্রয়োজন হয়, তখন একটি ক্লাস নির্ধারণ করা হয় যাতে রুট উপাদান সেট করা, ইনঅর্ডার ট্রাভার্সাল করা, পোস্টঅর্ডার ট্রাভার্সাল করা ইত্যাদি মেথড থাকে। ক্লাসের একটি ইনস্ট্যান্স তৈরি করে এটি ব্যবহার করা যায়।

নিচে এর একটি উদাহরণ দেওয়া হলো:

উদাহরণ

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_traversal(self):
        if self.left is not None:
            self.left.inorder_traversal()
        print(self.key, end=' ')
        if self.right is not None:
            self.right.inorder_traversal()
    def post_order_traversal(self):
        if self.left is not None:
            self.left.post_order_traversal()
        if self.right is not None:
            self.right.post_order_traversal()
        print(self.key, end=' ')

def construct_btree(post_ord, in_ord):
    if post_ord == [] or in_ord == []:
        return None
    key = post_ord[-1]
    node = BinaryTree_struct(key)
    index = in_ord.index(key)
    node.left = construct_btree(post_ord[:index], in_ord[:index])
    node.right = construct_btree(post_ord[index:-1], in_ord[index + 1:])
    return node

post_ord = input('The input for post-order traversal is : ').split()
post_ord = [int(x) for x in post_ord]
in_ord = input('The input for in-order traversal is : ').split()
in_ord = [int(x) for x in in_ord]
my_instance = construct_btree(post_ord, in_ord)
print('Binary tree has been constructed...')
print('Verification in process..')
print('Post-order traversal is... ', end='')
my_instance.post_order_traversal()
print()
print('In-order traversal is... ', end='')
my_instance.inorder_traversal()
print()

আউটপুট

The input for post-order traversal is : 1 2 3 4 5
The input for in-order traversal is : 5 4 3 2 1
Binary tree has been constructed...
Verification in process..
Post-order traversal is... 1 2 3 4 5
In-order traversal is... 5 4 3 2 1

ব্যাখ্যা

• প্রয়োজনীয় অ্যাট্রিবিউটসহ 'BinaryTree_struct' ক্লাস তৈরি করা হয়েছে।

• এতে একটি 'init' ফাংশন আছে যা লেফট এবং রাইট নোডকে 'None' সেট করতে ব্যবহৃত হয়।

• এতে একটি 'set_root' মেথড আছে যা বাইনারি ট্রির রুট সেট করতে সাহায্য করে।

• 'inorder_traversal' নামে আরেকটি মেথড আছে যা ইন-অর্ডার ট্রাভার্সাল সম্পাদন করে, অর্থাৎ Left→Node→Right।

• 'post_order_traversal' নামে আরেকটি মেথড নির্ধারণ করা হয়েছে যা পোস্ট-অর্ডার ট্রাভার্সাল করে, অর্থাৎ Left→Right→Node।

• 'construct_btree' নামে একটি মেথড নির্ধারণ করা হয়েছে, যা পূর্বে নির্দিষ্ট উপাদানগুলো ব্যবহার করে বাইনারি ট্রি নির্মাণ করতে সাহায্য করে।

• 'search_elem' নামে একটি মেথড নির্ধারণ করা হয়েছে, যা নির্দিষ্ট উপাদান সার্চ করতে সাহায্য করে।

• 'BinaryTree_struct' ক্লাসের একটি অবজেক্ট তৈরি করা হয়েছে।

• 'construct_btree' মেথডটি ব্যবহার করে পূর্বে নির্দিষ্ট উপাদানগুলো নেয়া হয়েছে বাইনারি ট্রি নির্মাণ করতে।

• এই ট্রিতে পোস্ট অর্ডার ট্রাভার্সাল এবং ইন অর্ডার ট্রাভার্সাল সম্পাদন করা হয়েছে।

• প্রাসঙ্গিক আউটপুট কনসোলে প্রদর্শিত হয়েছে।