python - 如何将孙子添加到 python 树？

Question

我试图在 python 中实现一个 Tree，我发现了 this线程并尝试处理我自己的树，但我被困在如何添加孙子的问题上。

我要构建的树是这样的:

Root
    ch1
        ch2
            ch3
            ch4

所以我认为 add_child() 方法应该是递归的:

1、如果这棵树没有子树，则将子树添加到Root

2、对于Root的每个子节点，如果其中一个子节点等于parent，则向其添加子节点并停止循环(因此新的子节点实际上是一个孙子节点)。

3、如果没有匹配，则对当前的 child 调用add_child()。

但是我的代码给了我:

Root
    ch1
        ch2
            ch3
                ch4

顺便说一句，每次我在使用递归算法时都会感到困惑，有人能给我一些关于如何编写递归代码的好建议吗？或者有什么好的教程吗？

class Node(object):
    def __init__(self, data, parent=None):
        self.data = data
        self.children = []
        self.parent = parent

    def __repr__(self, level=0):
        ret = "\t" * level + repr(self.data) + "\n"
        for child in self.children:
            ret += child.__repr__(level + 1)
        return ret

    def add_child(self, node, parent):

        if self.children == []:
            self.children.append(node)
            return

        for child in self.children:
            if child == parent:
                child.children.append(node)
                return
            else:
                child.add_child(node, parent)

        # self.children.append(node)


if __name__ == '__main__':

    tree = Node('Root')
    tree.add_child(Node('ch1'), 'Root')
    tree.add_child(Node('ch2'), 'ch1')
    tree.add_child(Node('ch3'), 'ch2')
    tree.add_child(Node('ch4'), 'ch2')
    print tree

Answer 1

以下部分没有意义:

if self.children == []:
    self.children.append(node)
    return

如果一个节点没有子节点，您会自动将该节点添加到该节点吗？如果节点应该添加到不同的父节点怎么办？

你可能打算写:

def add_child(self, node, parent):
    if self.data == parent:
        self.children.append(node)
        return
    for child in self.children:
        child.add_child(node, parent)

按预期生成树。