Arbol binario.
Un arbol es una estructura de datos que emula una estructura de un arbol real. Los arboles tienen los siguientes elementos:
Nodo Raiz: El nodo raiz es aquel que no tiene nodo padre.
Nodos Hoja: Es un nodo que no tiene nodos hijos.
Nodos Internos: Son nodos que tienen al menos un hijo y tienen padre.
Un Arbol Binario de ordenamiento es una estructura de datos que permite almacenar informacion que siempre estara ordenada, por lo que la busqueda de un elemento si el arbol esta bien balanceado (Tiene el mismo peso del lado izquiero que del derecho) tendra un orden (Big-O) de O(log n) .
A continuación puede ver un ejemplo de un arbol binario simple en Java, no tiene balanceo, si necesita implementar uno, este le puede servir.
public class BinaryTree {
private Node root;
class Node {
int element;
Node leftNode;
Node rightNode;
Node parentNode;
public Node() {
super();
}
public Node(int element) {
this();
this.element = element;
}
/**
* Add an element to this tree
* @param element
*/
void addElement(int element) {
if (element > this.element) {
if (rightNode == null) {
rightNode = new Node(element);
rightNode.parentNode = this;
} else {
rightNode.addElement(element);
}
}else {
if (leftNode == null) {
leftNode = new Node(element);
leftNode.parentNode = this;
} else {
leftNode.addElement(element);
}
}
}
}
/**
* Add an element to the tree
* @param element
*/
public void addElement(int element) {
if (root == null)
root = new Node(element);
else
root.addElement(element);
}
public void printInOrder() {
printInOrder(root);
}
private void printInOrder(Node node) {
if (node == null) return;
printInOrder(node.leftNode);
System.out.print(" " + node.element);
printInOrder(node.rightNode);
}
public void printPreOrder() {
printPreOrder(root);
}
private void printPreOrder(Node node) {
if (node == null) return;
System.out.print(" " + node.element);
printPreOrder(node.leftNode);
printPreOrder(node.rightNode);
}
public void printPostOrder() {
printPostOrder(root);
}
private void printPostOrder(Node node) {
if (node == null) return;
printPostOrder(node.leftNode);
printPostOrder(node.rightNode);
System.out.print(" " + node.element);
}
public static void main (String []args) {
int []list = new int [] { 5, 3, 7, 1, 9, 2, 8, 4, 6};
BinaryTree tree = new BinaryTree();
for (int element : list)
tree.addElement(element);
System.out.println("In order: ");
tree.printInOrder();
}
}
Mostrando entradas con la etiqueta Estructuras de datos. Mostrar todas las entradas
Mostrando entradas con la etiqueta Estructuras de datos. Mostrar todas las entradas
lunes, 6 de octubre de 2008
Estructuras de Datos - Lista enlazada Simple
La Lista enlazada simple es una estructura de datos que crece de manera dinamica, a diferencia de los arreglos que son conjuntos de datos del mismo tipo almacenados en memoria secuencial, las Listas enlazadas no estan en memoria secuencial, se puede crear el nuevo elemento en cualquier lugar de la memoria.
Para crear una lista enlazada simple necesitamos crear los siguientes elementos.
Usaré el lenguaje Java ya que nos permite ver un poco mas acerca de el algoritmo sin tener que meternos tanto con destructores y punteros. Aqui se entiende mas facil
Nodo.- El nodo es un eslavon le la lista, y contiene dos partes. el Elemento y el NodoSigiuiente. el siguiente ejemplo en Java permite ver como se implementaria el nodo.
/**
* El nodo de la lista enlazada
* @author Ernesto Maldonado Thomas
*/
public class Nodo {
private T elemento;
private Nodo siguiente;
/**
* Permite crear una instancia del Nodo
*/
public Nodo() {
super();
}
/**
* Permite obtener el valor que almacena el Nodo
* @return
*/
public T getElemento() {
return elemento;
}
/**
* Permite asignar el valor que almacena el nodo
* @param elemento
*/
public void setElemento(T elemento) {
this.elemento = elemento;
}
/**
* Permite obtener el siguiente nodo
* @return
*/
public Nodo getSiguiente() {
return siguiente;
}
/**
* Permite asignar el siguiente Nodo
* @param siguiente
*/
public void setSiguiente(Nodo siguiente) {
this.siguiente = siguiente;
}
}
Luego, teniendo el nodo podremos implementar la lista.
La Lista.- Debe de contener un elemento que este siempre apuntando a la cabeza de la lista y otro a la cola. y los metodos necesarios para agregar un elemento, eliminar un elemento, buscar un elemento etc...
/**
* Permite generar una lista enlazada simple.
* @author Ernesto Maldonado Thomas
* @paramTipo del objeto que va a almacenar la lista
*/
public class ListaEnlazadaSimple {
private Nodo cabeza;
private Nodo cola;
/**
* Permite crear una instancia de la lista enlazada Simple
*/
public ListaEnlazadaSimple() {
super();
}
/**
* Permite agregar un elemento poniendolo en el ultimo lugar de la lista
* @param elemento
*/
public void agregarElemento(T elemento) {
Nodo nuevoNodo = new Nodo();
nuevoNodo.setElemento(elemento);
if (cabeza == null) { // Si la lista esta vacia
cabeza = nuevoNodo; // La cabeza se convierte en el nuevo nodo
cola = nuevoNodo; // Y la cola tambien ya que solo hay uno
} else { // Si la lista no esta vacia
cola.setSiguiente(nuevoNodo); // El siguiente elemento de la cola sera el nuevo nodo
cola = nuevoNodo; // Y ahora la cola sera el nuevo nodo
}
}
/**
* Permite borrar un elemento de la lista
* @param elemento
* @return
*/
public boolean borrarElemento(T elemento) {
Nodo i = cabeza;
Nodo anterior = null;
while (i != null) { // Recorremos los elementos hasta encontrarlo.
if (elemento.equals(i.getElemento())) {
return eliminar(anterior, i);
} else { //Si no lo encontramos continuamos con el siguiente elemento de la lista
anterior = i;
i = i.getSiguiente();
}
}
return false;
}
/**
* Permite eliminar un nodo dandole el nodo anterior
* @param anterior
* @param nodoAEliminar
* @return
*/
private boolean eliminar(Nodo anterior, Nodo nodoAEliminar) {
if (anterior == null) { //Asumimos que esta en la cabeza
cabeza = cabeza.getSiguiente();
if (nodoAEliminar.equals(cola)) { //Asumimos que solo hay un elemento en la lista
cola = null;
}
return true;
}
else { // Asumimos que esta en los nodos interiores
anterior.setSiguiente(nodoAEliminar.getSiguiente());
return true;
}
}
/**
* Permite buscar un elemento
* @param elemento
* @return
*/
public boolean buscar(T elemento) {
return buscar(cabeza, elemento); // Llamamos al metodo recursivo
}
/**
* Funcion recursiva para la busqueda
* @param nodo
* @param elemento
* @return
*/
private boolean buscar(Nodo nodo, T elemento) {
if (nodo == null) // Si no hay donde buscar regresamos false
return false;
if (elemento.equals(nodo.getElemento())) // Si lo encontramos regresamos true
return true;
return buscar(nodo.getSiguiente(), elemento); // Si no lo encontramos buscamos en el siguiente
}
public synchronized void imprimirElementos() {
for (Nodo i = cabeza; i != null; i = i.getSiguiente()) // Recorremos los elementos
System.out.print( i.getElemento() + " ");
System.out.println();
}
public static void main(String []args) {
//Probando el codigo
ListaEnlazadaSimple lista = new ListaEnlazadaSimple();
lista.agregarElemento("Ernesto");
lista.agregarElemento("Maldonado");
lista.agregarElemento("Thomas");
lista.agregarElemento("Ernesto2");
lista.agregarElemento("Maldonado2");
lista.agregarElemento("Thomas2");
lista.imprimirElementos();
lista.borrarElemento("Maldonado");
lista.imprimirElementos();
lista.borrarElemento("Ernesto");
lista.imprimirElementos();
lista.borrarElemento("Thomas2");
lista.imprimirElementos();
System.out.println("Lista contiene \"Thomas\": " + lista.buscar("Thomas"));
System.out.println("Lista contiene \"Hola\": " + lista.buscar("Hola"));
}
}
Bueno por el momento este es el código que ofrezco para que lo analizen, si necesitan ver como se implementa otro metodo a esta lista, solo dejen un comentario y yo lo implemento muchas gracias. 
Aqui puede ver como se agrega un elemento a la lista, es un gif simple pero concreto
Para crear una lista enlazada simple necesitamos crear los siguientes elementos.
Usaré el lenguaje Java ya que nos permite ver un poco mas acerca de el algoritmo sin tener que meternos tanto con destructores y punteros. Aqui se entiende mas facil
Nodo.- El nodo es un eslavon le la lista, y contiene dos partes. el Elemento y el NodoSigiuiente. el siguiente ejemplo en Java permite ver como se implementaria el nodo.
/**
* El nodo de la lista enlazada
* @author Ernesto Maldonado Thomas
*/
public class Nodo
private T elemento;
private Nodo
/**
* Permite crear una instancia del Nodo
*/
public Nodo() {
super();
}
/**
* Permite obtener el valor que almacena el Nodo
* @return
*/
public T getElemento() {
return elemento;
}
/**
* Permite asignar el valor que almacena el nodo
* @param elemento
*/
this.elemento = elemento;
}
/**
* Permite obtener el siguiente nodo
* @return
*/
public Nodo
return siguiente;
}
/**
* Permite asignar el siguiente Nodo
* @param siguiente
*/
public void setSiguiente(Nodo
this.siguiente = siguiente;
}
}
La Lista.- Debe de contener un elemento que este siempre apuntando a la cabeza de la lista y otro a la cola. y los metodos necesarios para agregar un elemento, eliminar un elemento, buscar un elemento etc...
/**
* Permite generar una lista enlazada simple.
* @author Ernesto Maldonado Thomas
* @param
*/
public class ListaEnlazadaSimple
private Nodo
/**
* Permite crear una instancia de la lista enlazada Simple
*/
public ListaEnlazadaSimple() {
super();
}
/**
* Permite agregar un elemento poniendolo en el ultimo lugar de la lista
* @param elemento
*/
public void agregarElemento(T elemento) {
Nodo
nuevoNodo.setElemento(elemento);
if (cabeza == null) { // Si la lista esta vacia
cabeza = nuevoNodo; // La cabeza se convierte en el nuevo nodo
cola = nuevoNodo; // Y la cola tambien ya que solo hay uno
} else { // Si la lista no esta vacia
cola.setSiguiente(nuevoNodo); // El siguiente elemento de la cola sera el nuevo nodo
cola = nuevoNodo; // Y ahora la cola sera el nuevo nodo
}
/**
* Permite borrar un elemento de la lista
* @param elemento
* @return
*/
public boolean borrarElemento(T elemento) {
Nodo
Nodo
while (i != null) { // Recorremos los elementos hasta encontrarlo.
if (elemento.equals(i.getElemento())) {
return eliminar(anterior, i);
} else { //Si no lo encontramos continuamos con el siguiente elemento de la lista
anterior = i;
i = i.getSiguiente();
}
}
return false;
}
/**
* @param anterior
* @param nodoAEliminar
* @return
*/
private boolean eliminar(Nodo
if (anterior == null) { //Asumimos que esta en la cabeza
cabeza = cabeza.getSiguiente();
if (nodoAEliminar.equals(cola)) { //Asumimos que solo hay un elemento en la lista
cola = null;
}
return true;
else { // Asumimos que esta en los nodos interiores
anterior.setSiguiente(nodoAEliminar.getSiguiente());
return true;
}
}
/**
* Permite buscar un elemento
* @param elemento
* @return
*/
return buscar(cabeza, elemento); // Llamamos al metodo recursivo
}
/**
* Funcion recursiva para la busqueda
* @param nodo
* @param elemento
* @return
*/
private boolean buscar(Nodo
if (nodo == null) // Si no hay donde buscar regresamos false
return false;
if (elemento.equals(nodo.getElemento())) // Si lo encontramos regresamos true
return true;
return buscar(nodo.getSiguiente(), elemento); // Si no lo encontramos buscamos en el siguiente
}
public synchronized void imprimirElementos() {
for (Nodo
System.out.print( i.getElemento() + " ");
System.out.println();
}
public static void main(String []args) {
//Probando el codigo
ListaEnlazadaSimple
lista.agregarElemento("Ernesto");
lista.agregarElemento("Maldonado");
lista.agregarElemento("Thomas");
lista.agregarElemento("Ernesto2");
lista.agregarElemento("Maldonado2");
lista.agregarElemento("Thomas2");
lista.borrarElemento("Maldonado");
lista.imprimirElementos();
lista.borrarElemento("Ernesto");
lista.imprimirElementos();
lista.borrarElemento("Thomas2");
lista.imprimirElementos();
System.out.println("Lista contiene \"Thomas\": " + lista.buscar("Thomas"));
System.out.println("Lista contiene \"Hola\": " + lista.buscar("Hola"));
}
}
Bueno por el momento este es el código que ofrezco para que lo analizen, si necesitan ver como se implementa otro metodo a esta lista, solo dejen un comentario y yo lo implemento muchas gracias.

Aqui puede ver como se agrega un elemento a la lista, es un gif simple pero concreto
Suscribirse a:
Entradas (Atom)