Python 树数据结构中的递归 object 引用

Question

我是 python 的新手。我需要使用树来存储一些数据（文件路径），问题是当我生成树时，似乎根引用相同的 object 之后的所有 object，尽管逐步调试显示相反。这是我的（最小化的）代码：首先是节点 class:

class PathElement:  

  Element = ""
  IsStatic = True
  Children = []
  ChildrenCount = 0 

  def __init__(self, Element, IsStatic=True):
      self.Element = Element
      self.IsStatic = IsStatic
      if not IsStatic:
          self.Element = [] 

  def AddChild(self, Child):
      print(self, "    ", Child)
      self.Children.append(Child)
      self.ChildrenCount = len(self.Children)
      return Child

Children 是 PathElement 节点的列表。构建树的代码：

def UnFoldAndCheck(self):
    Path = PathElement("root")
    Handler = Path
    Index = 0
    Count = len(self.Path)
    while Index < Count:

        element = self.Path[Index]

        if something:
            Child = None
            Child = PathElement(element)
            Handler.AddChild(Child)
            Handler = None #Those added to debug the problem
            Handler = Child
        elif other_thing:
            if condition:
                if some_large_condition:
                    ChildExec = None
                    ChildExec = PathElement(element, False)
                    for i in range(0, 5):
                        ChildExec.Element.append(self.Path[Index + i])
                    Handler.AddChild(ChildExec)
                    Handler = None
                    Handler = ChildExec
                    Index += 4
            elif another_condition:
                ChildOp = None
                ChildOp = PathElement(element, False)
                Handler.AddChild(ChildOp)
                Handler = None
                Handler = ChildOp
            elif some_else_condition:
                 if condition:
                    ChildExec = None
                    ChildExec = PathElement(element, False)
                    for i in range(0, 3):
                        ChildExec.Element.append(self.Path[Index + i])
                    Handler.AddChild(ChildExec)
                    Handler = None
                    Handler = ChildExec
                    Index += 2

                elif different_condition:
                    ChildExec = None
                    ChildExec = PathElement(element, False)
                    for i in range(0, 3):
                        ChildExec.Element.append(self.Path[Index + i])
                    Handler.AddChild(ChildExec)
                    Handler = None
                    Handler = ChildExec
                    Index += 1
        Index += 1
    return Path

我的问题是，当我使用它时，在构建树之后，它总是具有相同的结构： root -> object with 3 exact nodes -> same object -> same object to infinity 而预期的是： root -> object -> 第一个 children -> 第二个 children -> 第三个 children -> 等等我确定问题与 python 如何处理 object 引用有关，但我看不出问题到底出在哪里。有什么帮助吗？

更新：

我用更小的代码重现了这个问题（相同的 class PathElement）：

from PathElement import PathElement
Path = PathElement("root")
Handler = Path
for i in range(1,6):
   Child = PathElement("child"+str(i))
   Handler.AddChild(Child)
   Handler = Child
Tree = Path
while True:
   print(Tree.Element)
   if len(Tree.Children) > 0:
      Tree = Tree.Children[0]
   else:
       break

这段代码会无限循环

Answer 1

我猜你来自 Java 或类似的语言。坚持 Python 的约定很重要（Jakob Sachs 给你的 va link 到 Style Guide for Python Code）因为这会让你的错误更容易识别。

现在，这里出了什么问题？当您写道：

class PathElement():  
  Children = []
  Element = ""
  IsStatic = True
  ChildrenCount = 0

您没有给出实例字段的初始值。 您创建了一个初始化 class（静态）字段。 因此，Children 是 class PathElement 的静态字段。这是一个例子：

class A():
    i = []

a = A()
b = A()

a.i.append(1) 
b.i.append(2) 
assert a.i == b.i == [1,2]

当您尝试读取树的最左侧部分（子节点 0，子节点 0 的子节点 0，...）时会发生什么？

while True:
   print(Tree.Element)
   if len(Tree.Children) > 0:
      Tree = Tree.Children[0]
   else:
       break

只需将 Tree.Children 替换为真正的 PathElement.Children，即 class PathElement:[=22 的静态字段 Children =]

while True:
   print(Tree.Element)
   if len(PathElement.Children) > 0:
      Tree = PathElement.Children[0] # Tree has always the same value.
   else:
       break

现在，你可以写一个例子：

class PathElement:  
    def __init__(self, element):
        self.__element = element
        self.__children = []

    def add_child(self, child):
        self.__children.append(child)

    def children(self):
        return list(self.__children)

    def element(self):
        return self.__element

path = ["a", "b", "c", "d", "e", "f"]

root = PathElement("root")
handler = root
while path:
    child = PathElement(path.pop(0)) # you can put some conditions here, take more elements of path, ...
    handler.add_child(child)
    handler = child

def dfs(node):
    for c in node.children():
        yield c.element()
        yield from dfs(c)

print (list(dfs(root)))
# a b c d e f

Python 树数据结构中的递归 object 引用

Python recursive object refrence in Tree datastructure

python

python-3.x

object

tree

object-reference

更新：