[c++] Problema e chiarimento Alberi Binari di ricerca

[aleRomatre]

Salve a tutti,

Devo scrivere un metodo in c++ che : dato un albero binario di ricerca, in cui sono inseriti, come in una mappa(STL):

chiave=> Numero Identità alunno;
valore=> Alunno;

mi restituisca il numero di volte in cui compare un alunno il cui numero di identità comincia per 3;

Ho provato a scrivere questo ma non funziona (mi restituisce sempre 0) :

/**
 *  Funzione che ritorna il numero dei DNI (num. identità alunni) che cominciano per 3 (chiama a cuentaDNI3Aux).
 *
 *  @return Numero di DNI che cominciano per 3.
 */

unsigned ABB::cuentaDNI3() const
{
    return cuentaDNI3Aux(miRaiz);
}

/**
 *  Funzione ausiliare di cuentaDNI3.
 *
 *  @param raiz  Nodo radice
 *
 */

unsigned ABB::cuentaDNI3Aux(ABB::PtrNodoBin raiz) const{

    int count;

    if(raiz==NULL)
        count=0;
    else {
        if (raiz->clave[0]==3)
            count = 1 + cuentaDNI3Aux(raiz->izq) + cuentaDNI3Aux(raiz->der);
        cout << "\n";
        cout << "He encontrado " << count << " DNI que comienzan por 3" << endl;
    }
    return count;
}

è in spagnolo dunque izq => sinistra; der=>destra; miRaiz = nodo radice albero binario;

Altra cosa :

il modo di inserire il numero di DNI dovrebbe essere aleatorio... perchè invece mi calcola sempre DNI che cominiciano per 5 e maggiori?
Di seguito il metodo per la creazione dei DNI e il Main() per la prova :

classe alunno :

/**
 * Implementacion de la clase Alumno
 * Curso 2015/2016
 */

#include "alumno.h"
#include <iostream>
#include <fstream>
#include <string>
#include <cstdlib>
#include <sstream>

using namespace std;

// Nombres de ejemplo
string Alumno::list_nombre[] = {
        "Javier",
        "Jorge",
        "Angel",
        "Raul",
        "Jose",
        "Inigo",
        "Jose Antonio",
        "Julio",
        "Beatriz",
        "Ismael",
        "Oliver",
        "Carlos",
        "Alberto",
        "Francisco Manuel",
        "Lluis Carles"  };

// Apellidos de ejemplo
string Alumno::list_apellido[] = {
        "Albaladejo" ,
        "Albiach" ,
        "Aldana" ,
        "Alonso" ,
        "Anda" ,
        "Andres" ,
        "Angel" ,
        "Aranda" ,
        "Bernal" ,
        "Bonell" ,
        "Calderon" ,
        "Chakkour" ,
        "Contreras" ,
        "Correa" ,
        "Dacasa" };


/**
 * Constructor Alumno.
 * Genera un alumno con datos aleatorios excepto el curso, que se pasa como parametro.
 * @param curs curso del alumno
 */
Alumno::Alumno(unsigned curs): curso(curs)
{
    unsigned num = rand() % 100000000;
    stringstream s;
    s << num;
    string letra;
    letra.push_back( rand() % (90-65+1) + 65 ); // A 65, Z 90
    dni = s.str() + letra;
    nombre = list_nombre[ rand() % NUM_NOMBRE];
    apellidos = list_apellido[ rand() % NUM_NOMBRE];
    telefono = rand() % 100000000 + 600000000;
}

/**
 * Escribe el alumno en un stream de salida
 * @param out Stream de salida
 * @param alu alumno a escribir
 */
ostream & operator<<(ostream & out, const Alumno & alu)
{
    const string tab = "    ";
    out << "==================================" << endl;
    out << tab << "DNI: " << alu.dni << endl;
    out << tab << "Nombre: " << alu.nombre << tab << alu.apellidos << endl;;
    out << tab << "Curso: " << alu.curso;
    out << tab << "Telefono: " << alu.telefono << endl;
    out << "==================================" << endl;
    return out;
}

main() :

int main()
{
    ABB arbol;
    int i = 0;
    string dni;
    Alumno al_aux;

    for (int i=0; i<1000; i++){
        Alumno al_aux(rand());
        arbol.insertar(al_aux.getDNI(),al_aux);
    }

    arbol.inorden(cout);
    cout << endl;
}

il metodo inorden oltre a scorrere l'albero secondo una scansione inorder ... lo stampa ordinato.

[Nikopol]

Ciao,
non conosco bene la sintassi del c++ ma posso dirti che c'è un errore nell'algoritmo per il conteggio delle chiavi che iniziano con 3.
Ciò che stai facendo al momento è contare quanti nodi adiacenti, partendo dalla root, hanno la chiave che inizia per 3.
Ovvero

 if (raiz->clave[0]==3)
     count = 1 + cuentaDNI3Aux(raiz->izq) + cuentaDNI3Aux(raiz->der);

se il nodo corrente ha la chiave che inizia con 3 allora:
se i diretti figli hanno la chiave che inizia con 3 allora incremento di 1 il numero di occorrenze trovate nei figli
altrimenti interrompo la ricorsione e restiruisco solo le occorrenze trovate fino a quel momento.

Quindi se la chiave della root non inizia con 3 restituirai sempre 0.

Quello che devi fare è (in pseudocodice):

contaOccorrenze(nodo corrente)
     int count; 
     if(corrente == null){
           count = 0;
     }
     else{
           count = contaOccorrenze(figlio sinistro) + contaOccorrenze(figlio destro);
           if(chiave di corrente inizia con 3)    
               count++;
     }
     return count;

[aleRomatre]

ok grazie l'ho trovata molto utile ...

ho un altro problema : devo ricercare con il metodo count della classe map il numero di occorrenze di DNI che iniziano per 3;

ho scritto questo :

cout << "He encontrado "  << m.count("3") << " DNI que comienzan por 3." << endl;

ma naturalmente questo mi restituisce 0 in quanto cerca le chiavi esattamente uguali alla stringa "3" e non le stringhe che cominciano per 3 ... come posso fare ? grazie mille

[oregon]

Ma cosa hai scritto in

if(chiave di corrente inizia con 3)

?

[aleRomatre]

penso intenda la chiave del nodo corrente inizia per 3 ...

i problemi iniziali li ho risolti entrambi grazie anche alla risposta di Nikopol, ora mi manca solo capire come posso fare attraverso la funzione count della map STL ad ottenere il numero di DNI che iniziano per 3, in quanto per farlo ho bisogno di scansionare la chiave per fare un confronto solo sulla prima lettera.

[oregon]

penso intenda la chiave del nodo corrente inizia per 3 ...

La mia domanda era rivolta a te. Tu cosa hai scritto in quella riga effettivamente?

Nikopol ti ha suggerito la count ... non l'hai utilizzata?

[aleRomatre]

scusami oregon... non ti seguo.

Nikopol non mi ha suggerito di usare la funzione count; mi ha solo scritto in pseudocodice il metodo per ricercare il numero di occorrenze dei DNI che iniziano per 3 con la classe Albero Binario di Ricerca non STL. Il problema l'ho dunque risolto.

Ora, in un main(), sfruttando le potenzialità della classe map STL (molto simile all'implementazione di un albero), devo fare la stessa cosa.
Io ho ipotizzato di dover usare il metodo count della map... solo che non capisco come effettuare il confronto solo sulla prima lettera della chiave e non effettuare il confronto sulla chiave intera in quanto mi serve il numero di occorrenze delle chiavi che iniziano per 3.

Riguardo alla tua domanda precedente : io non ho scritto quella riga di codice ... l'ha scritta Nikopol in pseudocodice.

[oregon]

Se il problema è un altro, allora dovevi creare un altro thread. Così si fa confusione.

[aleRomatre]

Ok va bene scusami, creo un altro thread... Grazie mille ad entrambi