Visita inorder iterativa(Alberi)

di il
1 risposte

Visita inorder iterativa(Alberi)

Salve, sto studiando la visita inorder iterativa di un'albero e non riesco a capire dove ho sbagliato, quando chiamo il metodo inorder_iterativa stampa tutti gli elementi e poi va in segmentation fault, mi aiutate a capire dov'è l'errore? Grazie
#include<iostream>
using namespace std;
struct nodo
{
	nodo* destra;
	nodo* sinistra;
	nodo* padre;
	int val;
	
};
struct item
{
	nodo* elemento;
	item* succ;
};
class pila
{
	private:
		item* testa;
	public:
		void push(nodo* x)
		{
			item* temp=new item;
			temp->elemento=x;
			if(testa!=0)
				temp->succ=testa;
			else
				temp->succ=0;
			testa=temp;
		}
		nodo* primoelemento()
		{
			if(testa!=0)
				return testa->elemento;
		}
		nodo* pop()
		{
			nodo* a=primoelemento();
			item* t=testa;
			testa=testa->succ;
			delete t;
			return a;
		}
		bool pilavuota()
		{
			if(testa==NULL)
				return true;
			else
				return false;
		}
};
class albero
{
	private:
		nodo* radice;
	public:
		albero()
		{
			radice=NULL;
		}
		inserisci(int x)
		{
			nodo* temp=radice;
			nodo* nuovo=new nodo;
			nuovo->val=x;
			nuovo->destra=nuovo->sinistra=nuovo->padre=NULL;
			if(radice==NULL)
			{
				radice=nuovo;
			}
			else
			{
				nodo* prec=NULL;
				while(temp!=0)
				{
					prec=temp;
					if(temp->val>=x)
						temp=temp->sinistra;
					else
						temp=temp->destra;
				}
				nuovo->padre=prec;
				if(prec->val>=x)
					prec->sinistra=nuovo;
				else
					prec->destra=nuovo;
				
			}                        
		}
		
		inorder(nodo* p)
		{
			if(p!=0)
			{
			inorder(p->sinistra);
			cout<<p->val<<endl;
			inorder(p->destra);
			}
		}
		void inorder_iterativa()
		{
			pila stack;
			nodo* temp=radice;
			bool stop=false;
			while(!stop)
			{
				if(temp!=0)
				{
					stack.push(temp);
					temp=temp->sinistra;
				}
				else if(stack.pilavuota())
					stop=true;
				else
				{
					temp=stack.pop();
					cout<<temp->val<<endl;
					temp=temp->destra;
					
				}
			}
		}
		void stampa()
		{
			inorder(radice);
		}
		nodo* ricerca(int x)
		{
			nodo* temp=radice;
			if(temp==0)
				cout<<"albero vuoto";
			else
			{
				while(temp!=0 && temp->val!=x)
				{
					if(temp->val>=x)
						temp=temp->sinistra;
					else
						temp=temp->destra;
				}
				if(temp!=0)
					return temp;
				else
					return 0;
					
			}
		}
		void trapianta(nodo* u, nodo* v)
		{
			if(u->padre==NULL)
				radice=v;
			else
			{
				if(u->padre->sinistra==u)
				{
					u->padre->sinistra=v;
				}
				else
					u->padre->destra=v;
			}
			if(v!=NULL)
			{
				v->padre=u->padre;
			}
		}
		nodo* minimo(nodo* p)
		{
			while(p->sinistra!=0)
				p=p->sinistra;
			return p;
		}
		void cancella(nodo* p)
		{
			if(p!=0)
			{
				if(p->destra==NULL)
					trapianta(p,p->sinistra);
				else if(p->sinistra==NULL)
					trapianta(p,p->destra);
				else
				{
					nodo* y=minimo(p);
					if(y->padre!=p)
					{
						trapianta(y,y->destra);
						y->destra=p->destra;
						y->destra->padre=y;
					}
					trapianta(p,y);
					y->sinistra=p->sinistra;
					y->sinistra->padre=y;
				}
			}
			delete p;
		}
		nodo* successivo(nodo* p)
		{
			if(ricerca(p->val))
			{
			if(p->destra!=NULL)
				return minimo(p->destra);
			else
			{
				nodo* y=p;
				nodo* x=y->padre;
				while(y!=0 && x==y->destra)
				{
					x=y;
					y=y->padre;
				}
				return y;
			}
			}
		}
};
int main()
{
	albero alberello;
	for(int i=0; i<10; i++)
		alberello.inserisci(i);
	alberello.stampa();
	nodo* a=alberello.ricerca(5);
	alberello.cancella(a);
	cout<<endl;
	alberello.stampa();
	nodo* c=alberello.ricerca(7);
	nodo* b=alberello.successivo(c);
	cout<<b->val;
	cout<<endl<<endl;
	alberello.inorder_iterativa();
	
}

1 Risposte

  • Re: Visita inorder iterativa(Alberi)

    Ciao
    vedi quando finisce la lettura del ultimo nodo
    perchè vai a leggere un elemento che non è presente nel tuo albero.
    dovrebbe mancare la condizione di quando il nodo e null.
    spero di esserti stato d'aiuto
Devi accedere o registrarti per scrivere nel forum
1 risposte