C++ metodo inserisci per alberi binari di ricerca

[pietrol83]

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]

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;
}