ARBOLES

ARBOLES

Estructura jerárquica aplicada sobre una colección de elementos u objetos llamados nodos; uno de los cuales es conocido como raíz.

Tipos de recorridos:

Pre orden: raíz, subárbol izquierdo, y subárbol derecho.

In orden: subárbol izquierdo, raíz, subárbol derecho.

Pos orden: subárbol izquierdo, subárbol derecho, raíz.

ARBOL GENEALOGICO

ARBOL BINARIO

Estructura homogénea, resultado de la concatenación de un elemento tipo T, llamando a raíz, con dos árboles binarios disjuntos, llamados subárbol izquierdo de subárbol derecho.

Arboles distintos

Arboles similares

Arboles equivalentes

Árbol general

Árbol general ---------------- Árbol binario

Enlazar los hijos de cada nodo de forma horizontal (los hermanos).

Relacionar en forma vertical el nodo padre con hijo que se encuentra más a la izquierda. Además, se debe eliminar el vínculo de ese padre con el resto de los hijos.

Rotar el diagrama resultante, aproximadamente 45 grados hacia la izquierda y asi se obtendrá un árbol binario correspondiente.

BOSQUE

Representa un conjunto normalmente ordenado de uno o más árboles generales

CONVERSION DE ARBOL BINARIO

Enlazar en forma horizontal las raíces de los distintos arboles generales

Relacionar los hijos de cada nodo (los hermanos) en forma horizontal.

Enlazar en forma vertical el nodo padre con el hijo que se encuentre mas a la izquierda. Además se debe eliminar el vínculo del padre con el resto de hijos.

Rotar el diagrama resultante aproximadamente 45 grados hacia la izquierda y asi obtendrá el árbol binario correspondiente.

GRAFOS

Está formado por un conjunto de vértices o nodos v que representan a los vértices y un conjunto de arcos, que representan las relaciones entre vértices.

Vértice.- Es la unidad fundamental de la que están formados los grafos.

Arco.- Son las líneas que unen a los nodos en los grafos ya sean dirigidos o no dirigidos.

Camino.- Es el número de arcos que lo forma.

Grafo dirigido:

Son aquellos en el que los nodos están direccionados y son más fáciles de recorrer.

Grafo no dirigido: 

Son aquellos en el que los nodos están unidos por líneas y no tienen dirección.

RECURSIVIDAD

RECURSIVIDAD.

Es aquella propiedad que posee un método por el cual puede llamarse asi mismo.

Un método que tiene sentencias entre las que se encuentran al menos una que llama al propio método.

RECURSIVIDAD

Método 1(….)

{

      ……

     Método1 ();

}

NO RECURSIVIDAD

Método 1() {

………..

}

Método 2(…) {

……

Método 1();

}

APLICACIONES.

La suma de los n primeros números positivos:

5(6)=5(6)+5(5)+5(4)+5(3)+5(2)+5(1)

            SERIE DE FIBONACCI

Esta serie inicia con 1 y 0 y tiene la propiedad que cada elemento es la suma de los 2 elementos anteriores.

Ejemplo

0+1=1

1+1=2

2+1=3

3+2=5

5+3=8

…

Entonces se puede establecer que:

Fibonacci (0)=0

Fibonacci (1)=1

Fibonacci (n)=Fibonacci (n-1)+Fibonacci(n-2)

METODO RECURSIVO

Es un método que se invoca a si mismo de forma directa e indirecta.

Una definición recursiva debe incluir una condición de salida , que se denomina componente base, en el que f(n) se defina directamente para uno o mas valores de n.

Un requisito para que un algoritmo recursivo sea correcto es que no genere una secuencia infinita de llamadas sobre si mismo.

RECURSIVIDAD DIRECTA.

El código de f() contiene una sentencia que invoca a f().

Ejemplo

Método  f(){

Método f();

}

RECURSIVIDAD INDIRECTA.

La recursividad indirecta se da cuando un método llama a otro , que eventualmente terminara llamando de nuevo al primer método.

Ejemplo

Método f(){

Método g();

}

Método g(){

Método f();

}

RECURSION VS ITERACION

Estructura                                   Estructura

Control                                         control

Selección                                      repetitiva

PROGRAMAS

public class fibonacci {

    public int fibonaci (int n, int fibinf, int fibsup)

    {

        Scanner teclado = new Scanner (System.in);

        System.out.println("Ingrese el numero: ");

        n= teclado.nextInt ();

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

        if ((n==0)||(n==1))

        {

            System.out.println("La suma es: "+ n);

            return n;

        }

        fibinf=0;

            fibsup=1;

        for (int i=2; i<n; i++){

            int x;

            x=fibinf;

            fibinf=fibsup;

            fibsup=x+fibinf;

            System.out.println(""+fibsup);

        }

        return (fibsup);

    }

        public static void main(String[] args){

                fibonacci fb = new fibonacci ();

                int n=0, fibinf =0, fibsup = 1;

                fb.fibonaci(n,fibinf, fibsup);

public class factorial {

     public static double n,h;

    public static double factorial(double n){

        if(n==0){

            return 1;}

 else h=1;

        return n*factorial(n-1);

    }

            public static void main(String[] args) {

                System.out.println("¿Cual es el numero? ");

                Scanner cap = new Scanner (System.in);

                n= cap.nextInt();

                if (n==0){

                    System.out.println("\nFactorial: 1");

                }

                factorial f=new factorial();

                f.factorial(n);

                if(h==1){

                    System.out.println("\nFactorial= "+n*factorial (n-1));}

                }

        }

public class Recursividad {

    public boolean positivo(int n){

        if(n<=0)

            return true;

        else

            return negativo(n);

    }

    public boolean negativo(int n){

        if(n<0)

            return false;

        else

            return positivo(n);

    }

    public static void main(String[]args){

        Recursividad rec=new Recursividad();

        Scanner Teclado=new Scanner(System.in);

        int m;

        System.out.println("Ingrese valor");

        m=Teclado.nextInt();

        System.out.println(rec.positivo(m));

    }

}