[C] albero binario da vettore

[tonno16]

salve a tutti. ho un vettore di tipo char del genere: ciao(casa,albero)

ho messo solo tre nomi. ciao è la radice dell albero. casa figlio sinistro albero figlio destro.

ho creato una struttira del tipo:

struct nodo{
char* parola
struct nodo *SX
struct nodo *DX
};

avevo pensato ad una funzione ricorsiva per la creazione dell albero ma forse mi sbaglio....difatti l'assegnazione di tutti i nodi termina quando la stringa termina, in questo caso quando incontra il carattere ')'

per cui il tutto va fatto tramite for??

come posso muovermi?
grazie

[apatriarca]

Una funzione ricorsiva va benissimo, probabilmente all'interno ci sarà però un ciclo.. Quello che a grandi linee dovrai fare e iterare lungo la lista. Se incontri '(' smetti di leggere il testo del nodo corrente e richiami la funzione sul nodo figlio, se incontri la virgola ritorni al padre e passi al figlio successivo, se incontri ')' hai finito la lettura del nodo e ritorni al padre. Ovviamente la logica è un po' più complicata e devi considerare qualche caso in più probabilmente, ma spero ti sia chiara..

[tonno16]

iterare lungo la lista? ma che lista? il problema è che se ho casa[ciao,pesca(olio,miele)]

l'albero deve essere: casa radice. i figli di casa sono sx= ciao, dx = pesca. figli di pesca= olio e miele

[apatriarca]

Ho scritto lista ma intendevo il tuo vettore.. Devi guardare un carattere per volta del vettore di char e andare avanti e indietro nella ricorsione in base al carattere che incontri.. Ma in questo nuovo esempio hai introdotto due nuovi caratteri ('[' e ']') che hanno un significato nella tua stringa. Per prima cosa dovresti definire meglio come è fatta la tua stringa.

[tonno16]

no no asp. compaiono solo tonde nel mio esercizio. Ho messo ora delle quadre, tanto per evidenziare il tutto. avevo in mente una cosa del tipo:

funzione[100]="ciao(casa,albero(mele,pere)) .
ciao = radice
ciao.sx= casa
ciao.dx= albero
casa è una foglia.
albero.sx=mele e dx= pere.

il mio algoritmo sarebbe una roba del genere:

typedef struct _albero{
char* dato;
struct _albero *SX, *DX, *padre
}albero;

albero* nodo;
nodo=NULL;

void build_tree(char funz[100], tree nodo){       
        char*  parola;
        int i,k=0;
        
        for(i=0;i<100;i++){
               if(funz[i]!='('  ){
                     parola= (char*) realloc (parola, sizeof(char) * k+1 );    // è giusto questo k+1?
               
              if(funz[i]==' ( '  ){
                     nodo->dato=parola;
              }

              if(funz[i]==' ) '{   build_tree(funz[100], nodo->padre) }
              
              build_tree(funz[100], nodo->sx)
              build_tree(funz[100], nodo->dx
}

quanto ho sbagliato?

[apatriarca]

Ma nella tua funzione stai supponendo in qualche modo che sia già stato tutto allocato e non credo abbia senso darlo per scontato.. La parte in cui reallochi la stringa tutte le volte non ha molto senso. Puoi infatti semplicemente memorizzarti l'inizio e la fine della stringa e poi allocare la memoria per questa stringa solo alla fine. Le chiamate ricorsive e il test per verificare che il carattere sia uguale alla parentesi chiusa devono in qualche modo essere fatte all'interno dell'if in cui verifichi che il carattere sia la parentesi aperta. Il mio consiglio è di dividere la parte in cui leggi la parola da quella dove fai le chiamate ricorsive. Per cui scrivi un primo ciclo dal quale esci appena incontri un carattere tra "()," e poi scrivi il codice per creare i nodi figli. Non ho pensato più di tanto al codice ma immagino potresti aver bisogno di un numero maggiore di argomenti. Le chiamate ricorsive dovrebbero infatti probabilmente restituire la posizione all'interno della stringa dopo aver creato il nodo.

[tonno16]

La parte in cui reallochi la stringa tutte le volte non ha molto senso. Puoi infatti semplicemente memorizzarti l'inizio e la fine della stringa e poi allocare la memoria per questa stringa solo alla fine

del tipo che riallocare una posizione in più ogni volta è sbagliato? che sia dispendioso sinceramente non mi importa....
ma casa(ciao) dunque l'inizio è la 'c' il for prosegue per altri 3 cicli arriva alla '(' e li alloca un vettore con i posizioni?
ma nel mio modo che ora riposto e sembra funzionare io memorizzo lettera per lettera. Col consiglio che mi dai come mi muovo? quando arrivo alla '(' non so come memorizzare i carattere precedenti.

Comunque la versione funzionante:

void build_tree(tree* alb, char funz[]){
     
     int i, k;
     char *operando;
     operando=(char*)malloc(1*sizeof(char));

     k=0;
     for(i=0;i<100;i++){
        
        if(funz[i]=='(' ){ 
            operando=(char*)realloc(operando,sizeof(char) * (k+1) );
            operando[k]='\0';
            
            tree* nuovo;
            break; 
        }
        if(funz[i]!='(' ){
            operando=(char*)realloc(operando,sizeof(char) * (k+1) );  // k+1 perchè alloco un altra posizione
            operando[k]=funz[i];
            k++;
        }
     }//puts(operando);
}

la funzione lo dichiarata con void....in quanto data la mia struttura albero pensavo di fare albero->parola=operando
anche se vedo che ho problemi. Per cui per ora la funzione non mi ritorna niente.
Immagino una cosa del genere:

void build_tree(tree* alb, char funz[], int pos){ // pos=0 nella mail
     
     int i, k;
     char *operando;
     operando=(char*)malloc(1*sizeof(char));

     k=0;
     for(i=pos;i<100;i++){
        
        if(funz[i]=='(' ){ 
            operando=(char*)realloc(operando,sizeof(char) * (k+1) );
            operando[k]='\0';
            alb=(tree*)malloc(sizeof(T));
            alb->dato=operando;  
            
            pos=i;
            build_tree(&*alb->sx,funz,i);
            build_tree(&*alb->dx,funz,i);
                   
            
        }
        if(funz[i]!='(' ){
            operando=(char*)realloc(operando,sizeof(char) * (k+1) );  // k+1 perchè alloco un altra posizione
            operando[k]=funz[i];
            k++;
        }   
     }//puts(operando);
}

scusa, se magari scrivo cavolate, ma a quanto pare il mio cervello fa fatica ad assimilare ste cose

[apatriarca]

Due commenti rapidi che in questo momento ho poco tempo:
1. Ti stai limitando a stringhe con una dimensione fissa, ma non c'è alcun motivo. Puoi passare un array di qualsiasi dimensione alla funzione e puoi semplicemente verificare se è stato raggiunto il terminatore di stringa '\0' ad un certo punto.
2. Se preferisci reallocare tutto in continuazione puoi farlo. Non è sbagliato, solo molto più lento..

[tonno16]

ma guarda, grazie del consiglio. per ora se metto in input cane(gatto,pesca) giustamente mi mette in operando "cane"....per cui funziona. Magari alla fine della costruzione dell' albero posso cambiarlo.


nella struttura ora ho;

typedef struct T{ // comincio a definire la struttura che mi servirà
char* dato; // come posso notare ho il valore attuale
int numero;
struct T *l;
struct T *r; // e due puntatori uno al figlio sinistro
// l'altro al figlio destro.
}*tree;

nella main ho:
tree albero;
albero = NULL;
albero=build_tree(albero,funzione,posizione);
}

il mio codice

tree build_tree(tree alb, char funz[], int pos){ // pos=0 nella mail
     
     int i, k;
     char *operando;
     operando=(char*)malloc(1*sizeof(char));

     k=0;
     for(i=pos;i<100;i++){
        
        if(funz[i]=='(' ){ 
            operando=(char*)realloc(operando,sizeof(char) * (k+1) );
            operando[k]='\0';
            
            if(alb==NULL){ 
                tree nuovo;
                nuovo=(tree)malloc(sizeof(T));                
                nuovo->dato=operando;
                nuovo->l=NULL;
                nuovo->r=NULL;
                return nuovo;
            }
            break;
                     
        }
        if(funz[i]!='(' ){
            operando=(char*)realloc(operando,sizeof(char) * (k+1) );  // k+1 perchè alloco un altra posizione
            operando[k]=funz[i];
            k++;
        }   
     }//puts(operando);  //chiusura for
     
      
     // printf("%s",alb->dato);
  
}

sto pezzo di codice funziona....ma come notate ho fatto una piccola stampa di alb->dato all'interno della funzione. Sbaglio qualcosa poichè se creo una funzione stampa fuori da tutto.....non va a trovare niente nell albero e restituisce null. Sbaglio qualcosa coi puntatori magari e la memorizzazione nell' albero avviene solo all'interno della funzione.

ora con una funzione stampa_albero la stampa nel primo nodo viene. Ora provo a fare il rocedimento per le parentesi

[tonno16]

UPDATE...codice corretto......guardare e grazie a tutti :I

[apatriarca]

Invece di usare tanti if uno dopo l'altro conviene utilizzare un if/else if/else. Invece di allocare i figli nella funzione e richiedere che venga passato un nodo già allocato come argomento si potrebbe anche allocare direttamente il nodo padre nella funzione e far creare i figli nelle chiamate ricorsive.. Per il resto attenderei la parte più complicata della gestione delle chiamate ricorsive..

[tonno16]

ora sono a lavoro. Ti ringrazio. Vedo più tardi di combinare qualcosa

[tonno16]

ok mi rifacci ovivo. ho implementato una ricorsione. ho capiti che se p(a,x) alloco p. se incontro una tonda alloco il figlio a sinistra. se incontro una virgola richiamo la funziona sul padre e poi alloco il figlio destro.....per cui ho un Ins_dx e un Ins_sx.
se incontro una tonda chiusa, ritorno al padre del padre.

ecco il mio code

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <string.h>

FILE *testo;

struct nodo {// Albero di numeri interi
  int DATO;
  struct nodo *DX;
  struct nodo *SX;
  struct nodo *PAR;
} NODO;

typedef struct nodo* tree;

tree Albero_Vuoto(void)
{// Ritorna un albero vuoto (un puntatore NULL)
  return(NULL);
}

tree Ins_Ord_sx(int el,tree RADICE)  // Costruisce un albero binario di ricerca
{
		 if (RADICE==NULL) {  // Allocazione di una cella di memoria libera
				RADICE=(tree)malloc(sizeof(NODO));
				RADICE->DATO=el;
				RADICE->SX=NULL;
				RADICE->DX=NULL;
				//RADICE->PAR=NULL;  // padre
				return RADICE;
		 }
		else {
			    puts("ciao");
			    RADICE->SX=Ins_Ord_sx(el,RADICE->SX);
				RADICE->PAR = RADICE;
				return RADICE;
		}
}

tree Ins_Ord_dx(int el,tree RADICE)  // Costruisce un albero binario di ricerca
{
		 if (RADICE==NULL) {  // Allocazione di una cella di memoria libera
				RADICE=(tree)malloc(sizeof(NODO));
				RADICE->DATO=el;
				RADICE->SX=NULL;
				RADICE->DX=NULL;
				RADICE->PAR=NULL; // padre
				return RADICE;
		 }
		else {
				RADICE->DX=Ins_Ord_dx(el,RADICE->DX);
				RADICE->DX->PAR=RADICE;
				return RADICE;
		}
	   
 
}

void StampaAlbero(tree a) {
  if(a==NULL) {
    printf("()");
    return;
  }

  printf(" ( %c ",a->DATO);  
  StampaAlbero(a->SX);
  StampaAlbero(a->DX);
  printf(" ) ");            
}


int main() {
 
	int vettore[]={10,2,5,7,9,1,44};
	
	//StampaAlbero(t1);                                  
    
	tree t1;
	t1 = NULL;	// inizializzo l'albero vuoto

    testo=fopen("derivata.txt", "r");
	
	char Buf[100];   // lungheza massima stringa che trova

	fscanf(testo,"%s",Buf);// BUF = funzione
	fclose(testo);

	t1 = Ins_Ord_sx(Buf[0],t1);
	//StampaAlbero(t1);
	
	t1=t1->SX;
	t1 = Ins_Ord_sx(Buf[2],t1);
	
	StampaAlbero(t1);
	
	//t1=t1->SX;
    //t1 = Ins_Ord_sx(Buf[4],t1);
	
	//printf("%c", t1->PAR->DATO);

	
	
    

system("pause");
return 0;
}

nell inserimento della parte destra....eseguo bene l' assegnazione del padre? non capisco.
perchè nella main se faccio stampa(t1) tutto fila. se faccio stampa(t1->padre) crasha in esecuzione con un errore.

potetr aiutarmi?