Stockage de la traversée BinarySearchTree inOrder dans un tableau

Question

J'ai référé au lien suivant pour voir comment la traversée inOrder peut être enregistrée dans un tableau Binary Search Tree to inOrder Array.

Mon arbre:

 100 
    /\ 
    50 300 
/\ 
    20 70 

Lorsque premier élément (20) est inséré dans la valeur d'index de tableau est incrémenté de 1. Maintenant, quand la commande passe à la récupération de la prochaine valeur d'index noeud (50) devient 0.

Code

:

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); 
} 

sortie prévue dans le tableau: 20 50 70 100 300
je veux dire que la sortie 100 300 0 0 0

Answer 1

Vous pouvez modifier la fonction pour retourner le dernier index utilisé, puis mettre à jour en fonction du nouvel index.

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; 
} 

La fonction wrapper est pas nécessaire, mais puisque vous toujours passer de 0 à storeInOrderRecursive ce qui rend l'API similaire et la valeur de retour peut encore être void pour les appels à storeInOrder.

Answer 2

L'idée de mettre la logique dans le code de visite est correcte, mais vous avez besoin d'un index global. Dans votre implémentation, l'index que vous modifiez est transmis par valeur, ce qui n'aboutit pas au comportement souhaité, car seules les copies locales de la valeur sont modifiées. Une formulation en Java pourrait ressembler à ceci.

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); 
    } 
} 

Ou bien, sous une forme plus contractée plus proche de la question d'origine. Si l'implémentation doit être aussi proche que possible de la version d'origine, la version suivante peut être utilisée. Il utilise une classe wrapper pour int en remplacement de l'appel par référence, car Java n'autorise pas l'appel par référence pour les types de données élémentaires.

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); 
}