Datos personales

lunes, 28 de diciembre de 2009

ARBOL BINARIO

Metodo De Arbol binario

es aquel en el cual las ramas de los nodos del arbol estan ordenadas. Los arboles ordenados de grado 2 son de especial interes puesto que representa una dxe las estructiras de datos mas importantes en computacion.
Un arbol binario cada nodo puede tener como maximo dos subarboles y siempre es necesario distinguir entre el subarbol izquierdo y el subarbol derecho.
se define un arbol binario tipo T como una estructura homogenea que es la concatenacion de un elemento de tipo T, llamada raiz, con dos arboles binarios dijuntos, llamados subarbol izquierdo y subarbol derecho de la raiz.

CODIGO:
class NodoArbol{
NodoArbol li,ld;
int dato;

public NodoArbol(int d){
dato=d;
li=ld=null;
}

public synchronized void insertar(int d){

if(d if(li==null){
li=new NodoArbol(d);
}
else{
li.insertar(d);
}
}

if(d>dato){
if(ld==null){
ld=new NodoArbol(d);
}
else{
ld.insertar(d);
}
}

}//fin insertar

public int retornadato(){
return(dato);
}//end retornadato

}

public class Arbol {

private NodoArbol raiz;

public Arbol() {
raiz=null;
}
public NodoArbol retornaraiz(){
return(raiz);
}


public synchronized void insertarNodo(int d){
if(raiz==null){
raiz=new NodoArbol(d);
//primero=raiz;
}
else{
raiz.insertar(d);
}
}//fin insertarNodo

public synchronized String preorden(){
String pre=ayudantepreorden(raiz);
return(pre);
}

private String ayudantepreorden(NodoArbol nodo){
String cadena=new String();
if(nodo!=null){
//return;

//System.out.print(nodo.dato+" ");
cadena=cadena+String.valueOf(nodo.dato+" ");
cadena=cadena+ayudantepreorden(nodo.li);
cadena=cadena+ayudantepreorden(nodo.ld);
}
else{
cadena="";
}
return(cadena);
}

public synchronized String inorden(){
String inor=ayudanteinorden(raiz);
return(inor);
}

private String ayudanteinorden(NodoArbol nodo){
String cadena=new String();
if(nodo!=null){
// return;

cadena=cadena+ayudanteinorden(nodo.li);
cadena=cadena+nodo.dato+" ";
cadena=cadena+ayudanteinorden(nodo.ld);
}
else{cadena="";}
return(cadena);
}

public synchronized String posorden(){
String pos=ayudanteposorden(raiz);
return(pos);
}

private String ayudanteposorden(NodoArbol nodo){
String cadena=new String();
if(nodo!=null){



cadena=cadena+ayudanteposorden(nodo.li);
cadena=cadena+ayudanteposorden(nodo.ld);
cadena=cadena+nodo.dato+" ";
}
else{cadena="";}
return(cadena);
}

public synchronized int altura(NodoArbol R){
NodoArbol p=R;
int altizq=p.li==null ? 1:1+altura(p.li);
int altder=p.ld==null ? 1:1+altura(p.ld);
return(Math.max(altizq,altder));
}//end altura

public synchronized int hojas(NodoArbol R){
NodoArbol p=R;
int hojas=0;
if(p.li==null & p.ld==null){
hojas=1;
}
else{
if(p.li!=null){
hojas=hojas+hojas(p.li);
}
if(p.ld!=null){
hojas=hojas+hojas(p.ld);
}
}
return(hojas);
}//end hojas

public synchronized String ancestros(NodoArbol R,int d){
NodoArbol p=R;

String h=new String();

if (p.dato==d){
return(String.valueOf(" --> "+d));
}//end if

if (d>p.dato){
h=h+" --> "+p.dato+ancestros(p.ld,d);
}
else{
h=h+" --> "+p.dato+ancestros(p.li,d);
}
return(h);
}




}

No hay comentarios:

Publicar un comentario