修复Python中的深度树

Question

我想实现一个树形结构，这个树的深度是固定的。也就是说，当我给叶子节点添加子节点时，整个树结构应该“向上移动”。这也意味着可以同时存在多个根节点。下面是一个例子：

在这个例子中，绿色的节点是在第一轮添加的，删除了顶部的灰色节点，然后把两个蓝色节点（在K=0和第一轮）变成了根节点。

我该如何实现这个呢？

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]