在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]