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

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

问题似乎是树中没有正确记住前辈。由于某种原因，兄弟节点突然得到了他们children的所有前辈。这是程序的输出：

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()。

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

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

Python 中的树似乎构建不正确

Tree seemingly building incorrectly in Python

python

tree

nodes

data-structures

python-3.x