[C/C++] Stampare a sommario

[ferra03]

Ciao a tutti, devo scrivere una funzione che stampi un'elbero binario come un sommario per essere più chiaro vi allego un'immagine, guardate il punto 1.2:

http://lonati.dsi.unimi.it/algo/0910/lab/L07.pdf


La funzione viene definita nel seguente modo:

void bit_printassummary ( Bit_node p, int spaces );

Nel testo mi viene suggerto di usare una visita in prorder(vi scrivo anche la funzione preorder originale, e quella di printnode):

void bit_preorder ( Bit_node p ){
if ( p ) {
bit_printnode ( p );
bit_preorder ( p -> l );
bit_preorder ( p -> r );
}
}

void printnode(Bit_node p){
	printf("%d ",p->item);
}

la cosa che non ho veramente capito al di là della funzione in se, è a cosa corrispondono gli spazi che passo come argomento alla funzione, perchè in linea di principio per stampare a sommario si deve far addentrare il nodo di uno spazio in base a quanti padri abbia, o sbaglio?

Grazie

[YuYevon]

Originariamente inviato da ferra03
la cosa che non ho veramente capito al di là della funzione in se, è a cosa corrispondono gli spazi che passo come argomento alla funzione, perchè in linea di principio per stampare a sommario si deve far addentrare il nodo di uno spazio in base a quanti padri abbia, o sbaglio?

A meno che i nodi del tuo albero non abbiano anche un puntatore al padre, non hai modo di sapere "il numero dei padri" a salire. Quello in effetti sarebbe un buon modo per sapere quanti spazi stampare senza ricorrere al parametro "spaces", calcolando cioè al volo il livello del nodo. In ogni caso, "spaces" indica semplicemente, ad ogni livello, il numero di spazi da stampare. Al primo livello, cioè al "livello 0", quello della radice, devi stampare 0 spazi; al secondo livello (1) un solo spazio. Al terzo (2) due spazi e così via. Poi vabbè oltre agli spazi puoi stampare altri caratteri, ad esempio nel pdf che hai linkato ci sono dei simpatici asterischi, ma nulla ti vieta di metterci qualcosa di più significativo come cuoricini, stelline od altro.

[ferra03]

ah ok, ma allora come posso "assegnare" a spaces il valore di uno spazio se è un intero?

[YuYevon]

Non devi assegnare "il valore di uno spazio" a spaces...

"spaces" indica semplicemente, ad ogni livello, il numero di spazi da stampare

[ferra03]

per adesso ho scritto questa parte:

void bit_printassummary(Bit_node p, int spaces) {
           
           if(p) {
                printf("* %d", p->item);
           }
}

perchè con la visita in preordine il primo nodo letto è sempre la radice e quindi verrà sempre stampato in questo modo, ma ora come implemento spaces in modo tale che incrementino gli spazi prima dell'asterisco?

[YuYevon]

Richiami la visita sul nodo radice, stampi 0 spazi (o per dirla in maniera forse più utile "stampi spazi per 0 volte"), poi stampi le informazioni relative a quel nodo e dopo? Devi chiamare la procedura ricorsivamente sui figli destro e sinistro passandole p -> l (o p -> r) e un valore incrementato di spaces, perché al secondo livello dell'albero non devi più stampare 0 spazi ma 1 (o due, tre, dipende dall'incremento che stabilisci tu). Tutto questo viene ripetuto ricorsivamente per ogni nodo.

[ferra03]

grazie ai tuoi consigli sono molto vicino alla soluzione ti posto la funzione:

void bit_printassummary(Bit_node p, int spaces) {
	int i;
	if(p) {
		for(i = 0; i < spaces; i++) {
			printf(" ");
		}
		printf("*%d\n", p -> item);
		bit_printassummary(p -> l, spaces + 1);
		bit_printassummary(p -> r, spaces + 1);
		}
		
	}

chiamata su questo array(29 39 3 88 22 41 89 43 78 83) quindi con visita in prorder(29 39 88 43 78 22 83 3 41 89) con 2 come parametro spaces mi da questo output:

  *29
   *39
    *88
     *43
     *78
    *22
     *83
    *3
     *41
     *89

in sostanza figlio destro e sinistro non sono in linea. Ho per caso sbagliato il for?

[YuYevon]

Con quell'array intendi dire che il tuo albero è così?

                      29
           39                   3
     88         22         41       89
  43    78    83

Comunque l'idea è proprio quella, e sembra strano quell'output. Sicuro di aver costruito bene l'albero?

Prova così, anche se non dovrebbe cambiare praticamente nulla

void bit_printassummary(Bit_node p, int spaces) {
	int i;
	if(p) {
		for(i = 0; i < spaces; i++) {
			putchar(' ');
		}
		printf("*%d\n", p -> item);
                spaces++;
		bit_printassummary(p -> l, spaces);
		bit_printassummary(p -> r, spaces);
	}		
}

[ferra03]

Si l'output è uguale anche con la tua versione, per quanto riguarda l'albero sono abbastanza sicuro di averlo costruito come si deve, comunque se vuoi dargli un'occhiata di posto l'intero codice:

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define N 10

struct bit_node{
	int item;
	struct bit_node *l, *r;
};

typedef struct bit_node *Bit_node;

Bit_node bit_left(Bit_node p){
	if(p){
		return(p->l);
	}
	return NULL;
}

Bit_node bit_right(Bit_node p){
	if(p){
		return(p->r);
	}
	return NULL;
}

Bit_node bit_new (int item){
	Bit_node new;
	
	new=malloc(sizeof(struct bit_node));
	
	if(new == NULL){
		printf("\nMemoria Esaurita\n");
		exit(EXIT_FAILURE);
	}
	new->item=item;
	new->l= NULL;
	new->r=NULL;
	return new;
}

void printnode(Bit_node p){
	printf("%d ",p->item);
}

void bit_preorder(Bit_node p){
	if(p){
		printnode(p);
		bit_preorder(p->l);
		bit_preorder(p->r);
	}
}

void bit_inorder(Bit_node p){
	if(p){
		bit_inorder(p->l);
		printnode(p);
		bit_inorder(p->r);
	}
}

void bit_postorder(Bit_node p){
	if(p){
		bit_postorder(p->l);
		bit_postorder(p->r);
		printnode(p);
	}	
}

void bit_printassummary(Bit_node p, int spaces) {
	int i;
	if(p) {
		for(i = 0; i < spaces; i++) {
			putchar(' ');
		}
		printf("*%d\n", p -> item);
                spaces++;
		bit_printassummary(p -> l, spaces);
		bit_printassummary(p -> r, spaces);
	}		
}


Bit_node bit_arr2tree(int a[], int size, int j){
Bit_node root=bit_new(a[j]);
int left = 2*j+1, right = 2*j+2;
	if(left < size){
		root -> l = bit_arr2tree(a, size, left);
	}
	if(right < size) {
		root -> r = bit_arr2tree(a, size, right);
	}
	return root;
}
int main(void){

	int array[N];
	int i;
	Bit_node root;

	srand(time(NULL));


	/*generazione array di numeri casuali da 1 a 100*/
	for(i=0; i<N; i++) {
		array[i]=rand()%100+1;
	}

	/*stampo l'array*/
	printf("\nARRAY:\n");

	for(i=0; i<N; i++) {
		printf("%d ", array[i]);
	}

	printf("\n\n");
	printf("*************************\n");
	/*creazione albero*/
	root=bit_arr2tree(array, N, 0);

	printf("inorder\n");
	bit_inorder(root);
	printf("\n\n");
	printf("preorder\n");
	bit_preorder(root);
	printf("\n\n");
	printf("postorder\n");
	bit_postorder(root);
	printf("\n\n");
	printf("**************************\n\n");
	bit_printassummary(root, 0);
	
	return 0;
}

Grazie ancora per l'aiuto

[YuYevon]

Ma a me questi output sembrano corretti, cosa c'è che non va?

ARRAY:
100 30 27 50 43 21 60 30 73 2

*************************
inorder
30 50 73 30 2 43 100 21 27 60

preorder
100 30 50 30 73 43 2 27 21 60

postorder
30 73 50 2 43 30 21 60 27 100

**************************

*100
 *30
  *50
   *30
   *73
  *43
   *2
 *27
  *21
  *60

ARRAY:
58 86 72 7 95 20 67 51 69 25

*************************
inorder
51 7 69 86 25 95 58 20 72 67

preorder
58 86 7 51 69 95 25 72 20 67

postorder
51 69 7 25 95 86 20 67 72 58

**************************

*58
 *86
  *7
   *51
   *69
  *95
   *25
 *72
  *20
  *67