Arboles en C++

Tengo un proyecto de estructura de datos que no comprendo muy bien, ¿mi proyecto consiste en inserción búsqueda y eliminación de arboles binarios pero tengo que programarlo en c++?, pero la verdad estoy un poco confundido porque nunca había programado arboles y la profesora no nos ha dejado mucha información del tema. Ojala puedas ayudarme o orientarme un poco de como hacerlo gracias y espero tu respuesta.

1 respuesta

Respuesta
1
Claro que te puedo ayudar. Los arboles binarios nacen de un nodo padre y puede tener 2 hijos, a su vez un nodo hijo se puede convertir en padre y puede tener dos hijos, la idea es que no pueden ser más de 2 por eso lo de binario, un hijo no puede tener más de un padre. Esto entonces son una lista con doble enlace la diferencia con las listas doblemente enlazadas es que un puntero va a a la derecha y el otro a la izquierda (gráficamente hablando ya que el computador no reconoce eso) no hay uno de vuelta. Ahora si el árbol binario es ordenado el hijo la izquierda y toda la descendencia que va a la izquierda tiene que ser menor que el padre y la descendencia de la derecha mayor.
Ej:
10 <- padre
/ \
7 15
/ \ / \
5 8 NULL 17
/ \ \
NULL NULL NULL
ese es un ejemplo grafico simple de un arbol binario ordenado.
Ahora ya empiezo con codigo c++.
/*definicion del nodo (estructura del arbol binario)*/
struct nodo{
int info;/*numero de cada elemento del arbol*/
struct nodo *izq ; /*apunta al hijo inquierdo*/
struct nodo *der; /*apunta al nodo derecho*/
}
typedef struct nodo *ptrnodo;
ptrnodo l,a,b,p; /*crea variables del tipo nodo, l sera el que tenga el primer numero*/
/*ahora comienza el manejo del programa, copia esto en un texto si esta desordenado*/
int main()
{
int temporal;
char op;
l=NULL;
do{
cout<<"ing numero: ";
cin>>temporal;
p=new nodo;
p->info=temporal;
p->der=NULL;
p->izq=NULL;
if (l==NULL)
{
l=p;
}
else
{
a=NULL;
a=l;
while(a!=NULL)
{
if(a->info>p->info)
{
if(a->izq!=NULL)
a=a->izq;
else
a->izq=p;
}
if(a->info<p->info)
{
if(a->der!=NULL)
a=a->der;
else
a->der=p;
}
}
}
cout<<"desea ing otro nº s/n: ";
cin>>op;
}while(op=='s');
/*Ya esta listo un ingreso de un arbol binario ordenado,ahora una busqueda*/
a=l;
cout<<"ING Nº A BUSCAR: ";
cin>>temporal;
while(a!=NULL)
{
if(temporal<a->info)
a=a->izq;
else if(temporal>a->der)
a=a->der;
else break;
}
if(a!=NULL)
cout<<"El numero fue encontrado";/*ESTA APUNTADO POR a*/
else cout<<"Numero no esta en el arbol";
/*Ahora el eliminar te lo dejo a ti, aunque te dejo lo que es como una regla de eliminado.
Cuando necesita eliminar un nodo que no tiene hijos solo eliminas y enlazas el ultimo a
NULL (para cerrar ese lado del árbol), si solo tiene un hijo solo enlazas el padre del a
eliminar si es que tiene con el hijo del a eliminar y luego simplemente borras, para eliminar
un árbol con más de 1 hijo es más complicado, en ese caso tienes que buscar el sucesor más cercano
del a eliminar. Bueno espero que te sirva de ayuda, y si tienes una duda me preguntas. Saludos
Enrique Quargnolo*/
return 0;
}
Estupendo! Muchas gracias hermano ahora estoy un poco más claro, me has salvado la vida, voy a finalizar la pregunta ahora para no dejarla pendiente, pero si tengo otra interrogante te la haré llegar gracias por contestarme tan rapido, cada vez me sorprendo más de la calidad de expertos que hay aquí ! Hasta Pronto.. Leslie Giovanni/ [email protected]

Añade tu respuesta

Haz clic para o

Más respuestas relacionadas