Pagina 1 di 2 1 2 ultimoultimo
Visualizzazione dei risultati da 1 a 10 su 11
  1. #1
    Utente di HTML.it L'avatar di goatboy
    Registrato dal
    Mar 2011
    residenza
    Salerno
    Messaggi
    408

    [C] Cercare elemento in albero binario

    Salve a tutti, ho un problema con la ricerca di un intero all'interno di un albero binario.
    Questa è la funzione di ricerca, presa dal libro di testo da cui sto studiando, e mi è chiara.

    codice:
    TNode *binarytree_search(TBinaryTree bt, TInfo info){
        /* Caso base: Albero vuoto oppure la root è l'elemento cercato */
        if((bt==NULL) || bt->info==info){
            return bt;
        }else{
            if(info>bt->info){
                /* Fase di divide et impera */
                return binarytree_search(bt->right, info);
            }else{
                /* Fase di divide et impera */
                return binarytree_search(bt->left, info);
            }
        }
    }
    Restituisce il riferimento all'elemento, se è presente, altrimenti restituisce null.
    Ma ho un dubbio, non riesco a capire cosa voglia dire "restituisce il riferimento"..
    Come posso stampare il numero di occorrenze del numero cercato? La funzione è di tipo TNode e non capisco perchè, di solito le funzioni di ricerca sono di tipo int.

    Ho provato così ma ho sicuramente combinato un macello, anche se non mi da errori..

    codice:
    printf("Inserisci l'elemento che vuoi cercare: ");
    scanf("%d", &num);
    src=binarytree_search(bt, num);
    printf("L'elemento e' presente %d volte\n\n", src);
    Qualche consiglio? Ho lo stesso problema anche con le funzioni di ricerca del massimo e del minimo in un albero.

  2. #2
    Utente di HTML.it L'avatar di Scara95
    Registrato dal
    Jul 2009
    residenza
    Zimella (VR)
    Messaggi
    2,590
    E' un
    codice:
    TNode *
    non un
    codice:
    TNode
    Controlla la dichiarazione di TNode...
    "Quid enim est, quod contra vim sine vi fieri possit?" - Cicerone, Ad Familiares

  3. #3
    Utente di HTML.it
    Registrato dal
    Dec 2009
    Messaggi
    613

    Re: [C] Cercare elemento in albero binario

    Originariamente inviato da goatboy
    Salve a tutti, ho un problema con la ricerca di un intero all'interno di un albero binario.
    Questa è la funzione di ricerca, presa dal libro di testo da cui sto studiando, e mi è chiara.

    codice:
    TNode *binarytree_search(TBinaryTree bt, TInfo info){
        /* Caso base: Albero vuoto oppure la root è l'elemento cercato */
        if((bt==NULL) || bt->info==info){
            return bt;
        }else{
            if(info>bt->info){
                /* Fase di divide et impera */
                return binarytree_search(bt->right, info);
            }else{
                /* Fase di divide et impera */
                return binarytree_search(bt->left, info);
            }
        }
    }
    Restituisce il riferimento all'elemento, se è presente, altrimenti restituisce null.
    Ma ho un dubbio, non riesco a capire cosa voglia dire "restituisce il riferimento"..
    Come posso stampare il numero di occorrenze del numero cercato? La funzione è di tipo TNode e non capisco perchè, di solito le funzioni di ricerca sono di tipo int.

    Ho provato così ma ho sicuramente combinato un macello, anche se non mi da errori..

    codice:
    printf("Inserisci l'elemento che vuoi cercare: ");
    scanf("%d", &num);
    src=binarytree_search(bt, num);
    printf("L'elemento e' presente %d volte\n\n", src);
    Qualche consiglio? Ho lo stesso problema anche con le funzioni di ricerca del massimo e del minimo in un albero.
    Cosa vuol dire "di solito sono di tipo int"? Quella non è una funziona che conta le occorrenze di un elemento, ma una funzione che restituisce il puntatore ad un nodo contenente l'elemento cercato, se esiste. Tu cosa vuoi fare, cercare un nodo (ed eventualmente ottenerne il riferimento) o contare le occorrenze di un elemento?

    Comunque per riferimento di qualcosa s'intende il suo indirizzo, ciò che viene messo all'interno di un puntatore.

  4. #4
    Utente di HTML.it L'avatar di goatboy
    Registrato dal
    Mar 2011
    residenza
    Salerno
    Messaggi
    408
    Si, non so perchè mi ero intestardito che la funzione mi restituisse il numero di occorrenze. Per fortuna avevo scritto "la funzione mi è chiara"
    Ripensandoci ho capito, e ho risolto così:

    codice:
                    printf("Inserisci l'elemento che vuoi cercare: ");
                    scanf("%d", &num);
                    src=binarytree_search(bt, num);
                    if(src==NULL)
                        printf("Elemento non presente\n");
                    else
                        printf("L'elemento e' presente all'interno dell'albero\n");
    dove src è:

    codice:
    TNode *src;
    Se volessi invece inserire un contatore nella funzione, come potrei fare?

  5. #5
    Utente bannato
    Registrato dal
    Apr 2012
    Messaggi
    510
    Da come è scritto il codice deduco che si tratta di un albero binario di ricerca, infatti da questo spezzone di codice:

    codice:
            if(info > bt->info)
            {
                return binarytree_search(bt->right, info);
            }
            else
            {
                return binarytree_search(bt->left, info);
            }
        }
    }
    Si capisce che se l' informazione contenuta nel nodo è minore di quella cercata, si cerca nel sotto-albero destro, altrimenti si cerca nel sotto-albero sinistro.
    Per cui non è possibile contare il numero di occorrenze di un valore, il numero di occorrenze sarà 1 oppure 0 visto che l' albero binario di ricerca (se implementato correttamente) non contiene duplicati.

  6. #6
    Utente di HTML.it
    Registrato dal
    Dec 2009
    Messaggi
    613
    Originariamente inviato da Who am I
    Da come è scritto il codice deduco che si tratta di un albero binario di ricerca, infatti da questo spezzone di codice:

    codice:
            if(info > bt->info)
            {
                return binarytree_search(bt->right, info);
            }
            else
            {
                return binarytree_search(bt->left, info);
            }
        }
    }
    Si capisce che se l' informazione contenuta nel nodo è minore di quella cercata, si cerca nel sotto-albero destro, altrimenti si cerca nel sotto-albero sinistro.
    Per cui non è possibile contare il numero di occorrenze di un valore, il numero di occorrenze sarà 1 oppure 0 visto che l' albero binario di ricerca (se implementato correttamente) non contiene duplicati.
    Non sono sicuro di questa condizione di unicità degli elementi, si trovano svariate definizioni di albero binario di ricerca e molte di esse contengono condizioni per i sotto-alberi destri e sinistri tipo "maggiore o uguali di" o "minore o uguale di", il che ovviamente implica che la struttura ammette duplicati.

    Però se si seguisse rigorosamente la definizione matematica penso avresti ragione tu, visto che se non sbaglio gli alberi sono grafi e nei grafi gli elementi stanno in un insieme, e gli insieme non possono avere duplicati.

  7. #7
    Utente bannato
    Registrato dal
    Apr 2012
    Messaggi
    510
    Originariamente inviato da Kaamos
    Non sono sicuro di questa condizione di unicità degli elementi, si trovano svariate definizioni di albero binario di ricerca e molte di esse contengono condizioni per i sotto-alberi destri e sinistri tipo "maggiore o uguali di" o "minore o uguale di", il che ovviamente implica che la struttura ammette duplicati.

    Però se si seguisse rigorosamente la definizione matematica penso avresti ragione tu, visto che se non sbaglio gli alberi sono grafi e nei grafi gli elementi stanno in un insieme, e gli insieme non possono avere duplicati.
    La definizione dice che ogni dato contenuto in un nodo è una chiave, per cui ha un valore univoco e non ci sono ambiguità nella definizione.

  8. #8
    Utente di HTML.it
    Registrato dal
    Dec 2009
    Messaggi
    613
    Originariamente inviato da Who am I
    La definizione dice che ogni dato contenuto in un nodo è una chiave, per cui ha un valore univoco e non ci sono ambiguità nella definizione.
    Non ho capito, dalla pagina che hai linkato:

    "The right subtree of a node contains only nodes with keys greater than or equal to the node's key."

  9. #9
    Utente di HTML.it L'avatar di Scara95
    Registrato dal
    Jul 2009
    residenza
    Zimella (VR)
    Messaggi
    2,590
    Potrebbe non essere usato come albero di ricerca ma come struttura ordinata che ammette duplicati...
    "Quid enim est, quod contra vim sine vi fieri possit?" - Cicerone, Ad Familiares

  10. #10
    Utente di HTML.it L'avatar di goatboy
    Registrato dal
    Mar 2011
    residenza
    Salerno
    Messaggi
    408
    Più che altro a me interessava sapere se poteva capitare all'esame scritto che mi si chiedesse di "contare" le occorrenze di un dato elemento, e nel caso come si potrebbe fare. Ma se non è possibile, allora so che non capiterà
    Grazie per le risposte

Permessi di invio

  • Non puoi inserire discussioni
  • Non puoi inserire repliche
  • Non puoi inserire allegati
  • Non puoi modificare i tuoi messaggi
  •  
Powered by vBulletin® Version 4.2.1
Copyright © 2024 vBulletin Solutions, Inc. All rights reserved.