ধরুন আমাদের একটি বাইনারি গাছ আছে। আমাদের সেই গাছের প্রি-অর্ডার ট্রাভার্সাল ফেরত দিতে হবে। তাই গাছটি যদি −
এর মত হয়
তারপর প্রি-অর্ডার ট্রাভার্সাল হবে:[3,9,20,15,7]
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- রেস এবং সেন্ট নামে খালি তালিকা তৈরি করুন।
- নোড :=রুট
- যখন নোড বা st খালি নয়
- যখন নোড নাল না হয়, তারপর
- রেজে নোডের ভ্যাল সন্নিবেশ করান, st-এ নোড ঢোকান এবং নোড সেট করুন :=নোডের বাম দিকে
- temp :=st-এর শেষ উপাদান, এবং st-এর শেষ উপাদান মুছুন
- যদি তাপমাত্রার ডান পাওয়া যায়, তাহলে
- নোড :=তাপমাত্রার ডানদিকে
- যখন নোড নাল না হয়, তারপর
- রিটার্ন রিটার্ন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
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 preorderTraversal(self, root): res = [] st = [] node = root while node or st: while node: if node.data != None: res.append(node.data) st.append(node) node = node.left temp = st[-1] st.pop() if temp.right: node = temp.right return res ob1 = Solution() head = make_tree([3,9,20,None,None,15,7]) print(ob1.preorderTraversal(head))
ইনপুট
[3,9,20,null,null,15,7]
আউটপুট
[3, 9, 20, 15, 7]
