Fechar
QUE ES:
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.
Esto son definiciones simples. Pero las características que implican no lo son tanto.
DEFINICIÓN:
-Nodo hijo
-Nodo padre
-Nodo raíz
-Nodo hoja
-Nodo rama
Nodo hijo:
cualquiera de los nodos apuntados por uno de los nodos del árbol. 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 de 'B', 'C' y 'D'.
Nodo raíz:
nodo que no tiene padre. Este es el nodo que usaremos para referirnos al árbol. En el ejemplo, ese nodo es el 'A'.
Nodo hoja:
nodo que no tiene hijos. En el ejemplo hay varios: 'F', 'H', 'I', 'K', 'L', 'M', 'N' y 'O'.
Nodo rama:
aunque esta definición apenas la usaremos, estos son los nodos que no pertenecen a ninguna de las dos categorías anteriores. En el ejemplo: 'B', 'C', 'D', 'E', 'G' y 'J'.
GRADO
el número de hijos que tiene el elemento con más hijos dentro del árbol. En el árbol del ejemplo, el grado es tres, ya que tanto 'A' como 'D' tienen tres hijos, y no existen elementos con más de tres hijos.
ALTURA
la altura de un árbol se define como el nivel del nodo de mayor nivel. Como cada nodo de un árbol puede considerarse a su vez como la raíz de un árbol, también podemos hablar de altura de ramas. El árbol del ejemplo tiene altura 3, la rama 'B' tiene altura 2, la rama 'G' tiene altura 1, la 'H' cero, etc.
Al igual que hicimos con las listas que hemos visto hasta ahora, declaramos un tipo tipoNodo para declarar nodos, y un tipo pNodo para es el tipo para declarar punteros a un nodo.
Arbol es el tipo para declarar árboles de orden ORDEN.
Arboles Binarios
QUE ES UN ÁRBOL BINARIO
Un ÁRBOL BINARIO es aquel es el que cada elemento apunta como máximo a otros 2 elementos, comúnmente llamados hijo izquierdo y hijo derecho.
ÁRBOL BINARIO DE BÚSQUEDA
Un árbol binario de buque da o ABB, es un árbol binario en el cual para todo elemento, los elementos mayores a él, se ubican en su rama derecha, mientras que los elementos menores van en su rama izquierda. Cada elemento se almacena una sola vez por lo que no existen elementos repetidos.
Cada elemento(nodo) de un árbol ABB cuenta con tres campos:
- Dato(numero, letra, palabra, etc), en este caso usaremos un numero(entero).
- Puntero al nodo derecho
- Puntero al nodo izquierdo
RECORRIDOS DE ÁRBOL
Es la manera recursiva como pasaremos por cada nodo del árbol, existes tres formas:
OPERACIONES EN ARBOL BINARIO
Inserción
El procedimiento de inserción en un árbol binario de búsqueda es muy sencillo, únicamente hay que tener cuidado de no romper la estructura ni el orden del árbol.
Borrar
El borrado en árboles binarios de búsqueda es otra operación bastante sencilla excepto en un caso. Vamos a ir estudiando los distintos casos.
Tras realizar la búsqueda del nodo a eliminar observamos que el nodo no tiene hijos. Este es el caso más sencillo, únicamente habrá que borrar el elemento y ya habremos concuído la operación.
Búsqueda
La búsqueda Silaina consiste en acceder a la raíz del árbol, si el elemento a localizar coincide con éste la búsqueda ha concluido con éxito, si el elemento es menor se busca en el subárbol izquierdo y si es mayor en el derecho. Si se alcanza un nodo hoja y el elemento no ha sido encontrado se supone que no existe en el árbol. Cabe destacar que la búsqueda en este tipo de árboles es muy eficiente, representa una función logarítmica.
