Python में n-ary ट्री का रूट खोजने का प्रोग्राम

मान लीजिए, हमें एक n-ary ट्री के नोड्स एक सरणी में दिए गए हैं। हमें ट्री को पुनर्निर्मित करके उसका रूट नोड ढूंढना और वापस करना है। वापस किए गए नोड से पूरा ट्री प्रीऑर्डर नोटेशन में प्रदर्शित करना है।

इसलिए, यदि इनपुट निम्न ट्री है:

तो आउटपुट होगा:

[14, 27, 32, 42, 56, 65]

हम ट्री के प्रीऑर्डर ट्रैवर्सल को प्रदर्शित करने के लिए ट्री के रूट का उपयोग करेंगे। इसलिए, आउटपुट ट्री का प्रीऑर्डर ट्रैवर्सल है।

हल करने के चरण

1. indegree := पूर्णांक मानों वाला एक नया मैप
2. ट्री में प्रत्येक node के लिए:
   • node के children पॉइंटर्स में प्रत्येक child के लिए:
     • indegree[child का मान] := indegree[child का मान] + 1
3. ट्री में प्रत्येक node के लिए:
   • यदि indegree[node का मान] == 0, तो node वापस करें
4. null वापस करें

उदाहरण (Python)

import collections

class Node:
    def __init__(self, value, child=None) -> None:
        self.val = value
        self.children = []
        if child is not 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 is None:
        tree.append("None")
        return tree
    if tree is 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]