Восстановить полное дерево с учетом обхода в порядке

Question

Полное двоичное дерево - это дерево, в котором все уровни заполнены, кроме последнего, в котором мы начинаем заполнение слева. Существует ли какая-либо рекурсивная процедура для восстановления полного дерева с учетом обхода в порядке?

Редактировать: до сих пор я пришел к выводу

if (nr_nodes - (2^nr_complete_levels - 1) <= 2^(nr_complete_levels - 1))
  then root_index is nr_nodes - (2^(nr_complete_levels - 1) - 1)
    else root_index is 2^nr_complete_levels

Теперь эта идея может быть применена рекурсивно, как предложено. Я что-то упустил?

Answer 1

Я думаю, что определенно есть способ рекурсивного решения этой проблемы. Поскольку это полное дерево, то каждое поддерево в этом дереве является полным деревом. И поскольку это полное дерево, вы можете знать точную структуру дерева, и зная это, вы сможете узнать индексы корней поддеревьев в массиве. И тогда подзадачи становятся реконструкцией левого поддерева и правого поддерева. По сути, вы могли бы иметь указатель, инициализированный в 0-ую позицию индекса массива, и обходить массив, используя этот указатель, и в то же время строить дерево. Когда этот глобальный указатель указывает на корневой индекс, создайте корень, подключите его левый указатель к построенному левому поддереву, увеличьте указатель, рекурсивно вызовите эту функцию для построения правого поддерева и подключите его правый указатель к построенному правому поддереву.