Дерево вставок

Question

Не являются ли правильными функции вставки дерева на сайте Python

Вставить слева:

def insertLeft(root,newBranch):
    t = root.pop(1)
    if len(t) > 1:
        root.insert(1,[newBranch,t,[]])
    else:
        root.insert(1,[newBranch, [], []])
    return root

Я обнаружил, что логика неверна, вставка ведет к сломанному дереву.

Я попробовал ниже (вы можете запустить код на той же странице) и увидеть подтверждение.

r = BinaryTree(3)
insertLeft(r,4)
insertLeft(r,5)
insertLeft(r, [10, [11, [],[]], []])
insertRight(r,6)
insertRight(r,7)
print(r)

Выход:

[3, 
    [
        [10, [11, [], []], []], 
            [5, [4, [], []], []], 
            []
    ], 
    [
        7, 
            [], 
            [6, [], []]
    ]
]

Answer 1

Результат соответствует назначению этих функций. Следующие:

insertLeft(r, [10, [11, [],[]], []])

... вставляет значение как левый потомок корня. Значение, которое будет дано этому новому узлу, - это то, что вы указали в качестве второго аргумента. Эта функция всегда создает один новый узел (триплет), и вы дали ему значение древовидной структуры.

Это выглядит странно на выходе, и выглядит так, как будто структура была повреждена, но это не так. Значение [10, [11, [],[]], []] это просто значение, и оно не участвует в структурировании основного дерева.

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

insertLeft(r, 11)
insertLeft(r, 10)

... а затем предыдущее поддерево ([5, [4, [], []], []]) станет дочерним узлом со значением 11.

Короче говоря, чтобы объединить поддеревья, вы не можете просто передать одно поддерево в качестве аргумента insertLeft, Метод предназначен только для ввода отдельных узлов с одним конкретным значением.