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

Question

Как можно преобразовать дерево на основе массива в заказ? Массив содержит:

Приветствия

public void preOrder(int index) {

    if (index >= currSize) {
        return;
    }

    System.out.println(items[index]);
    preOrder(2 ^ index + 1); //left
    preOrder((2 ^ index) + 2); //right
}

Answer 1

При обходе предварительного заказа сначала вы обрабатываете родительский объект, а затем рекурсивно обрабатываете левое поддерево и правое поддерево.Представление, которое у вас есть, в основном такое же, как у кучи, поэтому ясно, что является левым и правым потомками любого узла.Это означает, что мы можем пройти это в предзаказе и распечатать узлы в том порядке, в котором мы их посещаем.

Псевдокод будет выглядеть следующим образом:

print_pre_order(index):
  if index is beyond the size of the array:
    return
  else:
    print value at index
    print_pre_order(left child of index)
    print_pre_order(right child of index)

Поскольку это организовано каккучи, для каждого индекса n у левого ребенка 2 * n, а у правого ребенка 2 * (n + 1).Обратите внимание, что я предполагаю, что индексы массива начинаются с 1 (хотя у большинства языков они начинаются с 0), но вы можете легко адаптировать его для массивов на основе 0.

Answer 2

Должно быть похоже на следующее.

public void preOrder(int index) {

    if (index >= currSize) {
        return;
    }
    System.out.println(items[index]);
    preOrder((2 * index)+1);
    preOrder((2 * index)+2);
 }