Insira um novo valor em uma árvore python

Question

Eu tenho uma árvore como:

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

Os números representam a raiz de cada nó, o none representa os filhos que não têm valor.

Por exemplo, a raiz principal é 4 e [[Nenhum, 1, Nenhum], 2, [Nenhum, 3, Nenhum]] é a subárvore à esquerda e esta [Nenhum, 6, [Nenhum, 7, Nenhum]] ele está subárvore à direita. A raiz principal na subárvore à esquerda é 2 etc etc ...

E o meu problema é que quero inserir um valor nesta árvore.

Por exemplo, eu quero adicionar o valor 5, é isso que eu quero:

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

Minha função leva dois argumentos, a árvore e o inteiro para adicionar, eu preciso usar a função recursiva, por exemplo, isto é o que eu comecei:

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

desde já, obrigado

Answer 1

Como você mencionou a recursão, aqui está uma solução usando recursão:

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)

Testando a solução:

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)

A função percorre a árvore recursivamente até chegar ao local correto para inserir o nó. Como é uma árvore de busca binária, devemos garantir que qualquer filho à esquerda de um nó seja menor que esse nó e que qualquer filho à direita seja maior. É por isso que vamos para a esquerda / direita de acordo com a comparação do novo nó com a raiz atual da travessia.