在Python中查找n叉树的根节点的程序

在Python中查找n叉树的根节点的程序

假设我们有一个n-ary树的节点数组。通过重建树,我们必须找到并返回树的根节点。从返回的节点中以前序遍历的方式显示完整的树。

因此,如果输入如下所示

在Python中查找n叉树的根节点的程序

那么输出将是

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

我们将使用树的根节点来显示树的先序遍历。因此,输出是树的先序遍历。

要解决这个问题,我们将遵循以下步骤:

  • indegree := 包含整数值的新映射

  • 对于树中的每个节点,做以下步骤

    • 对于节点的子指针中的每个子节点,做以下步骤
      • indegree[子节点的值] := indegree[子节点的值] + 1
  • 对于树中的每个节点,做以下步骤
    • 如果indegree[节点值]等于0,则
      • 返回节点
  • 返回null

示例(Python)

让我们看看以下实现,以更好地理解:

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]

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程