Insertar un nuevo valor en un árbol python

Question

Tengo un árbol como:

tree = [[[None,1,None],2,[None,3,None]],4,[None,6,[None,7,None]]]

Los números representan la raíz de cada nodo, ninguno representa a los hijos que no tienen valor.

Por ejemplo, la raíz principal es 4 y [[None, 1, None], 2, [None, 3, None]] es el subárbol a la izquierda y este [None, 6, [None, 7, None]] ¿Es el subárbol de la derecha? La raíz principal en el subárbol de la izquierda es 2, etc., etc.

Y mi problema es que quiero insertar un valor en este árbol.

Por ejemplo, quiero agregar el valor 5, esto es lo que quiero:

tree = [[[None, 1, None], 2, [None, 3, None]], 4, [[None, 5, None], 6, [None, 7, None]]]

Mi función toma dos argumentos, el árbol y el entero para agregar, necesito usar la función recursiva, por ejemplo, esto es lo que comencé:

def insert(tree,int):
    cur = tree
    prev = None
    while cur != None:
        prev = cur
        if int < cur[1]:
            cur = cur[0]
        else :
            cur = cur[2]

Gracias por adelantado

Answer 1

Como mencionaste la recursividad, aquí tienes una solución que usa la recursividad:

def insert_node(root, node):
    if root == [None]:  #corner case of an empty tree
        root.append(node)
        root.append(None)   #now root will be : [None, node, None]
        return
    if node <= root[1]:  #we need to go left
        if root[0] == None:
            root[0] = [None, node, None]
            return
        else:
            insert_node(root[0], node)
    else:               #we need to go right
        if root[2] == None:
            root[2] = [None, node, None]
            return
        else:
            insert_node(root[2], node)

Probando la solución:

tree = [None]   #starting with an empty tree
insert_node(tree, 4)
insert_node(tree, 2)
insert_node(tree, 1)
insert_node(tree, 3)
insert_node(tree, 6)
insert_node(tree, 7)
print(tree)

La función recorre el árbol de forma recursiva hasta llegar al lugar correcto para insertar el nodo. Dado que es un árbol de búsqueda binario, debemos asegurarnos de que cualquier hijo a la izquierda de un nodo sea menor que ese nodo y cualquier hijo a la derecha sea mayor. Es por eso que vamos a la izquierda / derecha de acuerdo con la comparación del nuevo nodo con la raíz actual del recorrido.