修复Python中的深度树

Question

我想实现一个具有固定深度的树结构，即当向叶节点添加子节点时，整个树结构应该“向上移动”。这也意味着多个根可以同时存在。请参阅下面的示例： 在此示例中，绿色节点在迭代 1 中添加，删除顶部节点（灰色）并在 K=0 处创建两个蓝色节点并成为迭代 1 的根节点。

我该如何实施呢？

Answer 1

存储每个节点及其父节点的引用。当您将一个节点作为子节点添加到其中时，请向上遍历父节点（从要添加到的节点），并在将其所有子节点中的父引用设置为 None 后删除第三个节点。然后将已删除节点的子节点添加到树列表中。

class Node(object):

    depth = 4

    def __init__(self, parent, contents):
        self.parent = parent
        self.contents = contents
        self.children = []


def create_node(trees, parent, contents):
    """Adds a leaf to a specified node in the set of trees.

    Note that it has to have access to the container that holds all of the trees so
    that it can delete the appropriate parent node and add its children as independent 
    trees. Passing it in seems a little ugly. The container of trees could be a class
    with this as a method or you could use a global list. Or something completely
    different. The important thing is that if you don't delete every reference to the
    old root, you'll leak memory.
    """
    parent.children.append(Node(parent, contents))

    i = 0:
    L = Node.depth - 1
    while i < L:
        parent = parent.parent
        if not parent:
            break
        i += 1
    else:
        for node in parent.children:
            node.parent = None
        trees.extend(parent.children)
        i = trees.find(parent)
        del trees[i]