数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言程序设计
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究用 Python 寻找 n 叉树根节点的程序
假设我们以数组的形式获得了 n 叉树的节点。我们必须通过重建它来找到并返回树的根节点。完整的树必须以先序表示法显示在返回节点中。
所以，如果输入如下
那么输出将是
[14, 27, 32, 42, 56, 65]
我们将使用树的根来显示树的先序遍历。因此，输出便是树的先序遍历。
为了解决这个问题，我们将遵循以下步骤 −
indegree := 包含整数值的新映射
对于树中的每个节点，执行操作
对于节点的每个子节点指针，执行操作
indegree[子节点值] := indegree[子节点值] + 1
对于树中的每个节点，执行操作
如果 indegree[节点值] 与 0 相同，则
返回 node
返回 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]
更新于：18-5-2021
545 次浏览
广告