PDA

Visualizza la versione completa : C++ metodo inserisci per alberi binari di ricerca


pietrol83
03-04-2012, 14:10
ciao a tutti, ho implementato il metodo inserisci, il quale inserisce un nuovo nodo come foglia in un albero binario di ricerca. il metodo diviso in 2 fasi: la prima quella di ricerca del padre a cui agganciare il nuovo nodo, la seconda quella di inserimento del nodo figlio.

ho notato che il metodo non aggancia i nodi figli al posto giusto. posto il codice del metodo:

metodo void inserisci(nodo node)


template<class tipoelem>
void bstreep<tipoelem>::inserisci(typename bstreep<tipoelem>::nodo node)
{
if(this->binalberovuoto())
this->insbinradice(node);
else
{
if(!this->appartiene(node))
{
bool trovato = false;
nodo tmp = this->binradice();

while(!trovato)
{
if(node->getchiave() < tmp->getchiave())
{
if(this->sxvuoto(tmp))
trovato = true;
else
tmp = this->figliosx(tmp);
}
else
{
if(this->dxvuoto(tmp))
trovato = true;
else
tmp = this->figliodx(tmp);
}
}

if(node->getchiave() < tmp->getchiave())
{
this->insfigliosx(tmp);
this->figliosx(tmp)->setetichetta(node->getetichetta());
this->figliosx(tmp)->setchiave(node->getchiave());
cout << "A\n";
}
else
{
this->insfigliodx(tmp);
this->figliodx(tmp)->setetichetta(node->getetichetta());
this->figliodx(tmp)->setchiave(node->getchiave());
cout << "B\n";
}
}
}
}

nella prova ho fatto, tramite un ciclo while, l'inserimento dei seguenti nodi:



chiave valore
7 10
2 5
8 15
1 7
3 6
20 4


subito dopo il ciclo per inserire i dati ho invocato il metodo min, che restituisce il valore del nodo con la chiave pi piccola, e mi d come risultato il valore 4 anzich 7.
premesso che secondo me il metodo inserisci fatto bene, ho notato che nella parte di inserimento del nodo come figlio viene sempre esegueto il blocco else, a prescindere che la chiave del nodo da inserire sia minore o maggiore di quella del nodo in esame (tmp). perch?

pietrol83
03-04-2012, 14:59
dopo l'inserimento del nodo come figlio, ho messo un'istruzione che mi visualizza il valore della radice e al posto di visualizzare il valore del primo nodo inserito, viene visualizzato quello dell'ultimo nodo che viene inserito, in pratica per ogni inserimento di un nuovo nodo viene sovrascritta la radice dell'albero. ho controllato anche i metodi insfigliosx e insfigliodx e anche quelli sembrano fatti correttamente. sto impazzendo.

main.cpp


#include "bstreep.h"

#include<iostream>
#include<stdlib.h>

using namespace std;

int main()
{
bstreep<int> T;
cout << "bstreevuoto() = " << T.binalberovuoto() << "\n\n";


int value = 0;
int key = 0;
alberobinp<int>::nodo n = new nodoalberop<int>;
cin >> key;
while(key != -1)
{
cin >> value;
cout << "\n";
n = new nodoalberop<int>;
n->setetichetta(value);
n->setchiave(key);
T.inserisci(n);
cout << T.legginodo(T.binradice());
delete n;
cin >> key;
}
cout << "min = " << T.min() << "\n\n";
cout << T.legginodo(T.binradice());

system("pause");
return 0;
}

Loading