ধরুন, আমাদের একটি এন-আরি গাছ দেওয়া হয়েছে যার মূল আমাদের 'মূল' দেওয়া হয়েছে। আমাদের সম্পূর্ণ n-ary বাইনারি গাছের একটি অনুলিপি তৈরি করতে হবে এবং উভয় গাছের একটি প্রি-অর্ডার ট্রাভার্সাল করতে হবে। অনুলিপি করা গাছটিকে অন্য রুট নোড ব্যবহার করে সংরক্ষণ করতে হবে। গাছের নোড গঠন নিচে দেওয়া হল -
নোড:মান:<পূর্ণসংখ্যা> শিশু:<অ্যারে>
সুতরাং, যদি ইনপুট মত হয়
, তাহলে আউটপুট হবে
<প্রে>[14, 27, 32, 42, 56, 65]ইনপুট ট্রি এবং আউটপুট ট্রির প্রি-অর্ডার উপস্থাপনা একই হবে যেভাবে গাছের একটি সঠিক কপি তৈরি করা হয়েছে।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
যদি রুট খালি না হয়, তাহলে
-
রিটার্ন রুট
-
-
head :=রুটের মান সহ একটি নতুন নোড
-
q :=রুট এবং হেড উপাদান ধারণকারী একটি নতুন ডিক
-
q খালি না থাকার সময়, করুন
-
নোড :=q
থেকে প্রথম উপাদানটি পপ করুন -
ক্লোনড :=q
থেকে প্রথম উপাদানটি পপ করুন -
node.children-এ প্রতিটি chld-এর জন্য করুন
-
new_n :=chld এর মান ধারণকারী একটি নতুন নোড
-
ক্লোন করা শিশুদের সাথে new_n যোগ করুন
-
q
এর শেষে chld এবং new_n ঢোকান
-
-
-
রিটার্ন হেড
উদাহরণ (পাইথন)
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
সারি থেকে আমদানি করা dequeclass নোড: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(root):রুট না হলে:রিটার্ন root head =Node(root.val) q =deque([(root, head)]) যখন q:node, cloned =q.popleft() chld এর জন্য node.children এ:new_n =Node(chld.val) cloned.children.append(new_n) q.append((chld,new_n)) রিটার্ন হেডডেফ ট্রিপ্রিন্ট(নোড, ট্রি):যদি নোড ==কোনটিই না:tree.append( "কোনটিই নয়") রিটার্ন ট্রি যদি ট্রি ==কোনোটিই না:নোড. চিল্ড্রেনে শিশুর জন্য গাছ =[] ট্রি.অ্যাপেন্ড(নোড.ভাল):ট্রিপ্রিন্ট(শিশু, গাছ) রিটার্ন ট্রিনোড6 =নোড(65)নোড5 =নোড(56) node4 =Node(42, [node5, node6])node3 =Node(32)node2 =Node(27)node1 =Node(14, [node2, node3, node4])root =node1copynode =solve(root)print(treeprint( কপিনোড, কোনটিই নয়))
ইনপুট
node6 =Node(65)node5 =Node(56)node4 =Node(42, [node5, node6])node3 =Node(32)node2 =Node(27)node1 =Node(14, [node2, node3, node4])root =node1
