Bir ağaç python'a yeni bir değer ekleyin

Question

Benim gibi bir ağacım var:

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

Sayılar her bir düğümün kökünü temsil eder, hiçbiri değeri olmayan çocukları temsil eder.

Örneğin, ana kök 4'tür ve [[Yok, 1, Yok], 2, [Yok, 3, Yok]] soldaki alt ağaçtır ve bu [Yok, 6, [Yok, 7, Yok]] o sağdaki alt ağaç mı? Soldaki alt ağaçtaki ana kök 2 vb.

Ve benim sorunum, bu ağaca bir değer eklemek istemem.

Örneğin 5 değerini eklemek istiyorum, istediğim bu:

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

İşlevim iki argüman alıyor, ağaç ve eklenecek tamsayı, özyinelemeli işlevi kullanmam gerekiyor, örneğin başladığım şey bu:

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

Şimdiden teşekkürler

Answer 1

Özyinelemeden bahsettiğinizden beri, işte özyineleme kullanan bir çözüm:

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)

Çözümü test etmek:

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)

İşlev, düğümü eklemek için doğru yere ulaşıncaya kadar ağacı özyinelemeli olarak dolaşır. Bir İkili arama ağacı olduğu için, bir düğümün solundaki herhangi bir alt düğümün o düğümden daha küçük olması ve sağdaki herhangi bir alt öğenin daha büyük olması koşulunu sağlamalıyız. Bu nedenle, yeni düğümün geçişin mevcut kökü ile karşılaştırılmasına göre sola / sağa gidiyoruz.