Buongiorno a tutti,
ho un problema nella lettura di un albero binario da file. In pratica, un programma A riceve in input da tastiera un albero binario (non di ricerca), e lo salva in un file in modalità pre-order (Operazione su nodo, visita sotto-albero sx in pre-order, visita sotto-albero dx in pre-order), di seguito il codice in C:
A questo punto, un programma B deve leggere il contenuto del file e ricreare dunque il medesimo albero binario. Il problema principale sta nei vincoli richiesti:
1) Utilizzare una sola funzione con la seguente intestazione:
La funzione dovrà dunque restituirmi un puntatore alla struttura.
2) Il vincolo 1 e i parametri forniti alla funzione non mi consentono di utilizzare la ricorsione, dal momento che non ho modo di muovermi nell'albero.
La natura randomica della funzione di inserimento dei nodi, va a complicare ulteriormente le cose, in quanto i nodi non seguono un percorso prestabilito:
Vorrei discuterne un pò con voi per tirare fuori qualche idea. Ovviamente non voglio il codice, solo uno scambio di idee. :)
ho un problema nella lettura di un albero binario da file. In pratica, un programma A riceve in input da tastiera un albero binario (non di ricerca), e lo salva in un file in modalità pre-order (Operazione su nodo, visita sotto-albero sx in pre-order, visita sotto-albero dx in pre-order), di seguito il codice in C:
Codice:
void saveTree(FILE *fPtr, NODE_PTR rootPtr){
if(rootPtr == NULL){
fprintf(fPtr, "%s\n", "NULL");
} else{
fprintf(fPtr, "%s%d\n", "NODO: ", rootPtr->key);
saveTree(fPtr, rootPtr->sxTree);
saveTree(fPtr, rootPtr->dxTree);
}
}
A questo punto, un programma B deve leggere il contenuto del file e ricreare dunque il medesimo albero binario. Il problema principale sta nei vincoli richiesti:
1) Utilizzare una sola funzione con la seguente intestazione:
Codice:
...
struct node{
int key;
struct node* sxTree;
struct node* dxTree;
};
typedef struct node NODE;
typedef NODE NODE_PTR;
//Intestazione
NODE_PTR freadAB(FILE* fPtr);
...
La funzione dovrà dunque restituirmi un puntatore alla struttura.
2) Il vincolo 1 e i parametri forniti alla funzione non mi consentono di utilizzare la ricorsione, dal momento che non ho modo di muovermi nell'albero.
La natura randomica della funzione di inserimento dei nodi, va a complicare ulteriormente le cose, in quanto i nodi non seguono un percorso prestabilito:
Codice:
struct node{
int key;
struct node* sxTree;
struct node* dxTree;
};
typedef struct node NODE;
typedef NODE NODE_PTR;
NODE_PTR newNode(int key){
NODE_PTR newNode = (NODE_PTR)malloc(sizeof(NODE));
if(newNode != NULL){
newNode->key = key;
newNode->sxTree = NULL;
newNode->dxTree = NULL;
}
}
NODE_PTR insRand(NODE_PTR rootPtr, int key){
if(rootPtr == NULL){
NODE_PTR node = newNode(key);
rootPtr = node;
} else{
int way;
way = rand()%2;
if(way){
rootPtr->sxTree = insRand(rootPtr->sxTree, key);
} else{
rootPtr->dxTree = insRand(rootPtr->dxTree, key);
}
}
return rootPtr;
}
Vorrei discuterne un pò con voi per tirare fuori qualche idea. Ovviamente non voglio il codice, solo uno scambio di idee. :)