[C] - Esercizio albero di ricerca binaria

[Ots]

Buongiorno a tutti!
Sto studiando per l'esame di programmazione di settembre e sono incappato in un esercizio che non mi convince del tutto.
Mi sto preparando sul noto libro di Deitel & Deitel - "C Corso completo di programmazione". Il materiale che vi allego è completamente opensource e scaricabile dal sito dell'editore.


L'esercizio in questione è il "Fig12.19" del capitolo "Le strutture dati in C", per coloro che avessero a disposizione il testo.
In sostanza, il programma mostra l'inserimento di dati all'interno di un albero binario. Il codice è il seguente:

/* Fig. 12.19: fig12_19.c
   Create a binary tree and traverse it 
   preorder, inorder, and postorder */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>


/* self-referential structure */
struct treeNode { 
   struct treeNode *leftPtr; /* pointer to left subtree */
   int data; /* node value */
   struct treeNode *rightPtr; /* pointer to right subtree */
}; /* end structure treeNode */


typedef struct treeNode TreeNode; /* synonym for struct treeNode */
typedef TreeNode *TreeNodePtr; /* synonym for TreeNode* */


/* prototypes */
void insertNode( TreeNodePtr *treePtr, int value );
void inOrder( TreeNodePtr treePtr );
void preOrder( TreeNodePtr treePtr );
void postOrder( TreeNodePtr treePtr );


/* function main begins program execution */
int main( void )
{ 
   int i; /* counter to loop from 1-10 */
   int item; /* variable to hold random values */
   TreeNodePtr rootPtr = NULL; /* tree initially empty */


   srand( time( NULL ) ); 
   printf( "The numbers being placed in the tree are:\n" );


   /* insert random values between 0 and 14 in the tree */
   for ( i = 1; i <= 10; i++ ) { 
      item = rand() % 15;
      printf( "%3d", item );
      insertNode( &rootPtr, item );
   } /* end for */


   /* traverse the tree preOrder */
   printf( "\n\nThe preOrder traversal is:\n" );
   preOrder( rootPtr );


   /* traverse the tree inOrder */
   printf( "\n\nThe inOrder traversal is:\n" );
   inOrder( rootPtr );


   /* traverse the tree postOrder */
   printf( "\n\nThe postOrder traversal is:\n" );
   postOrder( rootPtr );
   return 0; /* indicates successful termination */
} /* end main */


/* insert node into tree */
void insertNode( TreeNodePtr *treePtr, int value )
{ 
   /* if tree is empty */
   if ( *treePtr == NULL ) {   
      *treePtr = malloc( sizeof( TreeNode ) );


      /* if memory was allocated then assign data */
      if ( *treePtr != NULL ) { 
         ( *treePtr )->data = value;
         ( *treePtr )->leftPtr = NULL;
         ( *treePtr )->rightPtr = NULL;
      } /* end if */
      else {
         printf( "%d not inserted. No memory available.\n", value );
      } /* end else */
   } /* end if */
   else { /* tree is not empty */
      /* data to insert is less than data in current node */
      if ( value < ( *treePtr )->data ) {
         insertNode( &( ( *treePtr )->leftPtr ), value );
      } /* end if */


      /* data to insert is greater than data in current node */
      else if ( value > ( *treePtr )->data ) {
         insertNode( &( ( *treePtr )->rightPtr ), value );
      } /* end else if */
      else { /* duplicate data value ignored */
         printf( "dup" );
      } /* end else */
   } /* end else */
} /* end function insertNode */


/* begin inorder traversal of tree */
void inOrder( TreeNodePtr treePtr )
{ 
   /* if tree is not empty then traverse */
   if ( treePtr != NULL ) { 
      inOrder( treePtr->leftPtr );
      printf( "%3d", treePtr->data );
      inOrder( treePtr->rightPtr );
   } /* end if */
} /* end function inOrder */


/* begin preorder traversal of tree */
void preOrder( TreeNodePtr treePtr )
{ 
   /* if tree is not empty then traverse */
   if ( treePtr != NULL ) { 
      printf( "%3d", treePtr->data );
      preOrder( treePtr->leftPtr );
      preOrder( treePtr->rightPtr );
   } /* end if */
} /* end function preOrder */


/* begin postorder traversal of tree */
void postOrder( TreeNodePtr treePtr )
{ 
   /* if tree is not empty then traverse */
   if ( treePtr != NULL ) { 
      postOrder( treePtr->leftPtr );
      postOrder( treePtr->rightPtr );
      printf( "%3d", treePtr->data );
   } /* end if */
} /* end function postOrder */






/**************************************************************************
 * (C) Copyright 1992-2010 by Deitel & Associates, Inc. and               *
 * Pearson Education, Inc. All Rights Reserved.                           *
 *                                                                        *
 * DISCLAIMER: The authors and publisher of this book have used their     *
 * best efforts in preparing the book. These efforts include the          *
 * development, research, and testing of the theories and programs        *
 * to determine their effectiveness. The authors and publisher make       *
 * no warranty of any kind, expressed or implied, with regard to these    *
 * programs or to the documentation contained in these books. The authors *
 * and publisher shall not be liable in any event for incidental or       *
 * consequential damages in connection with, or arising out of, the       *
 * furnishing, performance, or use of these programs.                     *
 *************************************************************************/

La mia attenzione va soprattutto all'utilizzo della funzione insertNode. L'inizio mi è chiaro, cioè ho capito che se l'albero è vuoto, il nuovo dato farà parte di un nodo che verrà inserito come nodo "iniziale" dell'albero (nodo padre esclusivo). Il problema che ho io è nel comprendere appieno la parte seguente, ovvero:

if ( value < ( *treePtr )->data ) {
         insertNode( &( ( *treePtr )->leftPtr ), value );
      } /* end if */


      /* data to insert is greater than data in current node */
      else if ( value > ( *treePtr )->data ) {
         insertNode( &( ( *treePtr )->rightPtr ), value );
      } /* end else if */

Se il valore passato a insertNode è minore o maggiore del nodo corrente, la funzione verrà richiamata in modo ricorsivo passando rispettivamente l'indirizzo del sottoalbero sinistro o destro.
E' chiaro, ma secondo me non è del tutto esatto!
Mi spiego: così facendo, viene ignorato ad ogni ciclo un ramo di (sotto)albero.
Se un certo valore è minore del nodo, verrà considerato il suo sottonodo sinistro (il sottonodo DESTRO non verrà più riconsiderato e rimarrà senza sottonodi). Il sottonodo destro è destinato a rimanere così, perchè mi sembra che il passaggio iterativo continui a partire dal sottonodo sinistro: ancora se si considera un altro valore (maggiore o minore) di questo sottonodo sinistro, verrà rievocata la funzione insertNode con l'indirizzo del suo sottonodo (destro o sinistro). In altre parole, scelto un nodo si considereranno sempre i suoi sottonodi e così via, perdendo il legame col nodo "fratello".


Secondo voi è corretta come interpretazione?
Mi scuso, mi rendo pienamente conto che a parole possa risultare estremamente contorto; vi chiedo se per favore potete fare questo sforzo per aiutarmi a dileguare i miei dubbi!

 

[e_ale92]

quando la ricorsione si chiude non perdi il legame con il nodo "fratello"

ad ogni chiusura della ricorsione (tante quante sono le chiamate che vengono fatte) hai il legame con il nodo fratello. tutti i legami ti riformano l'albero completo.

p.s. non ho guardato il codice

 

[matteoc91]

Che brutta cosa gli alberi di ricerca binari :D

Cmq provo a spiegare il concetto (dimmi se qualcosa non ti è chiaro) :)

Dunque un albero di ricerca binario è un albero binario, quindi ogni nodo avrà 2 figli, uno destro ed uno sinistro.
Questo tipo di alberi gode di una proprietà particolare, ovvero: dato un nodo, tutti gli elementi appartenenti al sotto-albero sinistro saranno di valore minore rispetto al nodo considerato e tutti gli elementi appartenenti al sotto-albero destro saranno di valore maggiore rispetto al nodo considerato.

Ora, il metodo di inserimento dei nodi io l'avevo visto tramite induzione (se non ricordo male); in sostanza il discorso è questo:

Base:
prendiamo il caso base, albero vuoto; inserisco l'elemento.

Passo Induttivo:
l'albero non è vuoto; controlliamo il valore dell'elemento su cui ci troviamo; se è nullo inseriamo l'elemento (siamo giunti a destinazione); se il suo valore è maggiore significa che per definizione di albero di ricerca binario dovremo spostarci nel sotto-albero sinistro; alterimenti ci spostiamo nel sotto-albero destro.

PS: non mi ricordo se l'induzione fosse precisamente questa, ma bene o male dovremmo esserci.

Tradotto in codice non è altro che quello da te postato :)

Se il valore passato a insertNode è minore o maggiore del nodo corrente, la funzione verrà richiamata in modo ricorsivo passando rispettivamente l'indirizzo del sottoalbero sinistro o destro.
E' chiaro, ma secondo me non è del tutto esatto!
Mi spiego: così facendo, viene ignorato ad ogni ciclo un ramo di (sotto)albero.
Se un certo valore è minore del nodo, verrà considerato il suo sottonodo sinistro (il sottonodo DESTRO non verrà più riconsiderato e rimarrà senza sottonodi). Il sottonodo destro è destinato a rimanere così, perchè mi sembra che il passaggio iterativo continui a partire dal sottonodo sinistro: ancora se si considera un altro valore (maggiore o minore) di questo sottonodo sinistro, verrà rievocata la funzione insertNode con l'indirizzo del suo sottonodo (destro o sinistro). In altre parole, scelto un nodo si considereranno sempre i suoi sottonodi e così via, perdendo il legame col nodo "fratello".

Questa affermazione non è esatta; prova a considerare questa sequenza: 7 5 3 4 10 12 1 15.
La sequenza di sopra porta ad un albero di questo tipo:
Inseriamo 7; non ci sono elementi, quindi nuovo nodo.

7

Inseriamo 5; 5<7 quindi ci spostiamo a sinistra; il sotto-albero è vuoto, quindi nuovo nodo.

---7
5

inseriamo 3; 3<7 quindi ci spostiamo a sinistra; 3<5 quindi sx; sotto-albero vuoto -> nuovo nodo.

------7
---5
3

inseriamo 4; 4<7 sx; 4<5 sx; 4>3 dx; sotto-albero vuoto -> nuovo nodo.

---------7
------5
3
---4

inseriamo 10; 10>7 dx; sotto-albero vuoto -> nuovo nodo.

---------7
------5---10
3
---4

ecc...

E così via; alla fine otteremo:

------------7
------5---------10
---3-----------------12
1---4--------------------15

Questo è essenzialmente il modo in cui lavora quel determinato metodo.
Ogni volta che inserisci un nodo, questi parte dalla radice dell'albero per ricercare la posizione corretta in cui andare ad inserirlo.
Se il primo elemento và nel sotto-albero sx (come nell'esempio) non vuol dire che il blocco destro verrà ignorato perchè al richiamo del metodo (per un nuovo nodo) questi ripartirà dalla root.

Quindi in definitiva l'unico caso in cui il sotto-albero dx della root non viene considerato è quando il primo elemento è il più grande di tutta la sequenza.
Se poi andiamo a considerare un unico nodo, i.e. guarda quando inseriamo 4, non è vero che scelto il sotto-albero sx viene sempre ignorato il dx, di fatti vedi che 4 lo inseriamo in un sotto-albero dx a partire da una scelta iniziale di un sx (7>4 perciò sx, ma 3<4 perciò dx).
Quando il metodo viene richiamato ricorsivamente, è l'intero metodo che viene rieseguito, non solo una parte dello stesso.

 

[e_ale92]

Passo Induttivo:
l'albero non è vuoto; controlliamo il valore dell'elemento su cui ci troviamo; se è nullo inseriamo l'elemento (siamo giunti a destinazione); se il suo valore è maggiore significa che per definizione di albero di ricerca binario dovremo spostarci nel sotto-albero sinistro; alterimenti ci spostiamo nel sotto-albero destro.

preciso questa cosa perchè mi sono un po' confuso...

se l'albero NON è nullo:

0) controllo l'elemento da inserire (info) con il primo nodo (tree->info)
1) se info è maggiore mi sposto nel ramo destro
2) se info è minore mi sposto nel ram sinistro
3) eseguo ricorsivamente

se l'albero è nullo:

0) inserisco info in tree->info e ritorno tree

 

[matteoc91]

preciso questa cosa perchè mi sono un po' confuso...

se l'albero NON è nullo:

0) controllo l'elemento da inserire (info) con il primo nodo (tree->info)
1) se info è maggiore mi sposto nel ramo destro
2) se info è minore mi sposto nel ram sinistro
3) eseguo ricorsivamente

se l'albero è nullo:

0) inserisco info in tree->info e ritorno tree

Si, non mi ricordo alla perfezione come si definisce il passo induttivo (se non sbaglio dovrebbe esserci anche qua una suddivisione in 2 parti, ma non ne sono sicuro).
Se volete la definizione precisa posso andare a cercarla (purtroppo a memoria non mi ricordo).
Fatemi sapere se devo cercarla :)

 

[e_ale92]

in realtà se l'albero è nullo, prima devi creare il nodo richiamando la node_create (il controllo se il nodo è stato creato con successo o meno lo puoi fare o nella node_create o nella funzione di inserimento) e solo dopo inserisci l'info.
per quanto riguarda la ricorsione non ci sono altri passi :boh:

se volete vi scrivo la funzione :look:

 

[matteoc91]

in realtà se l'albero è nullo, prima devi creare il nodo richiamando la node_create (il controllo se il nodo è stato creato con successo o meno lo puoi fare o nella node_create o nella funzione di inserimento) e solo dopo inserisci l'info.
per quanto riguarda la ricorsione non ci sono altri passi :boh:

Si si, hai ragione :)
Ho scritto abb di fretta è non ho controllato :D

 

[Ots]

Vi ringrazio, avete dato risposte chiare ed esaurienti, ora ho capito! ;)