Учитывая обратный порядок, как преобразовать в предварительный порядок?в полном бинарном дереве

Question

Учитывая прохождение по заказу, как я могу преобразовать его в обход по предварительному заказу? Предположим, что данное дерево является полным двоичным деревом .

Пример:

Вход: в порядке: {d, b, e, a, f, c, g}

Выход: предварительный заказ: {a, b, d, e, c, f, g}

Answer 1

Если вы имеете дело с полным двоичным деревом, то ваш массив всегда содержит 2^n - 1 элементов.

Если предположить, легко заметить, что корень в порядке обхода всегда будет иметь индекс (arrayLen / 2) - 1.Отсюда вы можете использовать рекурсивный метод с обеих сторон массива.

Вот решение в PHP (может быть преобразовано в любой язык):

function getPreOrder($arr) {
        $num = count($arr) - 1;
        if ($num == 0) // if only 1 element return it
                return $arr;
        $pre = array();
        $pre[]= $arr[$num / 2]; // first is the root (pre-oreder definition)
        $pre = array_merge($pre, getPreOrder(array_slice($arr, 0, $num / 2 ))); //take the left side
        $pre = array_merge($pre, getPreOrder(array_slice ($arr, $num / 2 + 1))); // take the right side
        return $pre;
}

echo implode(",", getPreOrder(array("d", "b", "e", "a", "f", "c", "g")));

Это выведет вас: a,b,d,e,c,f,g.

Надеюсь, что поможет!