Tarea N°3
· En forma individual,
investigar e implementar en Java un algoritmo de búsqueda. Se recomienda
que desarrolle un programa que permita crear un árbol binario,
recorrerlo en diferente orden, y haber búsqueda de un
elemento dentro del árbol. También puede usar otra
estructura de datos.
· Publicar en su blog
y responder esta entrada, indicando su nombre y la url de su tarea en el blog
de su grupo.
Arbol Binario
Un árbol binario es una estructura de datos en la que los
nodos siempre tienen nodos hijos, tanto a su izquierda como su derecha, no
pueden tener mas de dos hijos cada nodo, si un nodo no
almacena ningún dato, es decir es null, se le llama nodo externo, en
otro caso a este nodo hijo se le llamara nodo interno, uno de los usos comunes
de un árbol binario es para búsquedas.
A continuacion se muestra un programa de árbol binario en
java, compuesto por tres clases una llamada nodo en la cual se aloja la
estructura de datos, otra llamada árbol la cual aloja
los métodos a utilizar y una llamada main que sera la clase principal
que aloje los métodos principales.
CLASE NODO
class nodo
{
int dato;
nodo der;
nodo izq;
nodo(int dat)
{
this.dato=dat;
this.der=null;
this.izq=null;
}
}
CLASE ARBOL
public class arbol
{
nodo
raiz=null;
public boolean tieneraiz()
{
if(raiz==null)
return false;
else return true;
}
public arbol
alta(int dat)
{
if(!tieneraiz())
{
nodo
nuevo=new nodo(dat);
raiz=nuevo;
}
else
{
boolean izq;
nodo actual=raiz;
while(true)
{
if(actual.dato<dat)
izq=false;
else izq=true;
if(!izq)
{
if(actual.der==null)
{
nodo
nuevo=new nodo(dat);
actual.der=nuevo;
break;
}
else actual=actual.der;
}
else
{
if(actual.izq==null)
{
nodo
nuevo=new nodo(dat);
actual.izq=nuevo;
break;
}
else actual=actual.izq;
}
}
}return this;
}
public boolean baja(int dat)
{
nodo
actual=raiz, anterior=raiz, temp;
while(true)
{
if(actual==null)
break;
if(actual.dato==dat)
break;
anterior=actual;
if(actual.dato<dat)
actual=actual.der;
else actual=actual.der;
}
if(actual==null)
return false;
else
{
if(actual==raiz)
{
temp=actual.izq;
raiz=raiz.der;
anterior=raiz;
}
else
if (anterior.der
== actual)
{
temp=actual.izq;
anterior=actual.der;
}
else
{
temp=actual.izq;
anterior.der=actual.izq;
}
actual=new nodo();
while(actual.izq!=null)
actual=actual.izq;
actual.izq=temp;
return true;
}
}
public void imprimirpreorden()
{
ayudantePreorden(raiz);
}
public void ayudantePreorden(nodo
dat)
{
if(dat==null)
return;
System.out.printf("%d
",dat.dato);
ayudantePreorden(dat.der);
ayudantePreorden(dat.izq);
}
public void impririnorden(nodo
dat)
{
if(dat!=null)
{
impririnorden(dat.izq);
System.out.println("
"+dat.dato);
impririnorden(dat.der);
}
}
}
CLASE MAIN
public class Main {
public static void main(String[]
args) {
java.util.Scanner
leer=new java.util.Scanner(System.in);
arbol x=new arbol();
int z;
System.out.print("Ingrese
el numero de Datos a capturar: ");
z=leer.nextInt();
for(int i=1;
i<=z;i++){
int m;
System.out.println("Ingrese
Dato "+i+": ");m=leer.nextInt();
x.alta(m);
}
System.out.println("Valores
Capturados en PreOrden:");
x.imprimirpreorden();
int q;
System.out.print("\nIngrese
dato a borrar: ");q=leer.nextInt();
x.baja(q);
System.out.println("\nDespues
de borrar el dato "+q+" :");
x.imprimir();
}
}
No hay comentarios:
Publicar un comentario