Soy bastante nuevo en python y algoritmo y quiero declarar una función dentro de la clase en lugar de fuera de ella. Lo siguiente es lo que tengo ahora:

Una implementación general de Clase de árbol NAryTree:

class NAryTree:
    def __init__(self, key):
        self.key = key
        self.children = []
    def __str__(self):
        return str(self.key)
    def addChild(self, tree):
        self.children.append(tree)
    def getChild(self, k):
        return self.children[k]
    def getNChildren(self):
        return len(self.children)
    def __iter__(self):
        return self.children.__iter__()
    def __next__(self):
        return self.children.__next__()

Una función minSubtree(tree) para calcular la suma mínima del subárbol:

def minSubtree(tree):
    value = tree.key
    for child in tree:
        value += min(minSubtree(child), 0)
    return value

Y una función Build Tree buildMyNAryTree():

def buildMyNAryTree():
    root = NAryTree(1)

    root.addChild(NAryTree(-2))
    root.addChild(NAryTree(3))
    root.addChild(NAryTree(4))

    root.getChild(0).addChild(NAryTree(-5))
    root.getChild(1).addChild(NAryTree(6))
    root.getChild(1).addChild(NAryTree(7))
    root.getChild(2).addChild(NAryTree(-8))

    root.getChild(0).getChild(0).addChild(NAryTree(-9))
    root.getChild(0).getChild(0).addChild(NAryTree(-10))
    root.getChild(0).getChild(0).addChild(NAryTree(11))
    root.getChild(1).getChild(0).addChild(NAryTree(-4))
    root.getChild(1).getChild(1).addChild(NAryTree(12))
    root.getChild(1).getChild(1).addChild(NAryTree(-13))
    root.getChild(2).getChild(0).addChild(NAryTree(14))
    return root

Lo que quiero es declarar minSubtree(tree) dentro de la Clase, sin embargo, no sé cómo cambiar el parámetro. En otras palabras, quiero devolver la suma mínima del subárbol usando buildMyNAyTree().minSubtree() en lugar de minSubtree(buildMyNAryTree()).

2
Alex Wang 16 oct. 2018 a las 12:01

2 respuestas

La mejor respuesta

Sangra la función para que esté dentro del cuerpo de la clase y, por convención, renombra tree a self. Acceda a child.minSubtree() en lugar de minSubtree(child).

class NAryTree:
    # your other methods
    def minSubtree(self):
        value = self.key
        for child in self:
            value += min(child.minSubtree(), 0)
        return value

print(buildMyNAryTree().minSubtree()) produce -32.

3
timgeb 16 oct. 2018 a las 09:11

Creo que esto debería hacer lo que quieres:

Recorre los elementos secundarios del árbol y llama al comando minSubTree del elemento secundario.

class NAryTree:
    def __init__(self, key):
        self.key = key
        self.children = []
    def __str__(self):
        return str(self.key)
    def addChild(self, tree):
        self.children.append(tree)
    def getChild(self, k):
        return self.children[k]
    def getNChildren(self):
        return len(self.children)
    def __iter__(self):
        return self.children.__iter__()
    def __next__(self):
        return self.children.__next__()

    def minSubtree(self):
        value = self.key
        for child in self.children:
            value += min(child.minSubtree(), 0)
        return value
0
Andrew McDowell 16 oct. 2018 a las 09:10