Блог

У меня есть дерево, подобное:

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

Числа представляют корень каждого узла, none представляют дочерние элементы, которые не имеют значения.

Например, главный корень равен 4, а [[None,1,None],2,[None,3,None]] — это поддерево слева, а это [None,6,[None, 7,None]] — это поддерево справа. Главный корень в поддереве слева равен 2 и т.д. и т.д…

И моя проблема в том, что я хочу вставить значение в это дерево.

Например, я хочу добавить значение 5, это то, что я хочу:

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

Моя функция принимает два аргумента, дерево и целое число для добавления, мне нужно использовать рекурсивную функцию, например, это то, что я начал:

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

Заранее спасибо

Поскольку вы упомянули рекурсию, вот решение с использованием рекурсии:

 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)
 

Тестирование решения:

 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)
 

Функция рекурсивно проходит по дереву, пока не достигнет нужного места для вставки узла. Поскольку это двоичное дерево поиска, мы должны обеспечить условие, что любой дочерний элемент слева от узла должен быть меньше этого узла, а любой дочерний элемент справа должен быть больше. Вот почему мы идем влево / вправо в соответствии с сравнением нового узла с текущим корнем обхода.

Это можно сделать, выполнив обход дерева, чтобы найти целевой узел и заменить его элемент желаемым значением.

 # Do an in-order traversal recursively
def in_order(tree):
    if tree is None:
        return
    for element in in_order(tree[0]):
        yield element
    yield tree
    for element in in_order((tree[2])):
        yield element

# helper method to create a new node
def new_node(val):
    return [None, val, None]

if __name__ == '__main__':
    tree = [[[None, 1, None], 2, [None, 3, None]], 4, [None, 6, [None, 7, None]]]
    print(tree)
    # Search for the target node with the value 6 and create a new node as its left child 
    for element in in_order(tree):
        if element[1] == 6:
            element[0] = new_node(5)
    print(tree)
 

Поскольку обход дерева является универсальным способом доступа ко всем узлам дерева, его можно изменить, чтобы найти другие узлы.
Например:

 # Finding leaf nodes
for element in in_order(tree):
    if element[0] is None and element[2] is None:
        # Do something
        pass
 

Также применимы обход по предварительному заказу и после заказа.