0

你能告诉我为什么需要在 for 循环中附加父子关系以获得预期的输出。我不了解 Python 中的范围。

#a unique id to be given to each node
current_id = 0
#ids = [parent_id, current_id]; stores parent_child tree data
ids = []
#MWE of depth first search
def bt(parent_id):
   global ids
   global current_id
   #increament current id because we just created a new node
   current_id = current_id +1
   #store the parent to child relationship in the list called ids
   ids.append([parent_id,current_id]) 
   #show the parent child relationship that is getting append to the ids list
   print 'parent-child (outside loop)', [parent_id,current_id]
   if(parent_id) > 1:
       return
   for i in range(2):
        print 'parent-child (inside loop)', [parent_id,current_id]
        bt(current_id)
#run depth first search
print bt(0)
#print list of parent to child relationships
print 'list of parent-child relationships\n',ids
print 'expected output',[[0,1],[1,2],[1,3],[0,4]]

编辑：这个脚本的输出是：

parent-child (outside loop) [0, 1]
parent-child (inside loop) [0, 1]
parent-child (outside loop) [1, 2]
parent-child (inside loop) [1, 2]
parent-child (outside loop) [2, 3]
parent-child (inside loop) [1, 3]
parent-child (outside loop) [3, 4]
parent-child (inside loop) [0, 4]
parent-child (outside loop) [4, 5]
None
list of parent-child relationships
[[0, 1], [1, 2], [2, 3], [3, 4], [4, 5]]
expected output [[0, 1], [1, 2], [1, 3], [0, 4]]
4

1 回答 1

0

我相信您遇到的问题是由于使用全局变量current_id. 当您在递归调用中创建一个孩子时，current_id也会针对父母的调用进行更新。

这是一个更简单的例子：

 x = 0
 def foo(level=0):
     global x
     print(" "*level+str(x))
     x += 1
     if level < 3:
         foo(level+1)
     print(" "*level+str(x))
 foo()

这将打印：

 0
  1
   2
    3
    4
   4
  4
 4

由于level参数，缩进表示递归级别。每次递归调用都会增加的值，x但当调用展开时它不会降低。那是因为它是一个全局变量，所以递归的内部级别所做的更改会被外部级别看到。

current_id在您的代码中，您可以通过在局部变量中保留对原始值的引用来解决此问题：

def bt(parent_id):
   global current_id
   current_id = current_id +1
   ids.append([parent_id,current_id])

   my_id = current_id # make a local reference to the current_id

   print('parent-child (outside loop)', [parent_id,my_id])
   if(parent_id) > 1:
       return
   for i in range(2):
        print('parent-child (inside loop)', [parent_id,my_id])
        bt(my_id) # use the local reference for the recursion

输出仍然不是您所期望的，但它是有道理的：

parent-child (outside loop) [0, 1]
parent-child (inside loop) [0, 1]
parent-child (outside loop) [1, 2]
parent-child (inside loop) [1, 2]
parent-child (outside loop) [2, 3]
parent-child (inside loop) [1, 2]
parent-child (outside loop) [2, 4]
parent-child (inside loop) [0, 1]
parent-child (outside loop) [1, 5]
parent-child (inside loop) [1, 5]
parent-child (outside loop) [5, 6]
parent-child (inside loop) [1, 5]
parent-child (outside loop) [5, 7]
None
list of parent-child relationships
[[0, 1], [1, 2], [2, 3], [2, 4], [1, 5], [5, 6], [5, 7]]
expected output [[0, 1], [1, 2], [1, 3], [0, 4]]

如果您要制作一个图表来显示您已构建的树形组织ids，您将获得：

    (0)  # This is not a real element, but the root's "parent"
     |
     1
    / \
   /   \
  2     5
 / \   / \
3   4 6   7
于 2013-09-14T03:58:09.747 回答