Array-Implementierung des binären Suchbaums

Question

Ich erstelle einen binären Suchbaum mit einem 1D-Array. Mein Problem ist mit der Einfügefunktion.

Das Einfügen von 5, 8, 3, 1, 4 und 9 ergibt den richtigen Index, wenn ich den Baum ausgabe. Wenn ich jedoch versuche, Zahlen nach 9 in den Baum einzufügen, ist der Index falsch. Zum Beispiel, mit den vorherigen Zahlen erwähnt, hat 9 einen Index von 7. Wenn ich 17, die 9 rechten Kind sein, anstelle von seinem Index bei 15, ist es Index 11.

Ich weiß, dass das Problem ist mit, wie ich i inkrementieren, aber ich bin mir nicht sicher, wie man es repariert. Jede Hilfe wird geschätzt. Vielen Dank!

void insert(int x)    
    { 
    int i = 1; //Counter 

    if (ptr->arr[1] == -1) //If bst is empty. 
    { 
     ptr->arr[1] = x; 
    } 
    else      
    { 
     int *temp = &ptr->arr[1]; //Temp starts at root 
     int *parent = NULL; 
     while (*temp != -1 && *temp != x) 
     { 
      if (x < *temp) 
      { 
       parent = temp; 
       temp = &ptr->arr[i*2]; 
       i++; 
      } 

      else 
      { 
       parent = temp; 
       temp = &ptr->arr[i*2+1]; 
       i+=2; 
      } 

     } 

     *temp = x; 

    } 

Answer 1

Du Aufrechterhaltung des aktuellen Knotens in zwei verschiedenen Variablen: einen Zeiger auf den Knoten in temp und der Index des Knotens ist in i gehalten gehalten wird. Dies alleine - obwohl wahrscheinlich nicht optimal - ist kein Problem. Sie halten die beiden Variablen jedoch nicht konsistent (Sie aktualisieren den Zeiger anders als den Index). Eine einfache Lösung wäre, diese konsistent zu machen:

temp = &ptr->arr[i*2]; //the pointer update is correct 
i = i * 2; //same update as above 
//... 
temp = &ptr->arr[i*2+1]; 
i = i * 2 + 1; //same update as above 

Meiner Meinung nach ist es auch eine gute Idee, um den Zeiger temp vollständig und immer Zugriff auf das Array durch seinen Index fallen. Dies würde keine Synchronisation zwischen zwei Variablen erfordern.