No es un bug, es una característica no documentada

30/1/15

Programación. Punteros en C (IV)

0:20 Posted by Inazio , No comments

Introducción a los árboles

Un árbol es una de las EDD más utilizadas para resolver multitud de problemas (y muy utlizadas también en juegos).

Es una EDD no lineal.

Un árbol se define recursivamente así: o es vacío o consiste en un nodo que contiene datos y punteros hacia otros árboles.

Idea gráfica del concepto de árbol

Un caso concreto. Árbol binario

Cada nodo tiene como máximo dos hijos.

Esto hace que la implementación sea más sencilla (cada nodo incluye dos punteros para apunter a cada uno de los hijos, el izquierdo y el derecho):

struct nodo {
       struct info elemento;
       struct nodo *izda;
       struct nodo *dcha;
};

struct nodo *arbol;

Implementación de un árbol general

Un árbol en general no tiene limitado el número de hijos que puede tener cada nodo, y por lo tanto no puedo establecer a priori un número de punteros en la estructura para apuntar a los hijos.

Una posible forma de hacerlo sería teniendo una lista de punteros a los hijos almacenada en cada nodo, junto con la información que guarda cada nodo.

Es decir, para implementar un árbol general, haríamos uso de otra EDD.

Operaciones habituales con árboles

è Inserción
è Eliminación
è Búsqueda
è Recorrido
·         Inorden. Primero se recorre el subárbol izquierdo, luego se lee el valor del nodo y finalmente se recorre el subárbol derecho.
·         Preorden. Primero se lee el valor del nodo y después se recorren los subárboles.
·         Postorden. Se recorren primero el subárbol izquierdo y el derecho y después se lee el valor del nodo.


Inorden: 15 – 35 – 38 – 43 – 44 – 46 – 50 – 69 – 70 – 75 – 81 – 90
Preorden: 50 – 35 – 15 – 43 – 38 – 46 – 44 – 75 – 69 – 70 – 90 – 81
Postorden: 15 – 38 – 44 – 46 – 43 – 35 – 70 – 69 – 81 – 90 – 50

Aplicaciones de los árboles

Se utilizan en problemas que involucran jerarquía (por ejemplo, miembros de una familia), ramificación (como  los árboles de juegos, que involucran tomar la mejor decisión de las posibles, tras analizar todas las consecuencias) y clasificación y búsqueda eficiente.

0 comments:

Publicar un comentario