ধরুন, আমাদের একটি অ্যারেতে একটি n-ary গাছের নোড দেওয়া হয়েছে। আমাদের খুঁজে বের করতে হবে এবং গাছের রুট নোডটি পুনর্গঠন করে ফেরত দিতে হবে। প্রি-অর্ডার স্বরলিপিতে ফিরে আসা নোড থেকে সম্পূর্ণ গাছটি প্রদর্শন করতে হবে।
সুতরাং, যদি ইনপুট মত হয়
তাহলে আউটপুট হবে
<প্রে>[14, 27, 32, 42, 56, 65]আমরা গাছের প্রি অর্ডার ট্রাভার্সাল প্রদর্শন করতে গাছের মূল ব্যবহার করব। সুতরাং, আউটপুট হল গাছের একটি প্রি অর্ডার ট্রাভার্সাল।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
indegree :=পূর্ণসংখ্যা মান সম্বলিত একটি নতুন মানচিত্র
-
গাছের প্রতিটি নোডের জন্য, করুন
-
প্রতিটি শিশুর জন্য নোডের চিলড্রেন পয়েন্টার, করুন
-
indegree[সন্তানের মান] :=indegree[সন্তানের মান] + 1
-
-
-
গাছের প্রতিটি নোডের জন্য, করুন
-
যদি indegree[নোডের মান] 0 এর সমান হয়, তাহলে
-
রিটার্ন নোড
-
-
-
রিটার্ন নাল
উদাহরণ (পাইথন)
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
ইমপোর্ট কালেকশনক্লাস নোড:def __init__(self, value, child =None) -> None:self.val =value self.children =[] if child !=None:for value in child:self.children.append( value)def solve(tree):indegree =collections.defaultdict(int) গাছে নোডের জন্য:node.children-এ শিশুর জন্য:indegree[child.val] +=গাছে নোডের জন্য 1:যদি indegree[node.val] ==0:রিটার্ন নোড রিটার্ন নোনেডেফ ট্রিপ্রিন্ট(নোড, ট্রি):যদি নোড ==কোনটিই না:ট্রি.অ্যাপেন্ড("কোনও") রিটার্ন ট্রি যদি ট্রি ==কোনটি নেই:ট্রি =[] ট্রি.অ্যাপেন্ড(নোড.ভাল) সন্তানের জন্য node.children এ:ট্রিপ্রিন্ট(শিশু, গাছ) রিটার্ন ট্রিনোড 6 =নোড(65)নোড5 =নোড(56)নোড4 =নোড(42, [নোড5, নোড6])নোড3 =নোড(32)নোড2 =নোড(27)নোড1 =Node(14, [node2, node3, node4])tree =[node2, node1, node5, node3, node6, node4]root =solve(tree)print(treeprint(root, None)) ইনপুট
node6 =Node(65)node5 =Node(56)node4 =Node(42, [node5, node6])node3 =Node(32)node2 =Node(27)node1 =Node(14, [node2, node3, node4])tree =[node2, node1, node5, node3, node6, node4]
