MI ÁRBOL

public class Arbol {
class Nodo
{
int info;
Nodo izq, der;
}
Nodo raiz;
int cant;
int altura;
public Arbol() {
raiz=null;
}
public void insertar (int info) {
if (!existe(info)) {
Nodo nuevo;
nuevo = new Nodo ();
nuevo.info = info;
nuevo.izq = null;
nuevo.der = null;
if (raiz == null)
raiz = nuevo;
else {
Nodo anterior = null, reco;
reco = raiz;
while (reco != null) {
anterior = reco;
if (info < reco.info)
reco = reco.izq;
else
reco = reco.der;
}
if (info < anterior.info)
anterior.izq = nuevo;
else
anterior.der = nuevo;
}
}
}
public boolean existe(int info) {
Nodo reco=raiz;
while (reco!=null) {
if (info==reco.info)
return true;
else
if (info>reco.info)
reco=reco.der;
else
reco=reco.izq;
}
return false;
}
private void imprimirEntre (Nodo reco) {
if (reco != null) {
imprimirEntre (reco.izq);
System.out.print(reco.info + " ");
imprimirEntre (reco.der);
}
}
public void imprimirEntre () {
imprimirEntre (raiz);
System.out.println();
}

private void cantidad(Nodo reco) {
if (reco!=null) {
cant++;
cantidad(reco.izq);
cantidad(reco.der);
}
}
public int cantidad() {
cant=0;
cantidad(raiz);
return cant;
}
private void cantidadNodosHoja(Nodo reco) {
if (reco!=null) {
if (reco.izq==null && reco.der==null)
cant++;
cantidadNodosHoja(reco.izq);
cantidadNodosHoja(reco.der);
}
}
public int cantidadNodosHoja() {
cant=0;
cantidadNodosHoja(raiz);
return cant;
}
private void imprimirEntreConNivel (Nodo reco,int nivel) {
if (reco != null) {
imprimirEntreConNivel (reco.izq,nivel+1);
System.out.print(reco.info + " ("+nivel+") - ");
imprimirEntreConNivel (reco.der,nivel+1);
}
}
public void imprimirEntreConNivel () {
imprimirEntreConNivel (raiz,1);
System.out.println();
}
private void retornarAltura (Nodo reco,int nivel) {
if (reco != null) {
retornarAltura (reco.izq,nivel+1);
if (nivel>altura)
altura=nivel;
retornarAltura (reco.der,nivel+1);
}
}
public int retornarAltura () {
altura=0;
retornarAltura (raiz,1);
return altura;
}
public void mayorValorl() {
if (raiz!=null) {
Nodo reco=raiz;
while (reco.der!=null)
reco=reco.der;
System.out.println("Mayor valor del įrbol:"+reco.info);
}
}
public void borrarMenor() {
if (raiz!=null) {
if (raiz.izq==null)
raiz=raiz.der;
else {
Nodo atras=raiz;
Nodo reco=raiz.izq;
while (reco.izq!=null) {
atras=reco;
reco=reco.izq;
}
atras.izq=reco.der;
}
}
}
public static void main (String [] ar)
{
Arbol abo = new Arbol ();
abo.insertar (100);
abo.insertar (50);
abo.insertar (25);
abo.insertar (75);
abo.insertar (150);
System.out.println ("Impresion entreorden: ");
abo.imprimirEntre ();
System.out.println ("Cantidad de nodos del įrbol:"+abo.cantidad());
System.out.println ("Cantidad de nodos hoja:"+abo.cantidadNodosHoja());
System.out.println ("Impresion en entre orden junto al nivel del nodo.");
abo.imprimirEntreConNivel();
System.out.print ("Artura del arbol:");
System.out.println(abo.retornarAltura());
abo.mayorValorl();
abo.borrarMenor();
System.out.println("Luego de borrar el menor:");
abo.imprimirEntre ();
}
}

ARBOL BINARIO

public class CArbolBinarioDeBusqueda extends CArbolBinB
{
public int comparar(Object obj1, Object obj2)
{
String str1=new String(((CDatos)obj1).obtenerNombre());
String str2=new String(((CDatos)obj2).obtenerNombre());
return str1.compareTo(str2);
}

public void procesar(Object obj)
{
String nombre=new String(((CDatos)obj).obtenerNombre());
Double nota=((CDatos)obj).obtenerNota();
System.out.println(nombre+" "+nota);
}

public void visitarInorden()
{
inorden(null, true);
}

public void visitarPosorden()
{
posorden(null, true);
}

public void visitarPreorden()
{
preorden(null, true);
}
}

Árbol binario

la mayoría de los árboles binarios son de búsqueda

Un árbol binario no vacío, de raíz R, es un árbol binario de búsqueda si:
En caso de tener subárbol izquierdo, la raíz R debe ser mayor que el valor máximo almacenado en el subárbol izquierdo, y que el subárbol izquierdo sea un árbol binario de búsqueda.
En caso de tener subárbol derecho, la raíz R debe ser menor que el valor mínimo almacenado en el subárbol derecho, y que el subárbol derecho sea un árbol binario de búsqueda.

h
LCI=Σni * i
i=1

i=nivel del árbol
h=altura
ni=número de nodos en el nivel i
Lci=número de nivel*número de nodos+número de nivel*número de nodos...
ejemplo(1*1+2*2+4*3+4*4=33)


Árbol extendido:
Aquel en el que el número de hijos de cada nodo es igual al grado del árbol, que no cumplir con esta caracteristica se deben incorporar nodos especiales.

Nodos especiales:
Reemplazan las ramas vacías o nulas.

LCE:
Es la suma de todos los nodos especiales.



Calcular la longitud de camino externo:
n+1
LCE=Σnei* i i=2

i=Nivel del árbol
h=altura
nei=número de nodos especiales

Aplicaciones:
Formulas matemáticas
Circuitos electricos
árbol genealogico


Propiedades:
Se dice que todos los nodos que son descendientes directos hijos de un mismo nodo padre, son hermanos.
Todo nodo que no tiene ramificaciones hijos, se conoce con el nombre de terminal u hoja.


Grado:
Número de desciendentes directos de un determinado nodo.


Grado de árbol:
Es el máximo grado de todos los nodos del árbol.

Nivel:
Es el número de arcos que pueden ser recorridos para llegar a un determinado nodo.
Por definición raíz tiene nivel 1.
Longitud de camino interno:
Es la suma de longitudes de camino de todos los nodos del árbol

ARBOLES

un árbol es una estructura de datos ampliamente usada que imita la forma de un árbol (un conjunto de nodos conectados).

Un nodo es la unidad sobre la que se construye el árbol y puede tener cero o más nodos hijos conectados a él. Se dice que un nodo Aes padre de un nodo B  si existe un enlace desde A  hasta B  (en ese caso, también decimos que B  es hijo de A). Sólo puede haber un único nodo sin padres, que llamaremos raíz. Un nodo que no tiene hijos se conoce como hoja. Los demás nodos (tienen padre y uno o varios hijos) se les conoce como rama.

COLA ESTÁTICA

public class colaestatica {

public static int op;

public static int tope;

    int cola[]= new int[10];

    public void insertar(){

        if(tope==10)

            System.out.println("Cola llena");

        else

    {

       for(int i=0;i<cola.length;i++ ){

        System.out.println("Proporciona el dato para la Cola");

        System.out.println("dato " + tope);

        Scanner cap= new Scanner(System.in);

        cola[tope]=cap.nextInt();

        tope++;

    } }

}

    public void imprimir(){

       if(tope>0){

            for(int topeL=0;topeL<10;topeL++){

                System.out.println("\n\n" + cola [topeL]);

                System.out.println(tope);

            }

        }

        else

            System.err.println("cola vacia no hay nada que mostrar");

    }

    public void eliminar(){

        if(tope<0){

            System.out.println("cola vacia");

        }

        else

                for(int topeL=0;topeL<10;topeL++){

                     cola[topeL]=0;

            }

            }

    public static void main(String[] args) {

       cola_estatica p = new cola_estatica();

       String r;

       Scanner cap1=new Scanner(System.in);

       Scanner cap=new Scanner(System.in);

       tope=0;

       do{

           System.out.println("Menu principal:\n¿Que desea hacer con la pila?");

           System.out.println("1.-insertar");

           System.out.println("2.- eliminar");

           System.out.println("3.- imprimir");

           System.out.println("4.-salir");

           op=cap.nextInt();

           switch(op){

               case 1: p.insertar();break;

               case 2:p.eliminar();break;

               case 3:p.imprimir();break;

               case 4:break; default:

                   System.out.println("opcion no valida");break;

           }

    }while(op!=4);

}}

Lista

Consiste en una secuencia de nodos, en los que se guardan campos de datos arbitrarios y una o dos referencias (punteros) al nodo anterior o posterior. El principal beneficio de las listas enlazadas respecto a los array convencionales es que el orden de los elementos enlazados puede ser diferente al orden de almacenamiento en la memoria o el disco, permitiendo que el orden de recorrido de la lista sea diferente al de
almacenamiento.

PROGRAMA PILA ESTATICA


public class Pila_Estatica {


public static int op;

public static int tope;

int pila[]= new int[10];

public void insertar(){




if(tope==10)

System.out.println("Pila llena");

else

{

System.out.println("Proporciona el dato para la pila");

System.out.println("dato" + tope);

Scanner cap= new Scanner(System.in);

pila[tope]=cap.nextInt();

tope++;

}

}

public void imprimir(){


if(tope>=10){

for(int topeM=tope-1;topeM>=0;topeM--){

System.out.println("\n\n" + pila [topeM]);

}

}

else

System.err.println("pila vacia no hay nada que mostrar");

}



public void eliminar(){



if(tope<0){

System.out.println("pila vacia");

}

else

if(tope==10){//Esto se usa cuando la pila esta totalmente llena,

//ya que se incremento en insertar y quedo en 10, de lo contrario

//noz arrojara un error de array

tope--;

pila[tope]=0;

tope--;//se vuelve a decrementar para que este en la pocision correcta, porque

//tenia un numero de mas

}

else{

pila[tope]=0;

tope--;

}

}





MAIN







public static void main(String[] args) {

Pila_Estatica p = new Pila_Estatica();

String r;

Scanner cap1=new Scanner(System.in);

Scanner cap=new Scanner(System.in);

tope=0;

do{

System.out.println("Menu principal:\n¿Que desea hacer con la pila?");

System.out.println("1.-insertar");

System.out.println("2.- eliminar");

System.out.println("3.- imprimir");

System.out.println("4.-salir");

op=cap.nextInt();

switch(op){

case 1:

p.insertar(); break;

case 2:

p.eliminar(); break;

case 3:

p.imprimir(); break;

case 4:

System.out.println("Adios!!!!"); break;

default:

System.out.println("Selecion erronea, teclea otra opcion!!!");

}

System.out.println("deseas Realizar Otra Operacion con tu pila? /(S/N)");

r=cap1.nextLine();

} while(r.equalsIgnoreCase("S"));

}

}

Implementacion mediante lista enlazada

Para hacer la implementacion se utilizara una LISTA CIRCULAR sin cabecera.
La cola estará inicialmente vacía, cuando se añaden elementos el puntero que mantiene la cola apuntada al ultimo elemento introducido, y el siguiente elemento al que apunta es al primero que esta esperando para salir.

¿Qué implementación es mejor, arrays o listas?

Al igual que con las pilas, la mejor implementación depende de la situación particular. Si se conocen de antemano el número de elementos entonces lo ideal es una implementación por arrays. En otro caso se recomienda el uso de lista enlazada circular.

COLA DOBLE 

Es un tipo de cola especial que permiten la inserción y eliminación de elementos de ambos extremos de la cola, se puede representarse de un vector o de dos indices, siendo su representación mas frecuente una lista circular doblemente enlazada.

cola circular

Es una estructura de datos de forma circular Los elementos pueden consultarse añadirse y eliminarse únicamente desde la cabeza del anillo que es una posición distinguida. Existen dos operaciones de rotaciones, una en cada sentido, de manera que la cabeza del anillo pasa a ser el elemento sucesor, o el predecesor, respectivamente, de la cabeza actual.






EJEMPLO:


La cola es una estructura de datos, donde la inserción del ítem se ase en un final ( final de la cola) y la recuperación borrado de elementos se ase otro al final(el inicio de la cola). como el primer elemento insertado es el primero en ser recuperado.