Gabry610
24-08-2012, 08:56
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!
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!