Предварительно заданное двоичное дерево на основе массива

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

Должно быть следующим.

public void preOrder(int index) { 

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

Answer 2

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

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

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) 

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