Insérer une nouvelle valeur dans un arbre python

Question

J'ai un arbre comme:

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

Les nombres représentent la racine de chaque nœud, les none représentent les enfants qui n'ont pas de valeur.

Par exemple, la racine principale est 4 et [[Aucun, 1, Aucun], 2, [Aucun, 3, Aucun]] est le sous-arbre sur la gauche et ceci [Aucun, 6, [Aucun, 7, Aucun]] est-il sous-arbre à droite. La racine principale du sous-arbre à gauche est 2 etc etc ...

Et mon problème est que je veux insérer une valeur dans cet arbre.

Par exemple je veux ajouter la valeur 5, c'est ce que je veux:

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

Ma fonction prend deux arguments, l'arbre et l'entier à ajouter, j'ai besoin d'utiliser la fonction récursive, par exemple voici ce que j'ai commencé:

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

Merci d'avance

Answer 1

Puisque vous avez mentionné la récursivité, voici une solution utilisant la récursivité:

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)

Tester la solution:

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 fonction parcourt l'arbre de manière récursive jusqu'à atteindre le bon endroit pour insérer le nœud. Puisqu'il s'agit d'un arbre de recherche binaire, nous devons nous assurer que tout enfant à gauche d'un nœud doit être inférieur à ce nœud, et tout enfant à droite doit être supérieur. C'est pourquoi nous allons gauche / droite en fonction de la comparaison du nouveau nœud avec la racine actuelle du parcours.