Arbre de recherche binaire C++ (Parents)

Question

J'ai besoin d'un peu plus d'aide sur mon BST. C'est ce que mon BST ressemble lors de l'insertion:

R, L, J, G

     R --Root at Index 0 
        /\ 
    L @ Index1  L NULL 
       /\ 
    J @ Index3 J NULL 
       /\ 
    G @ Index7 G NULL 

Voici le code qui le fait se produire.

void BST::insert(const data &aData) 
{ 
    if (items[Parent].empty) 
    { 
     items[Parent].theData = aData; // insert at leaf. 
     items[Parent].empty = false; 
     size++; 

     return; 
    }   
    for (int i = 0; i <= size; i++) 
    { 
     if (aData < items[Parent].theData) 
     { 
      if (items[2*i+1].empty) 
      { 
      items[2*i+1].theData = aData; 
      items[2*i+1].empty = false; 
      } 
      else 
          { 
      // we must already have a left child to some root. 
           Parent++; So make the previous data the root??? 
      if (items[Parent].empty) 
      { 
       items[Parent].theData = items[2*i+1].theData; 
       items[Parent].empty = false; 
       Parent = (i-1)/2; 
      } 
          } 
     } 
     else 
     { ...// do the same for data greater than but with items[2*i+2] } 

Ma question est quand aurais-je besoin de faire une nouvelle racine? Quand aurais-je besoin de faire une nouvelle racine? Pour la recomparaison?

Cette approche est-elle correcte? Merci à ceux qui même les deux à regarder mes messages :)

// Le constructeur de la classe BST et sa section privée.

BST::BST(int capacity) : items(new item[capacity]), size(0), Parent(0), 
leftChild(0), rightChild(0) 
{ 
    items->empty = true; 
    maxSize = capacity; 
} 
private: 
    int size; // size of the ever growing/expanding tree :) 
    int Parent; 
    int maxSize;  
    int leftChild; 
    int rightChild; 
    struct item 
    { 
     bool empty; 
     data theData; 
    }; 
    item *items; // The tree array 

Answer 1

Votre logique (je dois dire assez floue) semble se tromper: Quel genre de séquence « si » est-ce?

if (items[2*i+1].empty) 
{ 
} 
else if (!items[2*i+1].empty) 
{ 
    if (items[2*i+1].empty) 
    { 
     // any code here is unreachable 
    } 
} 

Answer 2

Je vous suggère de réimplémenter cela pour travailler récursivement. Quelque chose comme ceci:

void BST::insert(const data& aData, int pos) { 
    if (items[pos].empty) { 
     // insert it here 
    } 
    else (aData < items[pos].theData) { 
     // go to left child 
     insert(aData, 2*pos + 1); 
    } 
    else { 
     // go to right child 
     insert(aData, 2*pos + 2); 
    } 
} 

Ce n'est pas vraiment clair que Parent, leftChild et rightChild font dans votre classe, mais c'est une question distincte.