Я только что столкнулся с этой проблемой и задавался вопросом, смогу ли я найти правильное решение.Проблема заключается в замене двух узлов двоичного дерева не только по значению, но и по узлу.Таким образом, это означает, что мы должны изменить правое и левое значения.
Итак, допустим, что у нас есть двоичное дерево, похожее на изображение выше.Сначала я подумал об обходе узлов по порядку, чтобы я мог сгладить дерево, а затем просто поменять местами элементы, а затем восстановить дерево из списка подкачки.Таким образом, буквально решение выглядит примерно так:
. Для вышеупомянутого дерева обход по порядку генерирует такой список:
1,3,4,6,7,8,10,13,14.
Теперь я поменяю местами 8 и 13.
=> 1,3,4,6,7,13,10,8,14
Нопроблема здесь в том, что, поскольку я теперь сплющил дерево, когда я пытаюсь восстановить, я не могу это сделать, потому что я не знаю положение отдельных узлов, например, является ли конкретный узел левым подчиненным или если он является корнем,Таким образом, в буквальном смысле дерево не может быть восстановлено так же, как это было изначально с переставленными узлами.
Теперь вопрос заключается в том, могу ли я изменить свой алгоритм обхода, чтобы он содержал информацию о положении каждого из узлов, чтобы при замене элементов и восстановлении я получал одно и то же двоичное дерево с заменой нужных узлов?Можем ли мы сохранить состояние / положение отдельных узлов при прохождении по порядку?
PS.Я признаю, что выполнение пост-заказа приведет к тому, что мой список с первым и последним узлами будет заменен, но два узла, которые нужно поменять местами, не обязательно должны быть в корне и в самом правом элементе, это могут быть любые два.