मान लीजिए, हमें एक एन-आर्य वृक्ष प्रदान किया गया है जिसकी जड़ हमें 'जड़' दी गई है। हमें पूर्ण एन-आरी बाइनरी ट्री की एक प्रति बनानी होगी और दोनों पेड़ों का प्रीऑर्डर ट्रैवर्सल करना होगा। कॉपी किए गए पेड़ को दूसरे रूट नोड का उपयोग करके संग्रहीत किया जाना है। पेड़ की नोड संरचना नीचे दी गई है -
Node: value : <integer> children : <array>
तो, अगर इनपुट पसंद है
, तो आउटपुट होगा
[14, 27, 32, 42, 56, 65]
इनपुट ट्री और आउटपुट ट्री का प्रीऑर्डर प्रतिनिधित्व वैसा ही होगा जैसा ट्री की एक सटीक कॉपी बनाई गई है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
अगर रूट खाली नहीं है, तो
-
वापसी जड़
-
-
सिर :=रूट के मान के साथ एक नया नोड
-
q :=एक नया डेक जिसमें तत्व जड़ और शीर्ष शामिल हैं
-
जबकि q खाली नहीं है, करें
-
नोड:=q से पहला तत्व पॉप करें
-
क्लोन:=क्यू से पहला तत्व पॉप करें
-
नोड.चिल्ड्रेन में प्रत्येक chld के लिए, करें
-
new_n :=एक नया नोड जिसमें chld का मान हो
-
क्लोन के बच्चों के लिए new_n संलग्न करें
-
q के अंत में chld और new_n डालें
-
-
-
वापसी सिर
उदाहरण (पायथन)
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
from queue import deque
class Node:
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):
if not root:
return root
head = Node(root.val)
q = deque([(root, head)])
while q:
node, cloned = q.popleft()
for chld in node.children:
new_n = Node(chld.val)
cloned.children.append(new_n)
q.append((chld,new_n))
return head
def treeprint(node, tree):
if node == None:
tree.append("None")
return tree
if tree == None:
tree = []
tree.append(node.val)
for child in node.children:
treeprint(child, tree)
return tree
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
copynode = solve(root)
print(treeprint(copynode, None)) इनपुट
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
आउटपुट
[14, 27, 32, 42, 56, 65]