Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

ARBOLES EN JAVA

No description
by

on 2 October 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of ARBOLES EN JAVA

ARBOLES EN JAVA
Carlos Mauricio Rodriguez Arcila
Bryan Steven Vasquez Alvarez

¿que son arboles?
Un árbol es una estructura no lineal en la que cada nodo puede apuntar a uno o varios nodos.
También se suele dar una definición recursiva: un árbol es una estructura en compuesta por un dato y varios árboles.

NODO HIJO: cualquiera de los nodos apuntados por uno de los nodos del arbol. En el ejemplo L Y M son hijos de G.

NODO PADRE: nodo que contiene un puntero al nodo actual, en el ejemplo el nodo A es padre B, C, D.
Los arboles con los que trabajamos tiene otra caracteristica importante: cada nodo solo puede ser apuntado por otro nodo, es decir, cada nodo solo tendra un padre. Esto hace que estos arboles esten fuertemente jerarquizados, y es lo que en realidad les da la apariencia de arboles.
en cuanto a la posicion dentro del arbol:


RECORRER UN ARBOL
El modo evidente de moverse a través de las ramas de un árbol es siguiendo los punteros, del mismo modo en que nos movíamos a través de las listas.
Esos recorridos dependen en gran medida del tipo y propósito del árbol, pero hay ciertos recorridos que usaremos frecuentemente. Se trata de aquellos recorridos que incluyen todo el árbol.
Hay tres formas de recorrer un árbol completo, y las tres suelen implementar mediante recursividad. En los tres casos se sigue siempre a partir de cada nodo todas las ramas una por una.
ELIMINAR NODOS DE UN ARBOL
El proceso general es muy sencillo en este caso, pero con una importante limitación, solo podemos borrar nodos de hoja:
El proceso seria el siguiente:
1. Buscar el nodo padre del que queremos eliminar.
2. Buscar el puntero del nodo padre que apunta al nodo que queremos borrar.
3. Liberar el nodo.
4. Padre->nodo[i]=NULL;.
Cuando el nodo a borrar no sea un nodo hoja, diremos que hacemos una “poda”, y en ese caso eliminaremos el árbol cuya raíz es el nodo a borrar. Se trata de un procedimiento recursivo, aplicamos el recorrido PostOrden, y el proceso será borrar el nodo.
ARRAYLIST
La clase ArrayList (java.util) es una objeto que actúa como una lista que implemente la interfaz Collection de java. Esta clase permite contener y ordenar objetos, incluso, puede almacenar objetos duplicados. Su tamaño es dinámico, es decir, esta lista crecerá a medida que se inserten en ella mas elementos. Debememos recordar que el índice de un ArrayList empieza en 0 (cero), es decir, el primer elemento del ArrayList tiene como índice el 0.
GRACIAS POR SU ATENCION
PRESENTADO POR:
Carlos Mauricio Rodriguez Arcila
Bryan Steven Vasquez Alvarez
conceptos basicos
de los arboles
NODO RAIZ: nodo que tiene padre. Esto es el nodo que usaremos para referirnos al arbol. En el ejemplo es A.
NODO HOJA: nodo que no tiene hijos. En el ejemplo hay varios F, H, I, K, L, M, N y O.

NODO RAMA: son los nodos que no pertenecen a ninguna de las dos categirias anteriores. En el ejemplo B, C, D, E, G y J.
ORDEN: es el numero potencial de hijos que puede tener cada elemento del arbol. En pocas palabras es como decir que un arbol en el que cada nodo pueda apuntar a otros se le puede llamar ORDEN DE DOS, o si el nodo apunta a tres sera ORDEN DE TRES y haci sucesivamente.

GRADO: el numero de hijos que tiene el elemento con mas hijos dentro del arbol. En el ejemplo del arbol el grados es de tres, por que A y D tienen tres hijos, y no existen elementos con mas de tres hijos.

NIVEL: se define para cada elemento del arbol como la distancia a la raiz, medida en nodos. El nivel de la raiz es ceroy el de sus hijos es uno. Asi sucesivamente en el ejemplo el nodo D tiene un nivel 1, y el nodo G tiene un nivel 2 y el nodo N un nivel 3.

ALTURA: la altura de un arbol se define como el nivel del nodo de mayor nivel. Como cada nodo de un arbol puede considerarse a su vez como la raiz de un arbol, tambien podemos hablar de altura de ramas. El arbol del ejemplo tiene de altura 3, la rama B tiene altura 2, la rama G tiene altura 1, la H cero, etc.

Es importante conservar siempre el nodo raiz ya que es el nodo a partir del cual se desarrolla el arbol, si perdemos este nodo, perderemos el acceso a todo el arbol.

QUE SE DEBE TENER
ENCUENTA
Partiremos del nodo raíz:
RecorrerArbol(raíz);
La función RecorrerArbol, aplicando recursividad, será tan sencilla como invocar de nuevo a la función RecorrerArbol para cada una de las ramas:
Void RecorrerArbol (Arbol a) {
If (a == NULL) return;
RecorrerArbol (a->rama[0];
RecorrerArbol (a->rama[1];
RecorrerArbol (a->rama[2];
}
UN EJEMPLO
PRE-ORDEN
primero se accede a la informacion del nodo, despues al sub arbol izquierdo y despues al derecho.
INORDEN
primero se accede a la informacion del subarbol izquierod, despues a la informacion del nodo, y por ultimo, se accede a la informacion del subarbol izquierdo
POST-ORDEN
se accede a la informacion del subarbol izquierdo, despues a la del subarbol derecho, y por ultimo se accede a la informacion del nodo.
AGREGAR ELEMENTOS
El ArrayList contendrá diversos elementos que debemos gestionar, para agregar elementos se puede hacer de dos formas usando el método add(…) que recibe por parámetro un objeto cualquiera:
1. La primera forma sería insertándolo sin darle una posición específica, entonces, el elemento será agregado al final:

// instanciamos un nuevo ArrayList
ArrayList mi_lista = new ArrayList();

// agregamos el elemento, por defecto lo agregará de último
// si la lista está vacía será el primer elemento
mi_lista.add("elemento 1");
2. La segunda forma sería dándole una posición específica en la lista. Si por alguna razón el vamos a insertar el elemento es una posición donde ya existe un elemento, éste elemento será desplazado a la derecha (junto con todos los demás que estén también a la derecha) para darle campo al elemento que será insertado en dicho índice:

// instanciamos un nuevo ArrayList
ArrayList mi_lista = new ArrayList();

// agregamos el elemento, por defecto lo agregará de último
mi_lista.add(1, "elemento A");
ELIMINAR ELEMENTOS
Para eliminar elementos se dispone del método remove(…) en el cual recibe como argumento el objeto a eliminar o bien, eliminar el elemento conociendo su índice (posición).
Para este ejemplo supongamos que tenemos una clase Persona, que tiene nombre y edad, insertaremos unas cuantas personas en la lista y luego eliminaremos una de ellas usando las dos formas.
Eliminado según su índice en la lista
Persona persona_1 = new Persona("Julian", 20);
Persona persona_2 = new Persona("Bety", 17);
Persona persona_3 = new Persona("Marta", 22);

ArrayList mi_lista = new ArrayList();

// agregamos unos cuantos elementos
mi_lista.add(persona_1);
mi_lista.add(persona_2);
mi_lista.add(persona_3);
// la estructura de a lista ha quedado asi: 0 = [Julian] 1 = [Bety] 2 = [Marta]

// si queremos eliminar a "Betty" por su índice seria asi:
mi_lista.remove(1) // el 1 pertenece al índice o posicion de Betty en la lista
// la estructura de a lista ha quedado asi: 0 = [Julian] 1 = [Marta]
Eliminado según el objeto como argumento
Persona persona_1 = new Persona("Julian", 20);
Persona persona_2 = new Persona("Bety", 17);
Persona persona_3 = new Persona("Marta", 22);

ArrayList mi_lista = new ArrayList();

// agregamos unos cuantos elementos
mi_lista.add(persona_1);
mi_lista.add(persona_2);
mi_lista.add(persona_3);
// la estructura de a lista ha quedado asi: 0 = [Julian] 1 = [Bety] 2 = [Marta]

// si queremos eliminar a "Julian" debemos "enviarle a Juan" de nuevo
mi_lista.remove(persona_1) // se envia la instancia de Juan
// la estructura de a lista ha quedado asi: 0 = [bety] 1 = [Marta]
Full transcript