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

Имея двоичное дерево (Bt), преобразуйте его в двусвязный список (DLL). Левый и правый указатели в узлах должны использоваться как предыдущий и следующий указатели соответственно в преобразованной DLL. Порядок узлов в DLL должен быть таким же, как в Inorder для данного двоичного дерева. Первый узел обхода Inorder (крайний левый узел в BT) должен быть головным узлом DLL.

Я столкнулся с этим вопросом во время одного из своих интервью. Аналогичная проблема обсуждалась в этом посте.

Проблема здесь проще, так как нам нужно создавать не циклическую DLL, а простую DLL. Идея ее решения довольно проста и понятна.

1. Если левое поддерево существует, обработать левое поддерево
   1. Рекурсивно преобразовать левое поддерево в DLL.
   2. Затем найдите неупорядоченный предшественник корня в левом поддереве (неупорядоченный предшественник — это самый правый узел в левом поддереве).
   3. Сделать неупорядоченный предшественник предыдущим корнем, а корень — следующим по порядку предшественником.
2. Если правое поддерево существует, обработайте правое поддерево (ниже 3 шага аналогичны левому поддереву).
   1. Рекурсивно преобразовать правое поддерево в DLL.
   2. Затем найдите неупорядоченного преемника корня в правом поддереве (чтобы преемник был крайним левым узлом в правом поддереве).
   3. Сделайте преемник по порядку следующим корнем, а корень — предыдущим преемником по порядку.
3. Найдите самый левый узел и верните его (крайний левый узел всегда является головной частью преобразованной DLL).

Ниже приведен исходный код вышеуказанного алгоритма.

Другой подход:
Алгоритм:

1. Пройдите по дереву в порядке.
2. При посещении каждого узла отслеживайте указатели начала и конца DLL, вставляйте каждый посещенный узел в конец DLL с помощью указателя хвоста.
3. Вернуть начало списка.

Ниже приведена реализация вышеуказанного подхода:

Эта статья составлена Ашишем Мангла и проверена командой GeeksforGeeks. Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсуждаемой выше.
Вам также может быть интересно увидеть Преобразование заданного двоичного дерева в двусвязный список | Установите 2 для другого простого и эффективного решения.