Invoegfunctie in een willekeurige binaire boom

Ik heb een probleem met mijn invoegfunctie in deze binaire structuur in C ++. De knooppunten zijn correct geplaatst totdat ik opnieuw een knooppunt aan de rechterkant of aan de linkerkant moet toevoegen. De functie denkt dat ik links noch rechts geen knooppunten heb, omdat ik op die plaatsen al knooppunten heb ingevoegd.

Hier is mijn code:

void insert(string data)
{    
    srand(time(NULL));
    int r;
    node *aux=head;
    node *n=new node(data);
    if (head==NULL)
    {
        head =n;
        return;
    }

    while (aux!=NULL)
    { 
        r=rand()%100;
        if (r>50)
        {
            cout<<"\nRandom is "<right;  
        }
        else
        {   
            cout<<"\nRandom is "<left;
            if (aux!=NULL)
            {
                cout<getdata()<getdata()<
0
Welkom bij Stack Overflow! Vreemdelingen vragen om fouten in uw code te herkennen door inspectie is niet productief. U moet het probleem identificeren (of op zijn minst isoleren) door een foutopsporingsprogramma te gebruiken en vervolgens terugkomen met een meer specifieke vraag (nadat u het hebt beperkt tot een 10-regelige testcase ).
toegevoegd de auteur Oliver Charlesworth, de bron
het probleem zit niet in de code, het compileert, het probleem zit in de invoeging Ik kan niet achterhalen hoe ik het kan maken om te ontdekken waarom wanneer ik een 4e knooppunt moet toevoegen, weet het niet dat de eerste rechts en links knooppunten zijn al in gebruik.
toegevoegd de auteur elenfermodelcpp, de bron

1 antwoord

Hier is een kleine wijziging van uw code:

void insert(string data)
      {    srand(time(NULL));
           int r;
           node *aux=head;
           node *n=new node(data);
           if(head==NULL){
                          head =n;
                          return;
                          }

       while(aux!=NULL)//We could put while(true) here.
       { 
                       r=rand();//Modulo is a somehow slow operation
                       if((r  & 1 )== 0)//This is much faster. It checks if r is even
                       {  cout<<"\nRandom is "<right == NULL)//We found an empty spot, use it and break
                          {
                              aux->right = n; break;
                          }
                          else//else move to the right child and continue
                          {
                              aux=aux->right;  
                              cout<getdata()<left == NULL)//We found an empty spot, use it and break
                          {
                              aux->left = n; break;
                          }
                          else//else move to the left child and continue
                          {
                              aux=aux->left;  
                              cout<getdata()<getdata()<

De belangrijkste reden is dat je aux gebruikt. Hier is een voorbeeld waarvan ik hoop dat het u zal helpen uw fout te identificeren:

node * aux = head;//suppose head doesn't have any child node
node * n = new node(data);

aux = aux->left;//Set aux to point on the left child of head
aux = n;//Set aux to point on n

cout << aux == NULL?"Aux is null":"Aux is not null" << endl;
cout << head->left == NULL?"Left is null":"Left is not null" << endl;

Deze code moet terugkeren:

Aux is not null
Left is null

De reden is dat toen we n aan aux hebben toegewezen, we alleen aux hebben aangegeven om te wijzen op n in plaats van te wijzen op het linkerknooppunt. We hebben n niet toegewezen om het linker kind van het hoofd te zijn.

U kunt dit probleem ook oplossen door aux te laten aanduiden als een aanwijzer van een knooppunt.

node * * aux = &head;
2
toegevoegd
Blij dat het was :) Graag gedaan
toegevoegd de auteur Samy Arous, de bron
Bedankt man Ik heb zojuist gebruikt wat je hebt gepost en het loste mijn probleem volledig op! Ja je had gelijk, ik misbruikte de aux, maar ik heb mijn les nu geleerd. Nogmaals bedankt.
toegevoegd de auteur elenfermodelcpp, de bron