Перенесение узлов в бинарном дереве
Есть бинарное дерево, построенное из отсортированного списка. По условию задачи в дереве происходит смена узлов местами, и вместе с узлами, меняются местами и их потомки.
На вход дается список:
tree = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Затем из списка строится дерево:
Затем происходит замена узлов 5 и 2 местами, причем замена происходит вместе с потомками узлов, и дерево должно выглядить так:
Затем дерево переносится в список, и список должен выглядеть так:
tree = [1, 5, 3, 10, 2, 6, 7, 4, 8, 9]
Каким образом реализовать функцию, которая будет переносить узлы дерева вместе с потомками?
Ответы (2 шт):
решение по ссылке из комментариев конечно интересное, но сразу три рекурсивные функции выглядят сложно, есть способ попроще:
tree = []
q = [root] # root - корневой узел, в нашем случае - 1
while q:
for _ in range(len(q)):
cur = q.pop(0)
tree.append(cur.value)
if cur.left: q.append(cur.left)
if cur.right: q.append(cur.right)
>>> tree # [1, 5, 3, 10, 2, 6, 7, 4, 8, 9]
Проверить, не является ли один из узлов потомком другого. Если да, то сначала отсоединить дерево потомка от его родителя, затем второй узел от его родителя. Если такой зависимости нет, то отсоединять в любом порядке.
Теперь присоединить первый узел на место второго и наоборот.
О существенном: описание дерева по уровням не даёт однозначной информации о его структуре, это прокатывает только для полного бинарного дерева (как на первой картинке, все уровни заполнены, кроме, возможно, последнего)