Блог

Как можно реализовать BST без структур классов, но в виде списка списков? Я не смог найти такую реализацию, поэтому попробовал сам:

 numbers = [7, 2, 13, 0, 10, 15, 4, 1, 3, 8]
tree = []

for num in numbers:
    tree.append( [num, 0, 0] )

for num in numbers[1:]:
    for l in tree:
        if num != l[0]:
            if num > l[0]:
                if l[2] == 0:
                    l[2] = numbers.index(num)
                    break
            else:
                if l[1] == 0:
                    l[1] = numbers.index(num)
                    break
 

В дереве есть один список для каждого элемента.

• tree[i][0] будет значением узла.
• tree[i][1], tree[i][2] будет индексом для левого и правого узла узла at i .

Это, к сожалению, не работает (без ошибок). В приведенном выше примере это выглядело бы так (корень находится слева):

 # [7, 2, 13, 0, 10, 15, 4, 1, 3, 8]
#
#          15
#         /  
#        /    8
#      13
#     /  
#    /    4
#   /
#  7
#          10
#         /  
#        /    3
#       /
#       2
#           1
#          /
#          0
 

Как вы можете видеть, 10 он стал левым ребенком 2 , в то время как должен был быть правым ребенком 13 .

Если я правильно понимаю, вы хотите, чтобы дерево представляло собой список триплетов, где каждый триплет представляет собой узел дерева, состоящий из [значение, слева, справа], где слева и справа-индексы в общем списке, ссылающиеся на соответствующий дочерний узел, или 0.

Проблема в вашем коде заключается в том, что вы на самом деле не проходите по дереву вдоль этих отношений между родителями и детьми. Вместо этого вы просто повторяете его слева направо с for l in tree помощью . Вместо этого вы должны сделать l = tree[l[1]] или l = tree[l[2]] перейти от родительского узла к дочернему.

Во-вторых, этого никогда не должно произойти num == l[0] (за исключением самого корня, который ваш код все равно пропускает), так как это означало бы, что номер уже был связан с родительским узлом, и у вас есть дубликат. Если это произойдет, дубликат следует проигнорировать, и вы должны выйти из цикла.

Итак, вот исправление вашего основного цикла:

 for i, num in enumerate(numbers):
    l = tree[0]
    while num != l[0]:
        if num > l[0]:
            if l[2] == 0:
                l[2] = i
                break
            l = tree[l[2]]  # walk down to right child
        else:
            if l[1] == 0:
                l[1] = i
                break
            l = tree[l[1]]  # walk down to left child
 

Обратите внимание, что я использовал enumerate для цикла, чтобы избежать того, что вам придется звонить index .

Я бы также предложил создать по крайней мере функции и отделить логику поиска значения в дереве от вставки значения. Кроме того, можно было бы улучшить именование:

 VALUE = 0
LEFT = 1
RIGHT = 2

def find(tree, num):
    if not tree:
        return
    node = tree[0]
    while num != node[VALUE]:
        i = node[RIGHT if num > node[VALUE] else LEFT]  # index of child
        if i == 0:  # no child in that direction
            return node
        node = tree[i]
    return node

def insert(tree, num):
    if tree:
        node = find(tree, num)
        if num == node[VALUE]:
            return
        node[RIGHT if num > node[VALUE] else LEFT] = len(tree)
    tree.append([num, 0, 0])


numbers = [7, 2, 13, 0, 10, 15, 4, 1, 3, 8]
tree = []
for num in numbers:
    insert(tree, num)
print(tree)