我正在尝试根据给定的输入创建一棵树。那里将有一个根,包括子节点和子子节点。我可以实现树,在其中我可以将子节点添加到特定的主节点(我已经知道根)。但是,我试图弄清楚实现树的推荐方法是什么,我们必须首先从给定的输入集中找到根节点。举个例子:
There are n lines,
Value in each line represent the master node of that line number.
4 ( n = 4, next n lines)
1 ( 1 is a master node of 1, here line number is 1)
1 (1 is a master node of 2, here line number is 2)
2 (2 is a master node of 3, here line number is 3)
1 (1 is a master node of 4, here line number is 4)
所以树应该看起来像,
1
/ |
2 4
|
3
在这里,我们可以看到根节点是1。但是在知道所有输入值之前,我们无法猜测根节点。在实现树之前,我应该首先从输入中找出根节点吗?或者还有其他办法吗?
下面的代码是向树中添加一个节点:
class Node :
# Utility function to create a new tree node
def __init__(self ,key):
self.key = key
self.child = []
def printNodeLevelWise(root):
if root is None:
return
queue = []
queue.append(root)
while(len(queue) >0):
n = len(queue)
while(n > 0) :
# Dequeue an item from queue and print it
p = queue[0]
queue.pop(0)
print (p.key,)
# Enqueue all children of the dequeued item
for index, value in enumerate(p.child):
queue.append(value)
n -= 1
print ("")
root = Node(1)
root.child.append(Node(2))
root.child.append(Node(4))
root.child[0].child.append(Node(3))
printNodeLevelWise(root)
上面的代码将实现这棵树:
1
/ |
2 4
|
3
但是,从给定的输入实现相同的建议方法是什么?
最佳答案
假设:
- “主人”的意思是“ parent ”,并且
- 当一行具有自引用时 - 使得 i 出现在主列表的 i 行上 - 它是根
...那么你可以像这样继续:
nodes = {} # dictionary of all nodes keyed by their value
root = None
n = int(input()) # get the number of nodes
for linenum in range(1, n+1):
parentnum = int(input()) # get the "master" for this line
# create the involved nodes that do not yet exist:
if not linenum in nodes:
nodes[linenum] = Node(linenum)
if not parentnum in nodes:
nodes[parentnum] = Node(parentnum)
if parentnum == linenum: # a self-reference indicates the root
root = nodes[parentnum]
else: # set the parent-child relationship
nodes[parentnum].child.append(nodes[linenum])
关于python - 根据给定的输入集实现 n 叉树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59277021/