Хранение BinarySearchTree inOrder traversal в массиве

Question

Я ссылался на следующую ссылку, чтобы увидеть, как обход inOrder можно сохранить в массив Binary Search Tree to inOrder Array.

Мое дерево:

 100 
    /\ 
    50 300 
/\ 
    20 70 

Когда первый элемент (20) вставляется в значение индекса массива увеличивается на 1. Теперь, когда управление переходит к выборки следующего узла (50) значение индекса становится 0.

код:

storeInOrder(root1,arr1,0); 

private static void storeInOrder(Node root1, int[] arr1, int index) {  
    if(root1 == null){return;} 

    storeInOrder(root1.left, arr1,index);  
    arr1[index++] = root1.data; 
    storeInOrder(root1.right,arr1,index); 
} 

Ожидаемый результат в массиве: 20 50 70 100 300
Я получаю выход как 100 300 0 0 0

Answer 1

Вы можете изменить функцию, чтобы вернуть последний использованный индекс, а затем обновить его на основе нового индекса.

storeInOrder(root1,arr1); 

private static void storeInOrder(Node root1, int[] arr1) { 
    storeInOrderRecursive(root1,arr1,0); 
} 

private static Integer storeInOrderRecursive(Node root1, int[] arr1, int index) {  
    if(root1 == null){return index;} 

    index = storeInOrderRecursive(root1.left, arr1,index);  
    arr1[index++] = root1.data; 
    storeInOrderRecursive(root1.right,arr1,index); 

    return index; 
} 

Функция обертка не обязательно, но так как вы всегда проходит в 0, чтобы storeInOrderRecursive это делает API аналогично, а затем возвращаемое значение по-прежнему может быть void для звонков storeInOrder.

Answer 2

Идея поместить логику в код посещения верна, но вам нужен глобальный индекс. В вашей реализации индекс, который вы изменяете, передается по значению, что не приводит к желаемому поведению, так как изменяются только локальные копии значения. Формула на Java может выглядеть следующим образом.

int[] iArray; // initialize with the desired size 
int GlobalIndex = 0; 

void Visit(Node iNode) 
{ 
    iArray[GlobalIndex++] = iNode.Data; 
} 

void StoreInOrder(Node iRoot) 
{  
    if(null != iRoot) 
    { 
     StoreInOrder(iRoot.Left);  
     Visit(iRoot); 
     StoreInOrder(iRoot.Right); 
    } 
} 

Или альтернативно, в более сжатой форме ближе к исходному вопросу.

int[] iArray; // initialize with the desired size 
int GlobalIndex = 0; 

void StoreInOrder(Node iRoot) 
{  
    if(null != iRoot) 
    { 
     StoreInOrder(iRoot.Left); 
     iArray[GlobalIndex++] = iNode.Data; 
     StoreInOrder(iRoot.Right); 
    } 
} 

Если реализация должна быть как можно ближе к исходной версии, может использоваться следующая версия. Он использует класс-оболочку для int в качестве замены для вызова по ссылке, поскольку Java не разрешает вызов по ссылке для элементарных типов данных.

class IntWrapper 
{ 
    public int Value; 
    public IntWrapper(int InitialValue) 
    { 
     Value = InitialValue; 
    } 
} 

int[] iArray; 

StoreInOrder(iRoot, iArray, new IntWrapper()) 

void StoreInOrder(Node iRoot, int[] iArray, IntWrapper Index) 
{ 
    StoreInOrder(iRoot.Left,iArray,Index); 
    iArray[Index.Value++] = iNode.Data; 
    StoreInOrder(iRoot.Right,iArray,Index); 
}