Wstaw nową wartość w drzewie Pythona

Question

Mam drzewo takie jak:

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

Liczby reprezentują rdzeń każdego węzła, a none reprezentują dzieci, które nie mają wartości.

Na przykład główny katalog główny to 4, a [[None, 1, None], 2, [None, 3, None]] to poddrzewo po lewej stronie, a to [None, 6, [None, 7, None]] jest poddrzewem po prawej stronie. Główny katalog główny w poddrzewie po lewej stronie to 2 itd. Itd.

Mój problem polega na tym, że chcę wstawić wartość do tego drzewa.

Na przykład chcę dodać wartość 5, to jest to, czego chcę:

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

Moja funkcja przyjmuje dwa argumenty, drzewo i liczbę całkowitą do dodania, muszę użyć funkcji rekurencyjnej, na przykład zacząłem od tego:

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

Z góry dziękuję

Answer 1

Ponieważ wspomniałeś o rekursji, oto rozwiązanie wykorzystujące rekursję:

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)

Testowanie rozwiązania:

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)

Funkcja przechodzi przez drzewo rekurencyjnie, aż osiągnie właściwe miejsce do wstawienia węzła. Ponieważ jest to drzewo wyszukiwania binarnego, musimy upewnić się, że każde dziecko po lewej stronie węzła powinno być mniejsze niż ten węzeł, a każde dziecko po prawej stronie powinno być większe. Dlatego przechodzimy w lewo / w prawo zgodnie z porównaniem nowego węzła z bieżącym korzeniem przejścia.