Masukkan nilai baru di python pohon

Question

Saya punya pohon seperti:

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

Angka-angka mewakili akar dari setiap node, tidak ada yang mewakili anak-anak yang tidak memiliki nilai.

Misalnya, akar utamanya adalah 4 dan [[None, 1, None], 2, [None, 3, None]] adalah sub pohon di sebelah kiri dan ini [None, 6, [None, 7, None]] apakah dia sub pohon di sebelah kanan. Akar utama pada sub pohon di sebelah kiri adalah 2 dst dll ...

Dan masalah saya adalah saya ingin memasukkan nilai di pohon ini.

Misalnya saya ingin menambahkan nilai 5, inilah yang saya inginkan:

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

Fungsi saya mengambil dua argumen, pohon dan bilangan bulat untuk ditambahkan, saya perlu menggunakan fungsi rekursif, misalnya inilah yang saya mulai:

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

Terima kasih sebelumnya

Answer 1

Karena Anda menyebutkan rekursi, berikut ini solusi menggunakan rekursi:

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)

Menguji solusinya:

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)

Fungsi tersebut melintasi pohon secara rekursif hingga mencapai tempat yang benar untuk memasukkan node. Karena ini adalah pohon pencarian Biner, kita harus memastikan kondisi bahwa setiap anak di sebelah kiri simpul harus lebih kecil dari simpul itu, dan anak di sebelah kanan harus lebih besar. Itulah mengapa kita pergi ke kiri / kanan sesuai dengan perbandingan node baru dengan root traversal saat ini.