Início / coding / Perguntas / 79354652
Accepted
Hyde Fukui
Asked: 2025-01-14 18:18:55 +0800 CST

Encontre um caminho para a raiz em dados estruturados em árvore (função recursiva em Python3)

  • 772

Em uma classe para dados estruturados em árvore, estou tentando obter o caminho de um certo nó para a raiz. O get_forward_path()método abaixo funciona na primeira execução, mas sua lista de saída cresce para sempre toda vez que eu executo o método. Ela continua crescendo mesmo se eu aplicar o método a nós diferentes. Por que isso acontece mesmo que o pathargumento seja redefinido para seu padrão (a lista em branco) quando o método é chamado?

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.children = []
        self.parent = None
        
    def add_child(self, child):
        child.parent = self
        self.children.append(child)

    def print_tree(self):
        spaces = ' ' * self.get_level() * 3
        prefix = spaces + "|__" if self.parent else ""
        print(prefix + self.data)
        if self.children:
            for child in self.children:
                child.print_tree()
    
    def get_forward_path(self,path=[]):
        if not self.parent:
            path.append(self.data)
        else:
            path.append(self.data)
            p = self.parent
            p.get_forward_path(path)
        return path[::-1]

    def get_level(self):
        level = 0
        p = self.parent
        while p:
            level += 1
            p = p.parent

        return level

root = TreeNode("Electronics")

laptop   = TreeNode("Laptop")
Mac      = TreeNode("Mac")
Surface  = TreeNode("Surface")
ThinkPad = TreeNode("ThinkPad")
laptop.add_child(Mac)
laptop.add_child(Surface)
laptop.add_child(ThinkPad)

cellphone    = TreeNode("Cell Phone")
iPhone       = TreeNode("iPhone")
Google_Pixel = TreeNode("Google Pixel")
Vivo         = TreeNode("Vivo")
cellphone.add_child(iPhone)
cellphone.add_child(Google_Pixel)
cellphone.add_child(Vivo)

tv      = TreeNode("TV")
Samsung = TreeNode("Samsung")
LG      = TreeNode("LG")
tv.add_child(Samsung)
tv.add_child(LG)

root.add_child(laptop)
root.add_child(cellphone)
root.add_child(tv)

root.print_tree()

Electronics
   |__Laptop
      |__Mac
      |__Surface
      |__ThinkPad
   |__Cell Phone
      |__iPhone
      |__Google Pixel
      |__Vivo
   |__TV
      |__Samsung
      |__LG

Samsung.get_forward_path()

['Electronics', 'TV', 'Samsung']

Samsung.get_forward_path()

['Electronics', 'TV', 'Samsung', 'Electronics', 'TV', 'Samsung']

iPhone.get_forward_path()

['Electronics',
 'Cell Phone',
 'iPhone',
 'Electronics',
 'TV',
 'Samsung',
 'Electronics',
 'TV',
 'Samsung']
python-3.x

2 respostas

  1. Você definiu path=[], este é um argumento padrão e ele foi criado uma vez, não toda vez que você chama a função.

    Então ele é criado na primeira chamada da função get_forward_path e então o código continua usando o mesmo argumento ( append ).

    A solução é simples: use path = None na função def , verifique se path é None e crie a lista vazia

    def get_forward_path(self, path=None):
    if path is None:
        path = [] 
    
    if not self.parent:
        path.append(self.data)
    • 1
  2. Best Answer

    Recursão é uma herança funcional e, portanto, usá-la com estilo funcional produz os melhores resultados. Isso significa evitar coisas como mutação, reatribuição de variáveis ​​e outros efeitos colaterais.

    Quando você escreve path.append(something), a appendfunção muta a pathvariável. Em vez de mutar, use +which concatena listas de forma não destrutiva -

    def get_forward_path(self, path=[]):
    next_path = [self.data] + path   # ✅ no mutation!
    if not self.parent:
        return next_path
    else:
        return self.parent.get_forward_path(next_path)

    Seguindo essa disciplina, não há problema em usar path=[]o valor padrão.

    Benefício adicional: observe que acrescentamos os dados conforme a lista de saída é criada, o que significa que não precisamos pensar em reverter a saída final.

    • 1

relate perguntas