ARBOL GENEALOGICO

                 

archivo de árbol familiar

Ejemplo de arbol binario


opcion 2:

ARBOLES

Definicion:

Estructura no lineal y dinámica de datos. Dinámica: puede cambiar durante la ejecución de un programa. No lineal: a cada elemento del árbol pueden seguirle varios elementos. Están formados por un conjunto de nodos y un conjunto de aristas que conectan pares de nodos.

Nodo hijo: cualquiera de los nodos apuntados por uno de los nodos del árbol.

Nodo padre: nodo que contiene un puntero al nodo actual.

Posición dentro del árbol:

Nodo raíz: nodo que no tiene padre. Este es el nodo que usaremos para referirnos al árbol.

Nodo hoja: nodo que no tiene hijos.

Nodo rama: aunque esta definición apenas la usaremos, estos son los nodos que no pertenecen a ninguna de las dos categorías anteriores.

Operaciones:

• Añadir o insertar elementos.
• Buscar o localizar elementos.
• Borrar elementos.
• Moverse a través del árbol.
• Recorrer el árbol completo.

Existen dos recorridos típicos para listar los nodos de un árbol:  primero en profundidad y primero en anchura.
En el primer caso, se listan los nodos expandiendo el hijo actual de cada nodo hasta llegar a una hoja, donde se vuelve al nodo anterior probando por el siguiente hijo y así sucesivamente.
En el segundo, por su parte, antes de listar los nodos de nivel n + 1 (a distancia n + 1 aristas de la raíz), se deben haber listado todos los de nivel n. Otros recorridos típicos del árbol son preorden, postorden e inorden:
Recorrido en preorden, también llamado orden previo consiste en recorrer en primer lugar la raíz y luego cada uno de los hijos en orden previo.
Recorrido en inorden, también llamado orden simétrico (aunque este nombre sólo cobra significado en los árboles binarios) consiste en recorrer en primer lugar A1, luego la raíz y luego cada uno de los hijos en orden simétrico.
Recorrido en postorden, también llamado orden posterior consiste en recorrer en primer lugar cada uno de los hijos en orden posterior y por último la raíz.

Tipos de árboles

• Árboles Binarios
• Árbol de búsqueda binario auto-balanceable
• Árboles AVL
• Árboles Rojo-Negro
• Árbol AA
• Árboles Multicamino
• Árboles B (Arboles de búsqueda multicamino autobalanceados)
• Árbol-B+
• Árbol-B*

Aplicaciones

• Representación de datos jerárquicos.
• Ayuda para realizar búsquedas en conjuntos de datos

Bibliografias:
http://es.wikipedia.org/wiki/%C3%81rbol_(inform%C3%A1tica)
http://c.conclase.net/edd/?cap=006b#6_3

PILA CON ARREGLOS EN C#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int tam;
            Console.WriteLine("capture el tamaño de la pila");
            tam = int.Parse(Console.ReadLine());
            string[] pila = new string[tam];
            string Elemento = string.Empty;
            string op = string.Empty;

            do
            {
                Console.Write("\n\nMenú  \n 1)Meter elemento a la pila  \n 2)Muestra pila \n 3)Suprime elemento de la cima \n 0)Salir \n\n");

                op = Console.ReadLine();

                switch (op)
                {
                    case "1":
                        Console.Write("INGRESAR VALORES A LA PILA \n");
                        Console.Write("Escriba el dato a ingresar a la pila:");
                        Elemento = Console.ReadLine();

                        while (string.IsNullOrEmpty(Elemento))
                        {
                            Console.Write("Ingrese un valor válido a la pila:");
                            Elemento = Console.ReadLine();
                        }

                        if (estaLlena(pila))
                        {
                            Console.Write("La pila está llena, imposible agregar nuevo valor \n");
                        }
                        else
                        {
                            Meter(pila, Elemento);
                        }

                        break;

                    case "2":
                        Console.Write("MOSTRAR PILA \n");

                        if (esVacia(pila))
                        {
                            Console.Write("La pila está vacia \n");
                        }
                        else
                        {
                            Mostrar(pila);
                        }
                        break;


                    case "3":
                        Console.Write("SUPRIME ELEMENTO DE LA PILA \n");

                        if (esVacia(pila))
                        {
                            Console.Write("La pila tiene espacio en la disponible \n");
                        }
                        else
                        {
                            Suprime(pila);
                            Console.Write("El elemento de la cima suprimido");
                        }
                        break;

                    default:
                        Console.Write("saliendo");
                        break;
                }
            } while (!op.Equals("0"));
        }
        static public bool esVacia(string[] _pila)
        {
           bool fl = true;

            for (int i = _pila.Length - 1; i >= 0; i--)
            {
                if (_pila[i] != null)
                {
                    fl = false;
                    break;
                }
            }
            return fl;
        }

        static public bool estaLlena(string[] _pila)
        {
            bool fl = false;
            int count = 0;

            for (int i = _pila.Length - 1; i >= 0; i--)
            {
                if (_pila[i] != null)
                {
                    count += 1; ;
                }
            }

            if (count == _pila.Length) { fl = true; }

            return fl;
        }
        static public bool Suprime(string[] _pila)
        {
            bool fl = false;

            for (int i = _pila.Length - 1; i >= 0; i--)
            {
                if (_pila[i] != null)
                {
                    _pila[i] = null;
                    fl = true;
                    break;
                }
            }

            return fl;
        }
        static public bool Meter(string[] _pila, string _elemento)
        {
            bool fl = false;

            for (int i = _pila.Length - 1; i >= 0; i--)
            {
                if (_pila[i] != null)
                {
                    _pila[i + 1] = _elemento;
                    fl = true;
                    break;
                }
                else if (_pila[i] == null && i == 0)
                {
                    _pila[i] = _elemento;
                    fl = true;
                   break;
                }
           }
           return fl;
       }
        static public void Mostrar(string[] _pila)
        {
            for (int i = _pila.Length - 1; i >= 0; i--)
            {
                if (_pila[i] != null)
                {
                    Console.Write(_pila[i] + "\n");
                }
            }

        }
    }
}



           
           

PILA DINÁMICA EN JAVA

package estructuradedatospilas;

import java.util.ArrayList;

import java.util.Iterator;

import java.util.LinkedList;

import java.util.List;

import java.util.Scanner;

public class pilas {

     public static void main(String[] args) {

        Scanner leer = new Scanner (System.in);

        int num;

        int op;

        LinkedList pila = new LinkedList();

        do{

            System.out.println("\t menu \t");

            System.out.println("operaciones con pilas");

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

            System.out.println("2.-insertar al final");

            System.out.println("3.-borrar al final");

            System.out.println("4.-mostrar la pila");

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

            System.out.println("\n");

            System.out.println("elija la operacion que desee");

            op=leer.nextInt();

            switch (op){

                case 1:

                    System.out.println("inserte numero");

                    num=leer.nextInt();

                    pila.addFirst(num);

                    break;

                case 2:

                        System.out.println("inserte numero");

                        num=leer.nextInt();

                        pila.addLast(num);

                        break;

                case 3:

                    System.out.println("se borra el nodo final");

                    pila.removeLast();

                    break;

                case 4:

                    System.out.println("la pila es la siguiente");

                    List pila2= new ArrayList(pila);

                    Iterator it = pila2.iterator();

                    while (it.hasNext()){

                        System.out.println(it.next()+"");

                    }

                    break;

                    case 5:

                     System.out.println("al rato");

                     break;

            }

        }

        while (op !=5);   }            }

CÓDIGO DE PILA

package javaapplication;
import java.util.Scanner;

public class Main {

      public static void main(String[] args) {
     
     int dato;
        int pila[] = new int[5];
        Scanner Captura = new Scanner(System.in);
        for(int tope = 0; tope <= 4; tope++){
            System.out.println("Proporcione datos para la pila");
            dato = Captura.nextInt();
            pila[tope] = dato;
        }
        for(int tope = 4; tope >= 0; tope--){
            System.out.println("La pila tiene los siguientes datos: " + pila[tope]);
        }
        }
    }

COLAS

Definición:
Una cola es un tipo especial de lista abierta en la que sólo se pueden insertar nodos en uno de los extremos de la lista y sólo se pueden eliminar nodos en el otro. Además, como sucede con las pilas, las escrituras de datos siempre son inserciones de nodos, y las lecturas siempre eliminan el nodo leído.

Este tipo de lista es conocido como lista FIFO (First In First Out), el primero en entrar es el primero en salir.

tipos

Existen tres tipos de colas:

• cola lineal (sencilla)
• cola circular
• cola doble (bicola)

Cola sencilla

La cola lineal es un tipo de almacenamiento creado por el usuario que trabaja bajo la técnica FIFO (primero en entrar primero en salir). Las colas lineales se representan gráficamente de la siguiente manera:

 

Las colas lineales tienen un grave problema, como las extracciones sólo pueden realizarse por un extremo, puede llegar un momento en que el apuntador sea igual al máximo número de elementos en la cola, siendo que al frente de la misma existan lugares vacíos, y al insertar un nuevo elemento nos mandará un error de overflow (cola llena).

Cola circular

En este tipo de cola existe un apuntador desde el último elemento al primero de la cola. 

La representación gráfica de esta estructura es la siguiente: 

La condición de vacío en este tipo de cola es que el apuntador F sea igual a cero.

Las condiciones que debemos tener presentes al trabajar con este tipo de estructura son las siguientes: 

• Over flow, cuando se realice una inserción. 

• Under flow, cuando se requiera de una extracción en la cola. 

• Vació

Cola doble o bicola

Esta estructura es una cola bidimensional en que las inserciones y eliminaciones se pueden realizar en cualquiera de los dos extremos de la bicola. Gráficamente representamos una bicola de la siguiente manera: 

Existen dos variantes de la doble cola: 

• Doble cola de entrada restringida. 

• Doble cola de salida restringida. 

La primer variante sólo acepta inserciones al final de la cola, y la segunda acepta eliminaciones sólo al frente de la cola

Operaciones

Las colas sólo permiten añadir y leer elementos:

• Añadir: Inserta un elemento al final de la cola.
• Leer: Lee y elimina un elemento del principio de la cola.

código de colas en java

class ColaArreglo{

Object[] ArregloCola;

int frente=0,fondo=0,Num_elem;

int Cant_elem=5;

//Constructor

ColaArreglo(){

ArregloCola=new Object[Cant_elem];

frente=0;

fondo=-1;

Num_elem=0;

}

//Encola un elemento

public void Encolar(Object x){

if(fondo==-1){

fondo++;

ArregloCola[fondo]=x;

}

else{

fondo++;

if(fondo==Cant_elem)

System.out.println("No hay campo");

else

ArregloCola[fondo]=x;

}

}

//Desencola un elemento

public void Desencolar(){

if(VaciaCola())

System.out.println("No hay Elementos");

else{

for(int i=frente;i<fondo; i++){

ArregloCola[i]=ArregloCola[i+1];

}

ArregloCola[fondo]=null;

fondo--;

}

}

//Retorna si esta vacia la cola

public boolean VaciaCola(){

return (fondo<frente);

}

//Imprime al cola

public void Imprimir(){

int i=0;

System.out.print("La Cola es: ");

while(i<ArregloCola.length){

System.out.print(ArregloCola[i]+" ");

i++;

}

System.out.println("");

System.out.println("");

}

}

class ColasA{

public static void main(String[]args){

ColaArreglo nuevo=new ColaArreglo();

nuevo.Encolar("9");

nuevo.Encolar("10");

nuevo.Encolar("11");

nuevo.Encolar("12");

nuevo.Encolar("13");

nuevo.Desencolar();

nuevo.Encolar("1133");

nuevo.Imprimir();

    }

}

videos de colas

Fuentes:

http://c.conclase.net/edd/?cap=003b

estructura de datos

PILAS

                                                                Difinicion:

Las pilas son otro tipo de estructura de datos lineales, las cuales presentan restricciones en cuanto a la posición en la cual pueden realizarse las inserciones y las extracciones de elementos.

Una pila es una lista de elementos en la que se pueden insertar y eliminar elementos sólo por uno de los extremos.

Las pilas solo tiene 2 operaciones, Push(Inserción) y Pop(Eliminación) la cual solo se puede efectuar por un extremo llamado Top. Sin Embargo se le pueden aplicar todas las operaciónes al igual que a las listas.

Operaciones:

Push:  Es simplemente el método por el cual va agregando un Dato nuevo a la Pila tomando en cuenta la 

capacidad Máxima (Max) de almacenar un dato.

Pop: Es simplemente el método por el cual va sacando el ultimo Dato de la Pila, basándose únicamente en el Top.

Recorrido Ya que las pilas son LIFO(Last in  First Out) el Recorrido se hace sacando el ultimo dato que se inserto hasta que no encuentre ningún otro. 

Detalle: Apuntador toma el Top, después ve si la condición cumple para efectuar un Ciclo mientras Apuntador sea diferente de Nulo, si cumple lo que hace es que despliega el contenido de la Pila(Pila[Apuntador]), después Apuntador se le resta 1. Este proceso se repite hasta que Apuntador sea igual Nulo(Cuando llega a este punto la Pila ya fue Recorrida).

Algoritmo:

Recorrido(Pila, Top) 

Apuntador ←- Top 

Repetir mientras Apuntador &ne; Nulo 

Imprimir Pila[Apuntador] 

Apuntador ←- Apuntador - 1 

Fin del ciclo 

Salir 

<>

Búsqueda 

Definición: 

Este método usa el recorrido para encontrar Elemento y desplegar un mensaje si la búsqueda es exitosa. 

Detalle: 

El algoritmo compara para determinar si la Pila tiene algún dato, si no simplemente desplegara Lista Vacía y saldrá. De otra manera hará un Recorrido y comparara con cada uno de los Datos de la Pila hasta encontrar el dato que desea buscar. Si lo encuentra desplegara “El Dato fue encontrado” de otra manera “El Dato no se encontró”. 

Algoritmo: 

Busqueda(Pila, Top, Elemento) 

Si Top &ne; Nulo 

Apuntador ←- Top 

Repetir mientras Apuntador &ne; Nulo 

Si Pila[Apuntador] = Elemento 

Imprimir “El Dato fue encontrado” y Salir 

Apuntador ←- Apuntador - 1 

Fin del ciclo 

Imprimir “El Dato no se encontró” 

Si no: 

Imprimir “Pila Vacía” 

Salir 

Eliminacion:

Definición:

Este método busca un Dato dentro de la pila y lo elimina.

Detalle:

El algoritmo compara para determinar si la Pila tiene algún dato, si no simplemente desplegara Pila Vacía y saldrá. De otra manera hará un Recorrido y comparara con cada uno de los Datos de la Pila hasta encontrar el dato que desea eliminar, mientras hace esto copia cada uno de los datos a un arreglo Temp para cuando encuentre el Dato regresar esos valores a la Pila. Si lo encuentra desplegara “Eliminado el Dato” y le restara 1 a Top, de otra manera “El Dato no encontrado”.

Algoritmo:

Borrar(Pila, Temp, Top, Elemento)

Si Top &ne; Nulo

Apuntador1 ←- Top

Repetir mientras Apuntador1 &ne; Nulo

Si Pila[Apuntador1] = Elemento

Imprimir “Eliminando el Dato…”

Repetir mientras Apuntador2 &ne; Nulo

Pila[Apuntador1]=Temp[Apuntador2]

Fin del ciclo

Top ←- Top - 1 y Salir

Si No:

Temp[Apuntador2] ←- Pila[Apuntador1]

Apuntador1 ←- Apuntador1 - 1

Apuntador2 ←- Apuntador2 + 1

Fin del ciclo

Imprimir “Dato no encontrado”

Si no:

Imprimir “Pila Vacía”

Salir

aplicaciones

• Un ejemplo típico de pila lo constituye un montón de platos: Cuando se quiere introducir un nuevo plato, éste se coloca en la posición más accesible, encima del último plato. Cuando se toma un  plato, éste se extrae, igualmente, del punto más accesible, el último que se ha introducido. 

• Si somos más estrictos, otro ejemplo sería una caja llena de libros. Sólo podemos ver cuál es el libro que está más arriba en la caja, y si ponemos o tomamos un libro, sólo podremos actuar sobre este primer libro. No podemos siquiera saber el número total de libros guardados en la pila. Sólo sabremos el número de elementos de la pila de libros si previamente los sacamos hasta vaciar la caja.

• Otro ejemplo natural de la aplicación de la estructura pila aparece durante la ejecución de un programa de ordenador, en la forma en que la máquina procesa las llamadas a los procedimientos. Cada llamada a un procedimiento (o función) hace que el sistema almacene toda la información asociada con ese procedimiento (parámetros, variables, constantes, dirección de retorno, etc...) de forma independiente a otros procedimientos y permitiendo que unos procedimientos puedan invocar a otros distintos (o a si mismos) y que toda esa información almacenada pueda ser recuperada convenientemente cuando corresponda. Como en un procesador sólo se puede estar ejecutando un procedimiento, esto quiere decir que sólo es necesario que sean accesibles los datos de un procedimiento (el último activado, el que está en la cima).

videos relacionados

Código de pila en java

fuentes
http://www.programacionfacil.com/estructura_de_datos:pilas
http://www.lcc.uma.es/~lopez/modular/tads/pilas_colas.pdf