Arreglar árbol de profundidad en Python

Question

Quiero implementar una estructura de árbol que tenga una profundidad fija, es decir, al agregar elementos secundarios a los nodos de leef, toda la estructura de árbol debe "moverse hacia arriba". Esto también significa que varias raíces pueden existir simultáneamente. Vea el ejemplo debajo: En este ejemplo, los nodos verdes se agregan en la iteración 1, eliminando el nodo superior (gris) y haciendo que los dos nodos azules en K = 0 e Iteración 1 nodos raíz.

¿Cómo hago para implementar esto?

Answer 1

Almacenar cada nodo con una referencia a su elemento principal. Cuando agregue un nodo como un niño, recorra los padres (desde el nodo que se agrega) y elimine el tercero después de establecer la referencia principal en todos sus elementos secundarios en None. A continuación, agregue los elementos secundarios del nodo eliminado a su lista de árboles.

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]