在Python中修复深度树

Question

我想实现一个固定深度的树结构，即当向leef节点添加子节点时，整个树结构应该“向上移动”。这也意味着可以同时存在几个根。请参阅下面的示例： 在此示例中，在迭代1中添加绿色节点，删除顶部节点（灰色）并在K = 0和Iteration 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]