ধরুন আমাদের একটি বাইনারি গাছ আছে। রিকারশন ব্যবহার না করে ইনঅর্ডার ট্রাভার্সাল স্কিম ব্যবহার করে আমাদের এই গাছটি অতিক্রম করতে হবে। তাই যদি গাছের মত হয়
তারপর ট্রাভার্সাল হবে [2,5,7,10,15,20]
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- দুটি অ্যারে রেস এবং স্ট্যাক তৈরি করুন, curr :=রুট সেট করুন
- একটি অসীম লুপ চালান
- যদিও কারেন্ট শূন্য নয়
- একটি স্ট্যাকের মধ্যে curr পুশ করুন এবং curr সেট করুন :=curr এর বাম
- স্ট্যাকের দৈর্ঘ্য =0, তারপর res ফেরত দিন
- নোড :=স্ট্যাক থেকে পপ করা উপাদান
- রেজে নোডের একটি মান সন্নিবেশ করান
- curr :=curr এর ডান
- যদিও কারেন্ট শূন্য নয়
উদাহরণ
আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -
class TreeNode: def __init__(self, data, left = None, right = None): self.data = data self.left = left self.right = right def insert(temp,data): que = [] que.append(temp) while (len(que)): temp = que[0] que.pop(0) if (not temp.left): temp.left = TreeNode(data) break else: que.append(temp.left) if (not temp.right): temp.right = TreeNode(data) break else: que.append(temp.right) def make_tree(elements): Tree = TreeNode(elements[0]) for element in elements[1:]: insert(Tree, element) return Tree class Solution(object): def inorderTraversal(self, root): res, stack = [], [] current = root while True: while current: stack.append(current) current = current.left if len(stack) == 0: return res node = stack[-1] stack.pop(len(stack)-1) if node.data != None: res.append(node.data) current = node.right return res ob1 = Solution() root = make_tree([10,5,15,2,7,None,20]) print(ob1.inorderTraversal(root))
ইনপুট
[10,5,15,2,7,null,20]
আউটপুট
[2,5,7,10,15,20]
