递归查找链的元素

Question

我想递归地 return 从 parent 到家谱中最后一个孩子的链。我从代码开始，但不知道它有什么问题：

class Tree:
    def __init__(self,kid,parent = None):
        self.kid = kid
        self.parent = parent


    def parent_chain(self):
        if self.parent != None:
            self.parent_chain()
        else:
            return self.kid # If no parent

a = Tree('Adam')
b = Tree('Beda')
c = Tree('Ceda')

c.parent = b
b.parent = a

print(c.parent_chain()) # Want it to return Adam --> Beda --> Ceda

Answer 1

您的代码有两个问题：

无论何时组装链，您都需要在 parent 上调用 .parent_chain()，而不是您当前所在的节点。否则，您将在一个节点上重复调用 .parent_chain()，直到递归超过递归深度。
您正在将字符串设置为孩子引用的值。您可能想要存储某种单独的标签。这不会直接影响你在这里尝试做的事情，但它几乎肯定是一个错误，如果你想以任何方式使用 child 指针（例如，如果你想扩展此代码从 parent 读取到 child).

这是解决这些问题的代码片段。

class Tree:
    def __init__(self, val, kid=None, parent=None):
        self.val = val
        self.kid = kid
        self.parent = parent

    def parent_chain(self):
        if self.parent:
            result = self.parent.parent_chain()
            result.append(self.val)
            return result
        else:
            return [self.val]

a = Tree('Adam')
b = Tree('Beda')
c = Tree('Ceda')

c.parent = b
b.parent = a

print(c.parent_chain()) # Prints ['Adam', 'Beda', 'Ceda']

递归查找链的元素

Recursively finding elements of the chain

recursion

class

nodes

chain

python-3.x