मान लीजिए, हमें एक सरणी में n-ary पेड़ के नोड दिए गए हैं। हमें पेड़ के रूट नोड को फिर से ढूंढकर वापस करना है। पूर्ण वृक्ष को पूर्व-आदेश संकेतन में लौटाए गए नोड से प्रदर्शित किया जाना है।
तो, अगर इनपुट पसंद है
तो आउटपुट होगा
[14, 27, 32, 42, 56, 65]
हम पेड़ के पूर्व-आदेश ट्रैवर्सल को प्रदर्शित करने के लिए पेड़ की जड़ का उपयोग करेंगे। तो, आउटपुट ट्री का प्री-ऑर्डर ट्रैवर्सल है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
डिग्री :=पूर्णांक मानों वाला एक नया नक्शा
-
पेड़ में प्रत्येक नोड के लिए, करें
-
बच्चों में प्रत्येक बच्चे के लिए नोड के पॉइंटर्स, करें
-
डिग्री [बच्चे का मूल्य]:=डिग्री [बच्चे का मूल्य] + 1
-
-
-
पेड़ में प्रत्येक नोड के लिए, करें
-
अगर डिग्री [नोड का मान] 0 के समान है, तो
-
वापसी नोड
-
-
-
वापसी शून्य
उदाहरण (पायथन)
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
import collections
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(tree):
indegree = collections.defaultdict(int)
for node in tree:
for child in node.children:
indegree[child.val] += 1
for node in tree:
if indegree[node.val] == 0:
return node
return None
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])
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]
आउटपुट
[14, 27, 32, 42, 56, 65]