[C] Albero binario

**^EvAmPiReS^** · 26-09-2005, 00:08

codice:

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


struct NodoAlbero;

typedef struct NodoAlbero *Posizione;

typedef struct NodoAlbero *AlberoRicerca;

typedef int TipoElemento;

struct NodoAlbero

{
	TipoElemento Chiave;
	
	AlberoRicerca Left;

	AlberoRicerca Right;

} ;

Come inizializzo l'albero a NULL?Ho provato con struct NodoAlbero *AlberoRicerca = NULL ma poi mi dà errori in esecuzione.

codice:

AlberoRicerca Insert (TipoElemento X, AlberoRicerca T)

{
	if ( T == NULL)

	{
		T = malloc ( sizeof (struct NodoAlbero) );
			if ( T == NULL )
				printf ("Errore di allocazione\n");
				else
				{
					T->Chiave = X;
					T->Left = T->Right = NULL;
				}
			}
				else
					if (X < T->Chiave )
						T->Left = Insert (X, T->Left );
				else 
					if (X > T->Chiave )
						T->Right = Insert (X, T->Right);
	return T;
}

Come uso la funzione insert nel main la prima volta per creare la radice?

Grazie in anticipo per qualsiasi risposta.

**alka** · 26-09-2005, 01:18

Il linguaggio di programmazione va indicato anche nel titolo.
Si tratta di C++, immagino. Correggo io.

Ciao!

**infinitejustice** · 26-09-2005, 08:18

Originariamente inviato da ^EvAmPiReS^

Come inizializzo l'albero a NULL?
typedef struct NodoAlbero *AlberoRicerca;
Ho provato con struct NodoAlbero *AlberoRicerca = NULL ma poi mi dà errori in esecuzione.

Alka direi che è C nn C++

Forse sbagli nel passare poi il puntatore alla radice (dovresti passarlo per indirizzo e quindi gestirlo come doppio puntatore)

Dai un'occhiata al mio albero binario di ricerca
http://www.fuoridalbranco.com/unife....ci%20sorgente/(tree)%20BST.c

La ricerca è sia ricorsiva che iterativa. Add è chiamata per creare nuovi nodi. Lei si preoccupa di capire se bisogna creare un nuovo nodo (newnode) o se bisogna tovare la posizione corretta all'interno dell'albero (pathfind).

Avevo fatto anche un esempio arbitrario con relativo disegnino ASCII dell'albero ma si è un po sballato

**^EvAmPiReS^** · 26-09-2005, 13:27

Forse sbagli nel passare poi il puntatore alla radice (dovresti passarlo per indirizzo e quindi gestirlo come doppio puntatore)

Detto in parole "sorgenti"?

Grazie per il link, penso adotterò l'iterativa visto che ancora la ricorsione non mi è proprio chiarissima

:master:
Ah, non riesco ad accedere agli appunti, ci vuole un login.

Utilissimo sto forum

P.S. ho visto nel tuo link la parola "UNIFE". Io che sono di Fano poco tempo fa prendevo un segnale wireless a banda piena denominato "UNIFE", stanno facendo prove? Come hanno fatto ad arrivare fin qua? :maLOL:

**infinitejustice** · 26-09-2005, 14:40

codice:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

struct node{
	int value;
	struct node *leftChild;
	struct node *rightChild;
	}*root = NULL;


struct node *findMin(struct node *);
struct node *findMax(struct node *);
struct node *leftRotation(struct node *);
struct node *rightRotation(struct node *);
struct node *search(struct node *, int);
struct node *searchRicorsivo(struct node *, int);
void add(struct node **, int);
void addPathfinder (struct node *, int);
void delete(struct node **, struct node *, int);
void newNode(struct node **, int);
void traverse(struct node *);
void visit(struct node *);


void main(){

	int i, array[] = {5, 3, 7, 2, 4, 8};

/*			  5
			 /    \
			3       7
		 /   \   /
	    2    4  8		*/

	srand(time(NULL));
	for(i = 0; i < 6; i++){
		add(&root, array[i]);
	}

	traverse(root);
}


void traverse(struct node *node){

	if(node == NULL)
		return;

	traverse(node->leftChild);
	traverse(node->rightChild);
	visit(node);
}


void visit(struct node *node){

	printf("%d\n", node->value);
}


//Ritorna un puntatore all'elemento piu piccolo (il child piu a sinistra senza child sinistro)
struct node *findMin(struct node *node){

	if(node == NULL)
		return NULL;
	else
		return((node->leftChild != NULL) ? findMin(node->leftChild) : node);
}


//Ritorna un puntatore all'elemento piu grande (il child piu a destra senza child destro)
struct node *findMax(struct node *node){

	if(node == NULL)
		return NULL;
	else
		return((node->rightChild != NULL) ? findMax(node->rightChild) : node);
}


//Ricerca iterativa: in caso positivo ritorna un puntatore all'elemento cercato
struct node *search(struct node *node, int x){

	if(node == NULL)
		return(NULL);

	else if(node->value == x)
		return(node);

	else if (node->value > x)
		return (search(node->leftChild, x));

	else
		return(search(node->rightChild, x));
}


//Ricerca ricorsiva
struct node *searchRicorsivo(struct node *node, int x){

	while((node != NULL) && (node->value != x)){
		if(node->value > x)
			node = node->leftChild;
		else
			node = node->rightChild;
		}

return(node);
}



void add(struct node **node, int x) {

	if((*node) == NULL)
		newNode(node, x);
	else
		addPathfinder(*node, x);
}


void newNode(struct node **node, int x){

	if(!((*node) = malloc(sizeof(struct node))))
		abort();
	(*node)->leftChild = NULL;
	(*node)->rightChild = NULL;
	(*node)->value = x;
}


void addPathfinder (struct node *node, int x) {

	if(x < node->value){
		if(node->leftChild != NULL)
			addPathfinder(node->leftChild, x);
		else
			newNode(&(node->leftChild), x);
		}
	else{
		if(node->rightChild != NULL)
			addPathfinder(node->rightChild, x);
		else
			newNode(&(node->rightChild), x);
		}
}


void delete(struct node **father, struct node *tree, int x){

	if(tree->value != x){
		if(x < tree->value)
			delete(&(tree->leftChild), tree->leftChild, x);
		else
			delete(&(tree->rightChild), tree->rightChild, x);
		}

	else{
		if((tree->leftChild == NULL) && (tree->rightChild == NULL)){	// il nodo e' una foglia
			*father = NULL;
			free(tree);
			}
		else if(tree->leftChild == NULL){		// il nodo ha solo il figlio di destra
			*father = tree->rightChild;
			free(tree);
			}
		else if(tree->rightChild == NULL){		// il nodo ha solo il figlio di sinistra
			*father = tree->leftChild;
			free(tree);
			}
		else{ 													// il nodo ha due figli
			tree->value = (findMax(tree->leftChild))->value;
			delete(&(tree->leftChild),
			tree->leftChild,
			tree->value);
			}
		}
}


struct node *rightRotation(struct node *node){

	struct node *temp = node->leftChild;
	node->leftChild = temp->rightChild;
	temp->rightChild = node;

return temp;
}


struct node *leftRotation(struct node *node){

	struct node *temp = node->rightChild;
	node->rightChild = temp->leftChild;
	temp->leftChild = node;

return temp;
}

**anx721** · 26-09-2005, 15:15

In genere per le funzioni che modificano un albero, come quella per fare un inserimento o una cancellazione, si possono adottare 3 strategie:

1 - le funzioni prendono il puntatore al nodo radice e ritornano come risultato il puntatore al nodo radice (soluzione che preferisco)

2 - le funzioni prendono il puntatore al puntatore al nodo radice

3 - le funzioni lavorano su una variabile globale.

Se non vuoi ritornare l'albero devi passare il puntatore al puntatore al nodo radice; solo inquesto modo sei ingrado di effettuare l'inserimento la prima volta, quando tale puntatore vale NULL, e in generale modificare il nodo radice.

**^EvAmPiReS^** · 26-09-2005, 18:45

codice:

AlberoRicerca Insert (TipoElemento X, AlberoRicerca T)

Credo di rientrare nel tuo secondo caso...sbaglio?
Nel caso in cui dicessi giusto, dovrei dichiarare nel main un puntatore di puntatore a struct, nel mio caso un puntatore a
struct NodoAlbero *AlberoRicerca , potrebbe funzionare?
Come lo dichiaro? struct **ptr; ptr = AlberoRicerca? Poi dovrei passarlo alle funzioni per indirizzo o per riferimento? Grazie, scusate ma mi sono fissato di capire questa cosa.

**anx721** · 26-09-2005, 19:52

No, ricadi nel mio primo caso, infatti ritorni un AlberoRicerca che deve essere il puntatore al primo nodo dell'albero e l'invocazione della funzione deve aggiornare il tuo puntatore:

AlberoRicerca albero;
TipoElemento X = ...
albero = Insert (X, albero);

**^EvAmPiReS^** · 26-09-2005, 20:37

Ok nel main ho scritto:

codice:

AlberoRicerca albero; 
TipoElemento X = 5; 
albero = Insert (X, albero);

comunque oltre al warning in compilazione che ho provato ad ignorare dovuto alla mancata dichiarazione del puntatore (non so come dichiararlo...puntatore a struct? come si dichiara?) ho un errore irreversibile in esecuzione...uffa se hai tempo e voglia di aiutarmi te ne sarei grato. Ciao.

**anx721** · 26-09-2005, 21:45

La logica della funzione è quasi giusta; l'errore sta nel fatto che scambi il nodo da inserire con la radice dell'albero, che è il parametro passato alla funzione.

codice:

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

AlberoRicerca Insert(TipoElemento X, AlberoRicerca radice){
	//se l'albero è vuoto costruisco il nodoe lo
	//ritorno nodo come nuova radice dell'albero
	if(radice == null){
		//alloco il nodo da inserire
		struct NodoAlbero *nodo = malloc(sizeof(struct NodoAlbero));
		if(nodo == NULL){
			printf ("Errore di allocazione\n");
			return radice;
		}
		nodo -> Chiave = X;
		nodo -> Left = nodo -> Right = NULL;
		return nodo;
	}
	//altrimenti richiamo ricorsivamente la funzione
	if(X < radice -> Chiave)
		radice -> Left = Insert(X, radice -> Left);
	else
		radice -> Right = Insert (X, radice -> Right);
	return radice;
}

Inoltre nel main devi inzializzare a NULL l'albero:

AlberoRicerca albero = NULL;
albero = Insert(10, albero);

Discussione: [C] Albero binario

Strumenti discussione

Ricerca discussione

Visualizza

Albero binario

Moderazione

Re: Albero binario

Re: Albero binario

Permessi di invio