python - Python 中的树似乎构建不正确

Question

data = {'murtaza':('arnav', 'ohjun'),
        'ohjun':('arnav', 'murtaza'),
        'arnav':('ohjun', 'murtaza')}

class node:
    predecessors=[]
    nexts=[]
    student=''
    def __init__(self, student='', predecessors=[]):
        self.student=student
        self.predecessors=predecessors
    def grow(self, max=6, depth=0):
        if not self.student in self.predecessors:
            self.predecessors.append(self.student)
            for pref in data[self.student]:
                next=node(pref, self.predecessors)
                print(depth, self.predecessors, self.student, pref)
                next.grow(max, depth=depth+1)
                self.nexts.append(next)
        else:
            return

所以，这是我的节点数据和类定义。当我在节点对象上调用 grow() 方法时，我期望发生的情况如下:它查找数据中的学生姓名，然后查找与该学生关联的每个姓名(即他们的偏好，因此 for pref in data[self.student]) 创建一个新节点，将其添加到从当前节点分支的节点中，然后调用 grow()在那个新节点上。然后，该方法将继续构建树，除非学生在序列中出现两次，因此检查 if not self.student in self.predecessors。

问题似乎是树中没有正确记住前任。由于某种原因，兄弟节点突然获得了其 child 的所有前辈。这是程序的输出:

0 ['murtaza'] murtaza arnav
1 ['murtaza', 'arnav'] arnav ohjun
2 ['murtaza', 'arnav', 'ohjun'] ohjun arnav
2 ['murtaza', 'arnav', 'ohjun'] ohjun murtaza #as expected up to here
1 ['murtaza', 'arnav', 'ohjun'] arnav murtaza
0 ['murtaza', 'arnav', 'ohjun'] murtaza ohjun

我希望读到:

0 ['murtaza'] murtaza arnav
1 ['murtaza', 'arnav'] arnav ohjun
2 ['murtaza', 'arnav', 'ohjun'] ohjun arnav
2 ['murtaza', 'arnav', 'ohjun'] ohjun murtaza 
1 ['murtaza', 'arnav'] arnav murtaza
0 ['murtaza'] murtaza ohjun
1 ['murtaza', 'ohjun'] ohjun arnav
2 ['murtaza', 'ohjun', 'arnav'] arnav ohjun
2 ['murtaza', 'ohjun', 'arnav'] arnav murtaza
1 ['murtaza', 'ohjun'] ohjun murtaza

是我对我写的代码理解错误，还是我对算法的理解错误？还是我的实现有误？我真的以为我了解如何制作一棵树，但这似乎并没有按照我想象的方式工作。

编辑:我应该补充一下，主体如下所示:

mort = node()
mort.student='murtaza'
mort.grow()

Answer 1

这一行:

next=node(pref, self.predecessors)

不复制 self.predecessors ，而是传递对命名 list 的引用目的。同样，这一行:

    self.predecessors=predecessors

不复制 predecessors 。因此，您所有的node对象在完全相同的列表上进行操作；当一个对象调用.append()时，所有对象' predecessor列表已更新。

解决方案是将其中一个调用替换为 copy.deepcopy() ，像这样:

    self.predecessors = copy.deepcopy(predecessors)

根据您的精确数据结构，您可能需要 copy.copy()相反。

此外，您为 predecessors 提供的默认值可能与您的问题无关。在__init__()不会按您期望的方式工作。 (参见here)。试试这个:

def __init__(self, student='', predecessors=None):
    self.student=student
    if predecessors is None:
        self.predecessors = []
    else:
        self.predecessors=copy.deepcopy(predecessors)