Download árboles binarios

ÁRBOLES
UNIDAD VI
____________________________________________________________________________________________________
UNIDAD VI
ÁRBOLES BINARIOS
6.1. REPRESENTACIÓN DE ÁRBOLES BINARIOS
6.1.1. TERMINOLOGÍA DE ÁRBOLES BINARIOS
Las estructuras dinámicas lineales de datos( listas enlazadas, pilas, colas) tienen grandes ventajas
de flexibilidad sobre las representaciones contiguas, pero tienen un problema son listas secuenciales, es
decir, que por la forma en la que están dispuestas es necesario moverse un elemento a la vez debido a que
cada elemento tiene un siguiente elemento, esta linealidad es típica de cadenas, de elementos que
pertenecen a una sola dimensión: campos en un registro, entradas en una pila, entradas en una cola y
nodos en una lista enlazada simple. En esta parte se mostraran las estructuras de datos no lineales
conocidos como árboles, adicionalmente podremos decir que no es el único tipo de estructura no lineal
pues a parte de los árboles existen los grafos la cual tiene aplicaciones muy diversas en las ciencias.
6.1.2. IMPLEMENTACION DE UN ARBOL BINARIO
Un árbol binario es un conjunto finito de elementos que está vacío, o está dividido en tres
subconjuntos desarticulados. El primer subconjunto contiene un solo elemento llamado raíz del árbol. Los
otros dos son en sí mismos, árboles binarios, llamados subárboles izquierdo y derecho del árbol original.
Un subárbol izquierdo o derecho puede estar vacío. Cada elemento de un subárbol se llama nodo del
árbol.
En la siguiente figura se muestra un árbol binario. Este árbol consiste en nueve nodos y tiene ‘A’
como raíz. Su subárbol izquierdo tiene a ‘B’ como raíz y su subárbol derecho a ‘C’.
A
B
D
C
E
G
F
H
I
____________________________________________________________________________________________________
ESTRUCTURA DE DATOS
ING. OSORNIO
80
ÁRBOLES
UNIDAD VI
____________________________________________________________________________________________________
La siguiente figura muestra estructuras de árboles que no son binarios. De tal modo que, si ‘A’ es
la raíz de un árbol binario y ‘B’ es la raíz de su subárbol derecho o izquierdo entonces ‘A’ se llama el
padre de ‘B’, y ‘B’ el hijo izquierdo o derecho de ‘A’. Un nodo que no tiene hijos se llama hoja. El nivel
de un nodo en un árbol binario se define como sigue. La raíz del árbol tiene nivel 0 (cero) y el nivel de
cualquier otro nodo del árbol es uno más que el nivel de su padre. Un árbol binario de completo de
profundidad ‘D’ es el árbol estrictamente binario cuyas hojas están en el nivel ‘D’. En la siguiente figura
se muestra un árbol de profundidad 3.
A
B
C
D
G
E
F
H
I
A
B
C
D
F
E
G
____________________________________________________________________________________________________
ESTRUCTURA DE DATOS
ING. OSORNIO
81
ÁRBOLES
UNIDAD VI
____________________________________________________________________________________________________
OPERACIONES CON ÁRBOLES BINARIOS
Existen varias operaciones simples que pueden aplicarse a árboles binarios. Si p es un apuntador a
un nodo nd de un árbol binario, la función info(p) da como resultado los contenidos de nd. Las funciones
left(p), right(p), father(p), da como resultado el apuntador nulo sí nd no tiene hijo izquierdo, hijo derecho
padre o hermano. Como consecuencia las funciones isleft(p) e isright(p) dan como resultado verdadero
(true) sí nd es hijo izquierdo o derecho, respectivamente, de algún otro nodo del árbol, y falso (false) en
caso contrario.
q = father(p);
if(q == null)
return(false);
if(left (q) == p)
return(true);
return(false);
APLICACIONES DE ÁRBOLES BINARIOS
Un árbol binario es una estructura de datos útiles cuando en cada punto de un proceso hay que
tomar una decisión de doble opción. Como en la aplicación para encontrar duplicados:
/* Leer el primer número e insertarlo en un árbol binario de un solo nodo */
scanf (“%d”, &number);
tree = maketree (number);
while (hay número rezagados en la entrada)
{
scanf (“%d”, number);
p = q;
while (number != info(p) && q != NULL)
{
p = q;
if (number < info(p))
q = left(p);
else
q = right(p);
} /* Fin del while */
if (number == info(p))
printf (“%d %s \n”, number, “es un duplicado”);
/* Insertar number a la derecha o izquierda de p */
else if (number < info(p))
setleft(p, number);
else
setright(p, number);
} /* Fin del while */
____________________________________________________________________________________________________
ESTRUCTURA DE DATOS
ING. OSORNIO
82
ÁRBOLES
UNIDAD VI
____________________________________________________________________________________________________
Otra operación común es recorrer un árbol binario; esto e pasar a través del árbol, enumerando
cada uno de sus nodos una vez. En cualquier caso se habla de visitar cada nodo al enumerar este. El orden
en que se visitan los nodos es de una manera clara, del primero al último.
Para recorrer un árbol binario lleno de preorden, se ejecutan las siguientes tres operaciones:
1. Visitar la raíz.
2. Recorrer el subárbol izquierdo en preorden.
3. Recorrer el subárbol derecho en preorden.
Para visitar un árbol binario lleno de orden, se ejecutan las siguientes tres operaciones:
1. Recorrer el subárbol izquierdo en orden.
2. Visitar la raíz.
3. Recorrer el subárbol derecho en orden.
Para recorrer un árbol binario lleno en postorden, se ejecutan las siguientes tres
operaciones:
1. Recorrer el subárbol izquierdo en postorden.
2. Recorrer el subárbol derecho en postorden.
3. Visitar la raíz.
A
B
C
F
D
E
G
H
I
Preorden: ABDGCEHIF
En orden: DGBAHEICF
Postorden: GDBHIEFCA
E
____________________________________________________________________________________________________
ESTRUCTURA DE DATOS
ING. OSORNIO
83
ÁRBOLES
UNIDAD VI
____________________________________________________________________________________________________
E
E
E
E
E
E
E
E
E
E
E
Preorden: ABCEIFJDHLA
En orden: EICFJBGDKHLA
Postorden: IEJFCGKLHDBA
REPRESENTACIÓNES DE ÁRBOLES BINARIOS.
Al igual que en el caso de los nodos de una lista, los nodos de un árbol pueden implantarse como
un arreglo de elementos o como asignación de una variable dinámica. Cada nodo contiene los campos
info, left, y father. Los campos left, right y father apuntan a los nodos hijo derecho, hijo izquierdo y padre
respectivamente.
#define NUMNODES 500
struct nodetype
{
int info;
int left;
int right;
int father;
};
struct nodetype node [numnodes];
ELECCIÓN DE UNA REPRESENTACIÓN DE ÁRBOLES BINARIOS.
____________________________________________________________________________________________________
ESTRUCTURA DE DATOS
ING. OSORNIO
84
ÁRBOLES
UNIDAD VI
____________________________________________________________________________________________________
La representación ligada requiere de campos left, right y father (aunque ya se ha visto que uno o
dos de ellos pueden eliminase en situaciones específicas), pero permite un uso mucho más flexible del
conjunto de nodos. En la representación ligada, un nodo particular puede colocarse en cualquier
localización y en cualquier árbol, mientras que en la representación secuencial un nodo se puede usar sólo
si se necesita en una localización en un árbol específico. Además en la representación con nodos
dinámica, el número total de árboles y nodos está limitado exclusivamente por la cantidad de memoria
disponible. Así la representación ligada es preferible en la situación dinámica general de muchos árboles
en forma impredecible.
RECORRIDOS DE ÁRBOLES BINARIOS EN C.
Es posible implantar el recorrido de árboles binarios en C por medio de rutinas recursivas que
reflejan las definiciones del recorrido. Las tres rutinas en C: pretav, intrav y posttrav, imprimen los
contenidos de un árbol binario en preorden, orden y postorden. El parámetro de cada rutina es un
apuntador al nodo raíz de un árbol binario.
pretav(tree)
NODEPTR tree;
{
if (tree != NULL)
{
printf (“%d”, tree-info);
pretav (tree- left);
pretav (tree - right);
} /* fin del if */
} /* fin del pretav */
intrav (tree)
NODEPTR tree;
{
if (tree != NULL)
{
intrav (tree - left);
printf (“%d”, tree - info);
intrav (tree - right);
} /* fin del if */
} /* fin del intrav */
posttrav (tree)
NODEPTR tree;
{
if (tree != NULL)
{
posttrav (tree - left);
posttrav (tree - right);
printf (“%d”, tree - info);
____________________________________________________________________________________________________
ESTRUCTURA DE DATOS
ING. OSORNIO
85
ÁRBOLES
UNIDAD VI
____________________________________________________________________________________________________
} /* fin del if */
} /* fin del posttrav */
6.2. OPERACIONES SOBRE UN ARBOL BINARIO
6.2.1. CONSTRUYE UN ARBOL
6.2.2. RECORRIDO DE ARBOL BINARIO
6.2.2.1 PREORDEN
6.2.2.2 EN ORDEN
6.2.2.3 POSTORDEN
6.2.3. BÚSQUEDA DE UN NODO
6.2.4. INSERCIÓN DE UN NODO
6.2.5. ELIMINACIÓN DE UN NODO
Las listas enlazadas, las pilas y las colas son estructuras lineales de datos. Un árbol es una
estructura lineal y de dos dimensiones de datos, con propiedades especiales, Los nodos de los árboles
contienen dos o más enlaces, árboles cuyos nodos todos ellos contienen dos enlaces (ninguno, uno, o
ambos de los cuales pudiera ser NULL). El nodo raíz es el primer nodo de un árbol. Cada enlace en el
nodo raíz se refiere aun hijo. El hijo izquierdo s el primer nodo en el subárbol izquierdo y el hijo derecho
es el primer nodo en el subárbol izquierdo. Los hijos de un nodo se conocen como descendientes. Un
nodo sin hijos se conoce como un nodo de hoja. Los científicos de la computación normalmente dibujan
los árboles partiendo del nodo raíz hacia abajo – en forma exactamente opuesta a los árboles en la
naturaleza.
Crearemos un árbol binario especial conocido como un árbol de búsqueda binario (que no tiene
valores duplicados de nodos) tienen la característica que los valores en cualquier subárbol izquierdo son
menores que el valor en sus nodos padre, y los valores en cualquier subárbol derecho son mayores que el
valor en sus nodos padre. En la figura se ilustra un árbol de búsqueda binario con 12 valores. Note que la
forma del árbol de búsqueda binario que corresponde a un conjunto de datos puede variar, dependiendo
del orden en el cual los valores están insertos dentro del árbol.
47
25
11
77
43
69
93
El programa de la siguiente
figura,
crea un árbol de búsqueda
binario y lo68recorre de tres formas,
7
17
31
44
en orden, preorden y postorden. El programa genera 10 números aleatorios e inserta cada uno de ellos en
el árbol, a excepción de los valores duplicados, que son descartados.
Las funciones utilizadas, para crear un árbol de búsqueda binario y recorrer el árbol, son
____________________________________________________________________________________________________
ESTRUCTURA DE DATOS
ING. OSORNIO
86
ÁRBOLES
UNIDAD VI
____________________________________________________________________________________________________
recursivas. La función insertNode recibe como argumentos la dirección del árbol y un entero para
almacenarse en el árbol. En un árbol de búsqueda binario un nodo puede ser únicamente inserto como
nodo de hoja, Los pasos para insertar un nodo en un árbol de búsqueda binario, son como sigue:
1. Si treePtr es NULL, crea un nuevo nodo. Llame malloc, asigna la memoria asignada a treePtr,
asigna a (treePrt)->data el entero a almacenarse, asigna (*treePtr)->leftPtr y (*treePtr)->rightPtr
el valor NULL y devuelve o regresa el control al llamador (ya sea a main o a una llamada anterior
a inserNode).
2. Si el valor de treePtr no es NULL, y el valor a insertarse es menor que (treePtr)->data, se
llama a la función insertNode con la dirección(*treePtr)->leftPtr. De no ser así, se llama a la
función insertNode con la dirección de (*treePtr)->righptr. Se continúan los pasos recursivos
hasta que se encuentre un apuntador NULL, entonces se ejecutara el paso 1) para insertar el
nuevo nodo.
Las funciones inOrder, preOrder y postOrder cada una de ellas recibe una árbol (es decir, el
apuntador al nodo raíz del árbol) y recorren el árbol.
Los pasos para recorrido un recorrido inOrder son:
1. Recorrer el subárbol izquierdo inOrder.
2. Recorrer el valor en el nodo.
3. Recorrer el subárbol derecho inOrder.
El valor en un nodo no es procesado en tanto no sean procesados los valores de su subárbol
izquierdo. El recorrido inOrder del árbol es:
6 13 17 27 33 42 48
Nótese que el recorrido inOrder de un árbol de búsqueda binario imprime los valores de nodo en
valor ascendente. El proceso de crear un árbol de búsqueda binario, de hecho ordene los datos y por lo
tanto este proceso se llama la clasificación de árbol binario.
27
42
13
6
17
33
48
El árbol de búsqueda binario facilita la eliminación de duplicación. Conforme se crea el árbol
cualquier intento para insertar un valor duplicado será detectado porque en cada una de las comparaciones
un duplicado seguirá las mismas decisiones “ir a la izquierda” o “ir a la derecha” que utilizo el valor
original. Entonces, el duplicado eventualmente será comparado con un nodo que contenga el mismo valor.
Llegado a este punto el valor duplicado pudiera simplemente sé desertado.
____________________________________________________________________________________________________
ESTRUCTURA DE DATOS
ING. OSORNIO
87
ÁRBOLES
UNIDAD VI
____________________________________________________________________________________________________
También es rápido buscar en un árbol binario un valor que coincida con un valor clave. Si el valor
es denso, entonces cada nivel contendrá aproximadamente dos veces tantos elementos como el nivel
anterior. Por lo tanto un árbol de búsqueda binario con n elementos tendría un máximo de log2n
(logaritmo de base 2 de n niveles) y, por lo tanto, tendrían que efectuarse un máximo log2n de
comparaciones, ya sea para encontrar una coincidencia, o para determinar que no existe ninguna. Esto
significa, por ejemplo, que al buscar en un árbol de búsqueda binario de 1000 elementos(densamente
empacados), no es necesario llevar a cabo mas de 10 comparaciones porque 2n >1000. Al buscar en un
árbol de búsqueda binario 1000000 (densamente empacados), no es necesario llevar a cabo mas de 20
comparaciones, porque 2 a la 20 >1000000.
En los ejercicios se presentan algoritmos para otras operaciones de árboles de búsqueda binarios,
como sé borrar un elemento de un árbol binario, imprimir un árbol binario en un formato de árbol de dos
dimensiones, ejecutar un recorrido en orden de niveles de un árbol binario, imprimir un árbol binario en
un formato de árbol de dos dimensiones, y ejecutar un recorrido en orden de niveles de un árbol binario.
El recorrido de orden de niveles de un árbol binario pasa por los nodos de un árbol, se pasa por los nodos
de izquierda a derecha. Otros ejercicios de árboles binarios incluyen permitir que un árbol de búsqueda
binario contenga valores duplicados, insertar valores de cadenas de un árbol binario, y determinar cuantos
niveles incluidos en u árbol binario.
/* PROGRAMA de ARBOL */
/* DECLARACION DE LAS LIBRERIAS */
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
/* ESTRUCTURA AUTOREFERENCIADA */
struct treeNode
{
struct treeNode *leftPtr;
int data;
struct treeNode *rightPtr;
};
/* DEFINICION DE TIPOS */
typedef struct treeNode TREENODE;
typedef TREENODE *TREENODEPTR;
/* ENCABEZADO DE LAS FUNCIONES */
void insertNode(TREENODEPTR *, int);
void inOrder (TREENODEPTR);
void preOrder (TREENODEPTR);
void postOrder (TREENODEPTR);
/* FUNCIONES PRINCIPALES */
main()
{
int i, item;
TREENODEPTR rootPtr =NULL;
/* DECLARACION DE DATOS */
srand(time(NULL));
____________________________________________________________________________________________________
ESTRUCTURA DE DATOS
ING. OSORNIO
88
ÁRBOLES
UNIDAD VI
____________________________________________________________________________________________________
/* intentar a insertar 10 valores aleatorios entre 0 y 14 en el arbol*/
printf("Los numeros iniciales en el arbol son: \n");
for(i=1;i<=10;i++)
{
item = rand() % 15;
printf("%3d", item);
insertNode(&rootPtr, item);
}
printf("\n\n El preorden tranversal es : \n");
preOrder(rootPtr);
printf("\n\n El inorden tranversal es : \n");
inOrder (rootPtr);
printf("\n\n El postorden tranversal es : \n");
preOrder (rootPtr);
return 0;
}
/* Insertar nodo */
void insertNode(TREENODEPTR *treePtr, int value)
{
if (*treePtr == NULL)
{
*treePtr = (TREENODEPTR) malloc(sizeof(TREENODEPTR));
if (*treePtr != NULL)
{
(*treePtr)->data = value;
(*treePtr)->leftPtr = NULL;
(*treePtr)->rightPtr = NULL;
}
else
printf("%d no inserto. Memoria insuficiente. \n\n, info");
}
else
if(value < (*treePtr)->data)
insertNode (&((*treePtr) -> leftPtr), value);
else
if (value > (*treePtr)->data)
insertNode (&((*treePtr)->rightPtr), value);
else
printf("duplicado");
}
/* Retirar un nodo*/
void inOrder (TREENODEPTR treePtr)
{
if(treePtr != NULL)
____________________________________________________________________________________________________
ESTRUCTURA DE DATOS
ING. OSORNIO
89
ÁRBOLES
UNIDAD VI
____________________________________________________________________________________________________
{
inOrder(treePtr->leftPtr);
printf("%3d", treePtr->data);
inOrder (treePtr->rightPtr);
}
}
void preOrder(TREENODEPTR treePtr)
{
if(treePtr != NULL)
{
printf("%3d", treePtr->data);
preOrder(treePtr->leftPtr);
preOrder (treePtr->rightPtr);
}
}
void postOrder(TREENODEPTR treePtr)
{
if(treePtr != NULL)
{
postOrder(treePtr->leftPtr);
postOrder (treePtr->rightPtr);
printf("%3d", treePtr->data);
}
}
____________________________________________________________________________________________________
ESTRUCTURA DE DATOS
ING. OSORNIO
90