Arbre de recherche binaire Array Imp. C++

Question

J'ai juste des problèmes avec l'insertion dans le tableau ... Et ayant les enfants bifurquent de la racine, ou "parent".

J'ai essayé d'insérer des données dans une implémentation basée sur un tableau d'un BST:

BST::BST(int capacity) : items(new item[capacity]), size(0) 
{ 
    // define the constructor to the BST Class. 
} 

void BST::insert (const data& aData) 
{ 
    if (items[root].empty) // make the first data the root. 
    { 
     items[root].theData = aData; 
     items[root].empty = false; 
     size++; 
    } 
    else if (items[root].theData.getName() < aData) 
    { 
     items[leftChild].theData = aData; // will be overwritten... 
     this->insert(aData); 
    } 
    else if (aData < items[root].theData.getName()) 
    { 
     items[rightChild].theData = aData; 
     this->insert(aData); 
    } 
} 

Quelques petites choses ne vont pas avec ceci. Permettez-moi de commencer en disant que les premières données entrantes seront la racine. Toutes les autres données seront comparées à celle-ci. Quand je fais les appels récursifs à "insérer" c'est essentiellement comment je "pense" je suis "traversant" (si c'était une liste liée). Le principal problème pour moi est de savoir que mes enfants gauche et droit seront écrasés. Je me demande comment je peux continuer à partir des "nœuds" de l'enfant ...?

Voici mon fichier d'en-tête pour la classe BST, je suis également préoccupé si j'ai mis les membres à droite et tout ..?

class BST 
{ 
public: 
    BST(int capacity = 5); 
    BST(const BST& aTable); 

    void insert(const data& aData); 
     .... 
private: 
    int size; // size of the ever growing/expanding tree :) 

    struct item 
    { 
     bool empty; 
     data theData; 
    }; 

    item * items; // The tree array 
    int rightChild; // access to the RHS 
    int leftChild; // access to the LHS 
    int root; // index to the root 
}; 

J'ai un autre fichier source, "data" auquel j'appelle les appels, "getname". Trois méthodes simples que j'ai définies à ce jour sont la surcharge de l'opérateur d'affectation, comparaison « < » surcharge et le cteur à la classe de données:

data::data(char const * const name) : name(new char[strlen(name)+1]) 
{ 
    if (name) 
    { 
     strcpy(this->name , name); 
    } 
    else this->name = NULL; 
} 

data& data::operator=(const data& data2) 
{ 
    if (this != &data2) // check for selfassignment 
    { 
     delete [] name; 
     name = NULL; 

     this->name = new char[strlen(data2.name)+1]; 
     strcpy(this->name , data2.name); 
    } 
    return *this; 
    } 

bool operator< (const data& d1, const data& d2) 
{ 
    if (strcmp(d1.getName(), d2.getName()) == -1) 
    { 
     return false; 
    } 
    else if (strcmp(d1.getName(), d2.getName()) == 1) 
    { 
     return true; 
    } 
    return false; // if they are equal return false 
}  

Answer 1

Je vois quelques problèmes. leftChild et rightChild doivent être membres de l'objet struct, pas de BST, car ils sont différents pour chaque élément (ou ils ne doivent pas exister en tant que champs et être calculés dynamiquement). Je ne vois pas de code qui fixe leftChild et rightChild à quoi que ce soit. Il semble que vous essayez de définir récursivement insert. Vous devez probablement définir une fonction d'insertion d'insertion qui prend à la fois un élément et un index du point d'insertion. Cela devrait vous mettre sur la bonne voie. Le wikipedia article a plus de pseudocode que vous pouvez regarder.