Arbol (ABB)
c++ – podar y elemento derecho
#include<iostream.h>
#include<conio.h>
struct nodo
{
int valor;
struct nodo* izq;
struct nodo* der;
};
typedef struct nodo *ABB;
void inserta(ABB& ,int);
void preorden(ABB);
void postorden(ABB);
void enorden(ABB);
void verarbol(ABB,int);
void elem_d_i(ABB);
void elem_d_d(ABB);
int buscar(ABB,int);
int buscarmayor(ABB);
int buscarmenor(ABB);
int subarbol(ABB);
void podar(ABB&,int);
void verelem_D_I();
void main()
{
ABB arbol=NULL;
int n,x,opc;
do
{
cout<<"menu principal"<<endl;
cout<<"1.ingresar elementos"<<endl;
cout<<"2.pre orden"<<endl;
cout<<"3.post orden"<<endl;
cout<<"4.en orden"<<endl;
cout<<"5.visualizar arbol"<<endl;
cout<<"6.buscar elementos"<<endl;
cout<<"7.buscar mayor"<<endl;
cout<<"8.buscar menor"<<endl;
cout<<"9.podar"<<endl;
cout<<"10.talar"<<endl;
cout<<"11.ver elem izquierda"<<endl;
cout<<"12.ver elem derecha"<<endl;
cout<<"13.ver el menor de mayores"<<endl;
cout<<"0.salir"<<endl;
cout<<"=========================="<<endl;
cout<<"ingrese una opcion: ";cin>>opc;
switch(opc)
{
case 1:{
cout<<"ingrese cantidad de elem. al arbol: ";cin>>n;
for(int i=0;i<n;i++)
{
cout<<"ingrese numero"<<i<<" : ";cin>>x;
inserta(arbol,x);
}
getch();
break;
}//fin case1
case 2:{
if(arbol!=NULL)
{
cout<<endl<<"pre orden : ";
preorden(arbol);
}
else
{
cout<<"el arbol no tiene elementos";
}
getch();
break;
}//fin case2
case 3:{
if(arbol!=NULL)
{
cout<<endl<<"post orden : ";
postorden(arbol);
}
else
{
cout<<"el arbol no tiene elementos";
}
getch();
break;
}//fin case3
case 4:{
if(arbol!=NULL)
{
cout<<endl<<"en orden : ";
enorden(arbol);
}
else
{
cout<<"el arbol no tiene elementos";
}
getch();
break;
}//fin case4
case 5:{
cout<<" visualizacion del arbol "<<endl<<endl;
if(arbol!=NULL)
{
verarbol(arbol,0);
}
else
{
cout<<"el arbol no tiene elementos";
}
getch();
break;
}//fin case5
case 6:{
int elem,r;
if(arbol!=NULL)
{
cout<<"ingrese elemento a buscar: ";cin>>elem;
r=buscar(arbol,elem);
if(r==1)
cout<<elem<<" encontrado";
else
cout<<elem<<" NO encontrado";
}
else
{
cout<<" el arbol no tiene elementos";
}
getch();
break;
}//fin case6
case 7:{
if(arbol!=NULL)
{
cout<<"el mayor elemento es: "<<buscarmayor(arbol);
}
else
{
cout<<"el arbol no tiene elementos";
}
getch();
break;
}//fin case7
case 8:{
if(arbol!=NULL)
{
cout<<"el menor elemento es: "<<buscarmenor(arbol);
}
else
{
cout<<"el arbol no tiene elementos";
}
getch();
break;
}//fin case8
case 9:{
int corte;
if(arbol!=NULL)
{
cout<<"ingrese elemento de corte: ";cin>>corte;
if(buscar(arbol,corte))
{
if(arbol->valor==corte)
arbol=NULL;
else
podar(arbol,corte);
cout<<"el arbol fue podado con exito";
}
else
cout<<"elemento no esta en el arbol";
}
else
{
cout<<"el arbol no tiene elementos";
}
getch();
break;
}//fin case 9
case 10:{
if(arbol!=NULL)
{
arbol=NULL;
cout<<"el arbol fue talado con exito";
}
else
{
cout<<"el arbol no tiene elementos";
}
getch();
break;
}//fin case 10
case 11:{
elem_d_i(arbol);
getch();
break;
}
case 12:{
elem_d_d(arbol);
getch();
break;
}
case 13:{
if(arbol!=NULL)
{
cout<<"el menor elemento de los mayores sera: "<<subarbol(arbol);
}
else
{
cout<<"el arbol no tiene elementos";
}
getch();
break;
}
}//fin switch
clrscr();
}while(opc!= 0);
}//fin main.
/*************************** funciones **************************/
void inserta(ABB &arbol,int x)
{
if(arbol==NULL)
{
arbol=new(struct nodo);
arbol->valor=x;
arbol->izq=NULL;
arbol->der=NULL;
}
else
{
if(x<arbol->valor)
{
inserta(arbol->izq,x);
}
else
if(x>arbol->valor)
{
inserta(arbol->der,x);
}
}
}
void preorden(ABB arbol)
{
if(arbol!=NULL)
{
cout<<arbol->valor<<" ";
preorden(arbol->izq);
preorden(arbol->der);
}
}
void enorden(ABB arbol)
{
if(arbol!=NULL)
{
enorden(arbol->izq);
cout<<arbol->valor<<" "<<endl;
enorden(arbol->der);
}
}
void postorden(ABB arbol)
{
if(arbol!=NULL)
{
postorden(arbol->izq);
postorden(arbol->der);
cout<<arbol->valor<<" ";
}
}
void verarbol(ABB arbol, int nro)
{
int i;
if(arbol==NULL)return;
verarbol(arbol->der,nro+1);
for(i=0;i<nro;i++)
cout<<" ";
cout<<arbol->valor<<endl;
verarbol(arbol->izq,nro+1);
}
int buscar(ABB arbol, int bus)
{
ABB A1;
A1=arbol;
while(A1!=NULL)
{
if(bus < A1->valor)
{
A1=A1->izq;
cout<<A1->valor;
}
else
if(bus > A1->valor)
{
A1= A1->der;
cout<<A1->valor;
}
else
return 1;
}
return -1;
}
int buscarmenor(ABB arbol)
{ABB anterior;
int menor,segmenor;
while(arbol->izq!=NULL)
{ anterior=arbol;
arbol=arbol->izq;
}
segmenor=anterior->valor;
cout<<"El segundo menor sera:"<<segmenor<<endl;
menor=arbol->valor;
return menor;
}
int buscarmayor(ABB arbol)
{ ABB anterior;
int mayor,segmayor;
while(arbol->der!=NULL)
{anterior=arbol;
arbol=arbol->der;
}
segmayor=anterior->valor;
cout<<"El segundo mayor sera:"<<segmayor<<endl;
mayor=arbol->valor;
return mayor;
}
void elem_d_i(ABB arbol)
{
int contd=0;
int conti=0;
if(arbol!=NULL)
{
while(arbol->izq!=NULL)
{
arbol=arbol->izq;
conti=conti+1;
}
}
cout<<"TOTAL DE ELEMETOS A LA IZQUIERDA"<<conti;
}
void elem_d_d(ABB arbol)
{
int contd=0;
int conti=0;
if(arbol!=NULL)
{
while(arbol->der!=NULL)
{
arbol=arbol->der;
contd=contd+1;
}
}
cout<<"TOTAL DE ELEMETOS A LA DERECHA"<<contd;
}
void podar(ABB& A1,int corte)
{
while(A1!=NULL)
{
if(corte<A1->valor)
if(A1->izq->valor==corte)
{
A1->izq=NULL;
break;
}
else
A1=A1->izq;
else
if(A1->der->valor==corte)
{
A1->der=NULL;
break;
}
else
A1=A1->der;
}//fin while
}
int subarbol(ABB arbol)
{
ABB q;
int menor;
while(arbol->der!=NULL)
{
q=arbol;
if(q->izq!=NULL)
q=arbol->izq;
}
menor=q->valor;
return menor;
}
Continuando con Arbol binario (ABB), les comparto el siguiente post: Pre orden, mostrar hojas, ver arbol, buscar elemento
