Рекурсивный объектный референс Python в структуре данных Tree

Question

Я как-то новичок в питоне.Мне нужно было использовать дерево для хранения некоторых данных (пути к файлам). Проблема в том, что когда я генерирую дерево, кажется, что все объекты после корня ссылаются на один и тот же объект, хотя пошаговая отладка показала обратное.Вот мой (свернутый) код: сначала класс узла:

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

Дети - это список узлов 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 -> объект с 3 точными узлами -> один и тот же объект ->тот же объект до бесконечности, в то время как ожидаемый: root -> объект -> первые дети -> вторые дети -> третьи дети -> и т.д. Я уверен, что проблема связана с тем, как python обрабатывает ссылки на объекты, но я не могу видеть, гдепроблема точно.Любая помощь?

Обновление:

Я воспроизвел проблему с меньшим кодом (тот же класс 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 дал вам ссылку на Руководство по стилю для кода Python ), потому что это делает ваши ошибки легче идентифицировать.

Теперь, что здесь не так?Когда вы пишете:

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

Вы не даете начальное значение полей экземпляра. Вы создаете поля класса инициализации (статические). Следовательно, Children является статическим полем класса 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, это статическое поле Children класса PathElement:

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