Árbol (informática)

De Wikipedia, la enciclopedia libre

(Redirigido desde Árbol (estructura de datos))

Saltar a navegación, búsqueda
Para otros usos de este término, véase Árbol (desambiguación).

En ciencias de la informática, un árbol es una estructura de datos

ampliamente usada que imita la forma de un árbol (un conjunto de nodos
conectados). Un nodo es la unidad sobre la que se construye el árbol y puede
tener cero o más nodos hijos conectados a él. Se dice que un nodo a es padre
de un nodo b si existe un enlace desde a hasta b (en ese caso, también decimos
que b es hijo de a). Sólo puede haber un único nodo sin padres, que
llamaremos raíz. Un nodo que no tiene hijos se conoce como hoja. Los demás
nodos (tienen padre y uno o varios hijos) se les conoce como rama.

Definición [editar]

Formalmente, podemos definir un árbol de la siguiente forma:

 Caso base: un árbol con sólo un nodo (es a la vez raíz del árbol y hoja).

 Un nuevo árbol a partir de un nodo nr y k árboles de

raíces con elementos cada uno, puede
construirse estableciendo una relación padre-hijo entre nr y cada una
de las raíces de los k árboles. El árbol resultante de
nodos tiene como raíz el nodo nr, los nodos
son los hijos de nr y el conjunto de nodos hoja está
formado por la unión de los k conjuntos hojas iniciales. A cada uno de
los árboles Ai se les denota ahora subárboles de la raíz.

Una sucesión de nodos del árbol, de forma que entre cada dos nodos
consecutivos de la sucesión haya una relación de parentesco, decimos que es
un recorrido árbol. Existen dos recorridos típicos para listar los nodos de un
árbol: primero en profundidad y primero en anchura. En el primer caso, se
listan los nodos expandiendo el hijo actual de cada nodo hasta llegar a una
hoja, donde se vuelve al nodo anterior probando por el siguiente hijo y así
sucesivamente. En el segundo, por su parte, antes de listar los nodos de nivel n
+ 1 (a distancia n + 1 aristas de la raíz), se deben haber listado todos los de
nivel n. Otros recorridos típicos del árbol son preorden, postorden e
inorden:

 El recorrido en preorden, también llamado orden previo consiste en

recorrer en primer lugar la raíz y luego cada uno de los hijos
en orden previo.
 El recorrido en inorden, también llamado orden simétrico (aunque
este nombre sólo cobra significado en los árboles binarios) consiste en
recorrer en primer lugar A1, luego la raíz y luego cada uno de los hijos
en orden simétrico.
 El recorrido en postorden, también llamado orden posterior consiste
en recorrer en primer lugar cada uno de los hijos en
orden posterior y por último la raíz.
 Árbol binario
 De Wikipedia, la enciclopedia libre
 Saltar a navegación, búsqueda
 Para otros usos de este término, véase Árbol binario (desambiguación).
 En ciencias de la computación, un árbol binario es una estructura de
datos en la cual cada nodo siempre tiene un hijo izquierdo y un hijo
derecho. No pueden tener más de dos hijos (de ahí el nombre "binario").
Si algún hijo tiene como referencia a null, es decir que no almacena
ningún dato, entonces este es llamado un nodo externo. En el caso
contrario el hijo es llamado un nodo interno. Usos comunes de los
árboles binarios son los árboles binarios de búsqueda, los montículos
binarios y Codificación de Huffman.

Un árbol binario sencillo de tamaño 9 y altura 3, con un nodo raíz cuyo valor
es 2.
En teoría de grafos, se usa la siguiente definición: «Un árbol binario es un
grafo conexo, acíclico y no dirigido tal que el grado de cada vértice no es
mayor a 3». De esta forma sólo existe un camino entre un par de nodos.

Un árbol binario con enraizado es como un grafo que tiene uno de sus
vértices, llamado raíz, de grado no mayor a 2. Con la raíz escogida, cada
vértice tendrá un único padre, y nunca más de dos hijos. Si rehusamos el
requerimiento de la conectividad, permitiendo múltiples componentes
conectados en el grafo, llamaremos a esta última estructura un bosque.

Tipos de árboles binarios [editar]

 Un árbol binario es un árbol con raíz en el que cada nodo tiene como
máximo dos hijos.
 Un árbol binario lleno es un árbol en el que cada nodo tiene cero o dos
hijos.
 Un árbol binario perfecto es un árbol binario lleno en el que todas las
hojas (vértices con cero hijos) están a la misma profundidad (distancia
desde la raíz, también llamada altura).
 A veces un árbol binario perfecto es denominado árbol binario
completo. Otros definen un árbol binario completo como un árbol
binario lleno en el que todas las hojas están a profundidad n o n-1,
para alguna n.

Un árbol binario es un árbol en el que ningún nodo puede tener más de dos
subárboles. En un árbol binario cada nodo puede tener cero, uno o dos hijos
(subárboles). Se conoce el nodo de la izquierda como hijo izquierdo y el nodo
de la derecha como hijo derecho.

  Miercoles, 21 de Abril de
2010
Entrar
Nombre Password [ Regístrate ]
Árboles
 
* Definición de árbol
* Formas de representación
* Nomenclatura sobre árboles
* Declaración de árbol binario
* Recorridos sobre árboles binarios
* Construcción de un árbol binario
* Árbol binario de búsqueda
* Problemas

Definición de árbol

Un árbol es una estructura de datos, que puede definirse de

forma recursiva como:

- Una estructura vacía o

- Un elemento o clave de información (nodo) más un
número finito de estructuras tipo árbol, disjuntos, llamados
subárboles. Si dicho número de estructuras es inferior o
igual a 2, se tiene un árbol binario.

Es, por tanto, una estructura no secuencial.

Otra definición nos da el árbol como un tipo de grafo (ver

grafos): un árbol es un grafo acíclico, conexo y no dirigido.
Es decir, es un grafo no dirigido en el que existe
exactamente un camino entre todo par de nodos. Esta
definición permite implementar un árbol y sus operaciones
empleando las representaciones que se utilizan para los
grafos. Sin embargo, en esta sección no se tratará esta
implementación.

Formas de representación
- Mediante un grafo:

  Figura 1

- Mediante un diagrama encolumnado:

a
  b
    d
  c
    e
    f

En la computación se utiliza mucho una estructura de datos,

que son los árboles binarios. Estos árboles tienen 0, 1 ó 2
descendientes como máximo. El árbol de la figura anterior
es un ejemplo válido de árbol binario.

Nomenclatura sobre árboles

- Raíz: es aquel elemento que no tiene antecesor; ejemplo:

a.
- Rama: arista entre dos nodos.
- Antecesor: un nodo X es es antecesor de un nodo Y si por
alguna de las ramas de X se puede llegar a Y.
- Sucesor: un nodo X es sucesor de un nodo Y si por alguna
de las ramas de Y se puede llegar a X.
- Grado de un nodo: el número de descendientes directos
que tiene. Ejemplo: c tiene grado 2, d tiene grado 0, a tiene
grado 2.
- Hoja: nodo que no tiene descendientes: grado 0. Ejemplo:
d
- Nodo interno: aquel que tiene al menos un descendiente.
- Nivel: número de ramas que hay que recorrer para llegar
de la raíz a un nodo. Ejemplo: el nivel del nodo a es 1 (es
un convenio), el nivel del nodo e es 3.
- Altura: el nivel más alto del árbol. En el ejemplo de la
figura 1 la altura es 3.
- Anchura: es el mayor valor del número de nodos que hay
en un nivel. En la figura, la anchura es 3.

Aclaraciones: se ha denominado a a la raíz, pero se puede

observar según la figura que cualquier nodo podría ser
considerado raíz, basta con girar el árbol. Podría
determinarse por ejemplo que b fuera la raíz, y a y d los
sucesores inmediatos de la raíz b. Sin embargo, en las
implementaciones sobre un computador que se realizan a
continuación es necesaria una jerarquía, es decir, que haya
una única raíz.

Declaración de árbol binario

Se definirá el árbol con una clave de tipo entero (puede ser

cualquier otra tipo de datos) y dos hijos: izquierdo (izq) y
derecho (der). Para representar los enlaces con los hijos se
utilizan punteros. El árbol vacío se representará con un
puntero nulo.

Un árbol binario puede declararse de la siguiente manera:

typedef struct tarbol
{
int clave;
struct tarbol *izq,*der;
} tarbol;

Otras declaraciones también añaden un enlace al nodo

padre, pero no se estudiarán aquí.

Recorridos sobre árboles binarios

Se consideran dos tipos de recorrido: recorrido en

profundidad y recorrido en anchura o a nivel. Puesto que los
árboles no son secuenciales como las listas, hay que buscar
estrategias alternativas para visitar todos los nodos.

- Recorridos en profundidad:

* Recorrido en preorden: consiste en visitar el nodo actual

(visitar puede ser simplemente mostrar la clave del nodo
por pantalla), y después visitar el subárbol izquierdo y una
vez visitado, visitar el subárbol derecho. Es un proceso
recursivo por naturaleza.
Si se hace el recorrido en preorden del árbol de la figura 1
las visitas serían en el orden siguiente: a,b,d,c,e,f.

void preorden(tarbol *a)

{
if (a != NULL) {
visitar(a);
preorden(a->izq);
preorden(a->der);
}
}

* Recorrido en inorden u orden central: se visita el

subárbol izquierdo, el nodo actual, y después se visita el
subárbol derecho. En el ejemplo de la figura 1 las visitas
serían en este orden: b,d,a,e,c,f.

void inorden(tarbol *a)

{
if (a != NULL) {
inorden(a->izq);
visitar(a);
inorden(a->der);
}
}

* Recorrido en postorden: se visitan primero el subárbol

izquierdo, después el subárbol derecho, y por último el
nodo actual. En el ejemplo de la figura 1 el recorrido
quedaría así: d,b,e,f,c,a.

void postorden(arbol *a)

{
if (a != NULL) {
postorden(a->izq);
postorden(a->der);
visitar(a);
}
}

La ventaja del recorrido en postorden es que permite borrar

el árbol de forma consistente. Es decir, si visitar se traduce
por borrar el nodo actual, al ejecutar este recorrido se
borrará el árbol o subárbol que se pasa como parámetro. La
razón para hacer esto es que no se debe borrar un nodo y
después sus subárboles, porque al borrarlo se pueden
perder los enlaces, y aunque no se perdieran se rompe con
la regla de manipular una estructura de datos inexistente.
Una alternativa es utilizar una variable auxiliar, pero es
innecesario aplicando este recorrido.
- Recorrido en amplitud:

Consiste en ir visitando el árbol por niveles. Primero se

visitan los nodos de nivel 1 (como mucho hay uno, la raíz),
después los nodos de nivel 2, así hasta que ya no queden
más.
Si se hace el recorrido en amplitud del árbol de la figura
una visitaría los nodos en este orden: a,b,c,d,e,f
En este caso el recorrido no se realizará de forma recursiva
sino iterativa, utilizando una cola (ver Colas) como
estructura de datos auxiliar. El procedimiento consiste en
encolar (si no están vacíos) los subárboles izquierdo y
derecho del nodo extraido de la cola, y seguir desencolando
y encolando hasta que la cola esté vacía.
En la codificación que viene a continuación no se
implementan las operaciones sobre colas.

void amplitud(tarbol *a)

{
tCola cola; /* las claves de la cola serán de
tipo árbol binario */
arbol *aux;
if (a != NULL) {
CrearCola(cola);
encolar(cola, a);
while (!colavacia(cola)) {
desencolar(cola, aux);
visitar(aux);
if (aux->izq != NULL) encolar(cola, aux-
>izq);
if (aux->der != NULL) encolar(cola, aux-
>der);
}
}
}

Por último, considérese la sustitución de la cola por una pila

en el recorrido en amplitud. ¿Qué tipo de recorrido se
obtiene?

Construcción de un árbol binario

Hasta el momento se ha visto la declaración y recorrido de

un árbol binario. Sin embargo no se ha estudiado ningún
método para crearlos. A continuación se estudia un método
para crear un árbol binario que no tenga claves repetidas
partiendo de su recorrido en preorden e inorden,
almacenados en sendos arrays.

Antes de explicarlo se recomienda al lector que lo intente

hacer por su cuenta, es sencillo cuando uno es capaz de
construir el árbol viendo sus recorridos pero sin haber visto
el árbol terminado.

Partiendo de los recorridos preorden e inorden del árbol de

la figura 1 puede determinarse que la raíz es el primer
elemento del recorrido en preorden. Ese elemento se busca
en el array inorden. Los elementos en el array inorden entre
izq y la raíz forman el subárbol izquierdo. Asimismo los
elementos entre der y la raíz forman el subárbol derecho.
Por tanto se tiene este árbol:

 
A continuación comienza un proceso recursivo. Se procede
a crear el subárbol izquierdo, cuyo tamaño está limitado por
los índices izq y der. La siguiente posición en el recorrido
en preorden es la raíz de este subárbol. Queda esto:

El subárbol b tiene un subárbol derecho, que no tiene

ningún descendiente, tal y como indican los índices izq y
der. Se ha obtenido el subárbol izquierdo completo de la
raíz a, puesto que b no tiene subárbol izquierdo:

 
 

Después seguirá construyéndose el subárbol derecho a

partir de la raíz a.

La implementación de la construcción de un árbol partiendo

de los recorridos en preorden y en inorden puede
consultarse aquí (en C).

Árbol binario de búsqueda

Un árbol binario de búsqueda es aquel que es:

- Una estructura vacía o

- Un elemento o clave de información (nodo) más un
número finito -a lo sumo dos- de estructuras tipo árbol,
disjuntos, llamados subárboles y además cumplen lo
siguiente:

  * Todas las claves del subárbol izquierdo al nodo son

menores que la clave del nodo.
  * Todas las claves del subárbol derecho al nodo son
mayores que la clave del nodo.
  * Ambos subárboles son árboles binarios de búsqueda.

Un ejemplo de árbol binario de búsqueda:

Figura 5

Al definir el tipo de datos que representa la clave de un

nodo dentro de un árbol binario de búsqueda es necesario
que en dicho tipo se pueda establecer una relación de
orden. Por ejemplo, suponer que el tipo de datos de la clave
es un puntero (da igual a lo que apunte). Si se codifica el
árbol en Pascal no se puede establecer una relación de
orden para las claves, puesto que Pascal no admite
determinar si un puntero es mayor o menor que otro.

En el ejemplo de la figura 5 las claves son números enteros.

Dada la raíz 4, las claves del subárbol izquierdo son
menores que 4, y las claves del subárbol derecho son
mayores que 4. Esto se cumple también para todos los
subárboles. Si se hace el recorrido de este árbol en orden
central se obtiene una lista de los números ordenada de
menor a mayor.
Cuestión: ¿Qué hay que hacer para obtener una lista de los
números ordenada de mayor a menor?

Una ventaja fundamental de los árboles de búsqueda es

que son en general mucho más rápidos para localizar un
elemento que una lista enlazada. Por tanto, son más
rápidos para insertar y borrar elementos. Si el árbol está
perfectamente equilibrado -esto es, la diferencia entre el
número de nodos del subárbol izquierdo y el número de
nodos del subárbol derecho es a lo sumo 1, para todos los
nodos- entonces el número de comparaciones necesarias
para localizar una clave es aproximadamente de logN en el
peor caso. Además, el algoritmo de inserción en un árbol
binario de búsqueda tiene la ventaja -sobre los arrays
ordenados, donde se emplearía búsqueda dicotómica para
localizar un elemento- de que no necesita hacer una
reubicación de los elementos de la estructura para que esta
siga ordenada después de la inserción. Dicho algoritmo
funciona avanzando por el árbol escogiendo la rama
izquierda o derecha en función de la clave que se inserta y
la clave del nodo actual, hasta encontrar su ubicación; por
ejemplo, insertar la clave 7 en el árbol de la figura 5
requiere avanzar por el árbol hasta llegar a la clave 8, e
introducir la nueva clave en el subárbol izquierdo a 8.
El algoritmo de borrado en árboles es algo más complejo,
pero más eficiente que el de borrado en un array ordenado.

Ahora bien, suponer que se tiene un árbol vacío, que

admite claves de tipo entero. Suponer que se van a ir
introduciendo las claves de forma ascendente. Ejemplo:
1,2,3,4,5,6
Se crea un árbol cuya raíz tiene la clave 1. Se inserta la
clave 2 en el subárbol derecho de 1. A continuación se
inserta la clave 3 en el subárbol derecho de 2.
Continuando las inserciones se ve que el árbol degenera en
una lista secuencial, reduciendo drásticamente su eficacia
para localizar un elemento. De todas formas es poco
probable que se de un caso de este tipo en la práctica. Si
las claves a introducir llegan de forma más o menos
aleatoria entonces la implementación de operaciones sobre
un árbol binario de búsqueda que vienen a continuación son
en general suficientes.

Existen variaciones sobre estos árboles, como los AVL o

Red-Black (no se tratan aquí), que sin llegar a cumplir al
100% el criterio de árbol perfectamente equilibrado, evitan
problemas como el de obtener una lista degenerada.

Operaciones básicas sobre árboles binarios de

búsqueda

- Búsqueda

Si el árbol no es de búsqueda, es necesario emplear uno de

los recorridos anteriores sobre el árbol para localizarlo. El
resultado es idéntico al de una búsqueda secuencial.
Aprovechando las propiedades del árbol de búsqueda se
puede acelerar la localización. Simplemente hay que
descender a lo largo del árbol a izquierda o derecha
dependiendo del elemento que se busca.

boolean buscar(tarbol *a, int elem)

{
if (a == NULL) return FALSE;
else if (a->clave < elem) return buscar(a->der,
elem);
else if (a->clave > elem) return buscar(a->izq,
elem);
else return TRUE;
}

- Inserción

La inserción tampoco es complicada. Es más, resulta

practicamente idéntica a la búsqueda. Cuando se llega a un
árbol vacío se crea el nodo en el puntero que se pasa como
parámetro por referencia, de esta manera los nuevos
enlaces mantienen la coherencia. Si el elemento a insertar
ya existe entonces no se hace nada.

void insertar(tarbol **a, int elem)

{
if (*a == NULL) {
*a = (arbol *) malloc(sizeof(arbol));
(*a)->clave = elem;
(*a)->izq = (*a)->der = NULL;
}
else if ((*a)->clave < elem) insertar(&(*a)-
>der, elem);
else if ((*a)->clave > elem) insertar(&(*a)-
>izq, elem);
}

- Borrado

La operación de borrado si resulta ser algo más complicada.

Se recuerda que el árbol debe seguir siendo de búsqueda
tras el borrado. Pueden darse tres casos, una vez
encontrado el nodo a borrar:
1) El nodo no tiene descendientes. Simplemente se borra.
2) El nodo tiene al menos un descendiente por una sola
rama. Se borra dicho nodo, y su primer descendiente se
asigna como hijo del padre del nodo borrado. Ejemplo: en
el árbol de la figura 5 se borra el nodo cuya clave es -1. El
árbol resultante es:
3) El nodo tiene al menos un descendiente por cada rama.
Al borrar dicho nodo es necesario mantener la coherencia
de los enlaces, además de seguir manteniendo la estructura
como un árbol binario de búsqueda. La solución consiste en
sustituir la información del nodo que se borra por el de una
de las hojas, y borrar a continuación dicha hoja. ¿Puede ser
cualquier hoja? No, debe ser la que contenga una de estas
dos claves:
· la mayor de las claves menores al nodo que se borra.
Suponer que se quiere borrar el nodo 4 del árbol de la
figura 5. Se sustituirá la clave 4 por la clave 2.
· la menor de las claves mayores al nodo que se borra.
Suponer que se quiere borrar el nodo 4 del árbol de la
figura 5. Se sustituirá la clave 4 por la clave 5.

El algoritmo de borrado que se implementa a continuación

realiza la sustitución por la mayor de las claves menores,
(aunque se puede escoger la otra opción sin pérdida de
generalidad). Para lograr esto es necesario descender
primero a la izquierda del nodo que se va a borrar, y
después avanzar siempre a la derecha hasta encontrar un
nodo hoja. A continuación se muestra gráficamente el
proceso de borrar el nodo de clave 4:
 

Codificación: el procedimiento sustituir es el que desciende

por el árbol cuando se da el caso del nodo con
descencientes por ambas ramas.

void borrar(tarbol **a, int elem)

{
void sustituir(tarbol **a, tarbol **aux);
tarbol *aux;

if (*a == NULL) /* no existe la clave */

return;

if ((*a)->clave < elem) borrar(&(*a)->der,

elem);
else if ((*a)->clave > elem) borrar(&(*a)->izq,
elem);
else if ((*a)->clave == elem) {
aux = *a;
if ((*a)->izq == NULL) *a = (*a)->der;
else if ((*a)->der == NULL) *a = (*a)->izq;
else sustituir(&(*a)->izq, &aux); /* se
sustituye por
la mayor de las menores */

free(aux);
}
}
 

Ficheros relacionados

Implementación de algunas de las operaciones sobre

árboles binarios.

Ejercicio resuelto

Escribir una función que devuelva el numero de nodos de

un árbol binario. Una solución recursiva puede ser la
siguiente:

funcion nodos(arbol : tipoArbol) : devuelve entero;

inicio
 si arbol = vacio entonces devolver 0;
 en otro caso devolver (1 + nodos(subarbol_izq) +
nodos(subarbol_der));
fin

Adaptarlo para que detecte si un árbol es perfectamente

equilibrado o no.

Problemas propuestos

Árboles binarios: OIE 98. (Enunciado)

Aplicación práctica de un árbol

Se tiene un fichero de texto ASCII. Para este propósito

puede servir cualquier libro electrónico de la librería
Gutenberg o Cervantes, que suelen tener varios cientos de
miles de palabras. El objetivo es clasificar todas las
palabras, es decir, determinar que palabras aparecen, y
cuantas veces aparece cada una. Palabras como
'niño'-'niña', 'vengo'-'vienes' etc, se consideran diferentes
por simplificar el problema.

Escribir un programa, que recibiendo como entrada un

texto, realice la clasificación descrita anteriormente.
Ejemplo:
Texto: "a b'a c. hola, adios, hola"

La salida que produce es la siguiente:

a2
adios 1
b1
c1
hola 2

Nótese que el empleo de una lista enlazada ordenada no es

una buena solución. Si se obtienen hasta 20.000 palabras
diferentes, por decir un número, localizar una palabra
cualquiera puede ser, y en general lo será, muy costoso en
tiempo. Se puede hacer una implementación por pura
curiosidad para evaluar el tiempo de ejecución, pero no
merece la pena.

La solución pasa por emplear un árbol binario de búsqueda

para insertar las claves. El valor de log(20.000) es
aproximadamente de 14. Eso quiere decir que localizar una
palabra entre 20.000 llevaría en el peor caso unos 14
accesos. El contraste con el empleo de una lista es
simplemente abismal. Por supuesto, como se ha comentado
anteriormente el árbol no va a estar perfectamente
equilibrado, pero nadie escribe novelas manteniendo el
orden lexicográfico (como un diccionario) entre las
palabras, asi que no se obtendrá nunca un árbol muy
 degenerado. Lo que está claro es que cualquier evolución
del árbol siempre será mejor que el empleo de una lista.

Por último, una vez realizada la lectura de los datos, sólo

queda hacer un recorrido en orden central del árbol y se
obtendrá la solución pedida en cuestión de segundos.

Una posible definición de la estructura árbol es la siguiente:

typedef struct tarbol

{
char clave[MAXPALABRA];
int contador; /* numero de apariciones. Iniciar
a 0 */
struct tarbol *izq,
*der;
} tarbol;

 
Versión del artículo con código ( ALGORITMIA #
fuente en Pascal 10/06/2004 14:01:16 )

© (2001-2008) ALGORITMIA.NET - Política de privacidad

4. Árboles binarios.
Los árboles de grado 2 tienen una especial importancia. Se les
conoce con el nombre de árboles binarios. Se define un árbol
binario como un conjunto finito de elementos (nodos) que bien
está vació o está formado por una raíz con dos árboles binarios
disjuntos, llamados subárbol izquierdo y derecho de la raíz.
En los apartados que siguen se considerarán únicamente árboles
binarios y, por lo tanto, se utilizará la palabra árbol para referirse a
árbol binario. Los árboles de grado superior a 2 reciben el nombre
de árboles multicamino.
Árbol binario de búsqueda.- Los árboles binarios se utilizan
frecuentemente para representar conjuntos de datos cuyos
elementos se identifican por una clave única. Si el árbol está
organizado de tal manera que la clave de cada nodo es mayor que
todas las claves su subárbol izquierdo, y menor que todas las
claves del subárbol derecho se dice que este árbol es un árbol
binario de búsqueda.
Ejemplo:

 
Operaciones básicas.- Una tarea muy común a realizar con un
árbol es ejecutar una determinada operación con cada uno de los
elementos del árbol.Esta operación se considera entonces como un
parámetro de una taré más general que es la visita de todos los
nodos o, como se denomina usualmente, del recorrido del árbol.
Si se considera la tarea como un proceso secuencial, entonces los
nodos individuales se visitan en un orden específico, y pueden
considerarse como organizados según una estructura lineal. De
hecho, se simplifica considerablemente la descripción de muchos
algoritmos si puede hablarse del proceso del siguiente elemento en
el árbol, según un cierto orden subyacente.
Hay dos formas básicas de recorrer un árbol: El recorrido en
amplitud y el recorrido en profundidad.
Recorrido en amplitud.- Es aquel recorrido que recorre el árbol
por niveles, en el último ejemplo sería:
12 - 8,17 - 5,9,15
Recorrido en profundidad.- Recorre el árbol por subárboles. Hay
tres formas: Preorden, orden central y postorden.
Preorden: Raiz, subárbol izquierdo y subárbol derecho.
Orden central: Subarbol izquierdo, raiz, subarbol derecho.
Postorden: Subarbol izquierdo, subarbol derecho, raiz.

Ejemplo:
Preorden: 20 - 12 - 5 - 2 - 7 - 13 - 15 - 40 - 30 - 35 - 47
Orden central: 2 - 5 - 7 - 12 - 13 - 15 - 20 - 30 - 35 - 40 - 47
Postorden: 2 - 7 - 5 - 15 - 13 - 12 - 35 - 30 - 47 - 40 - 20
Ejemplo:
Preorden: / + a b * c d Notación polaca
Orden central: a + b / c * d Notación infija
Postorden: a b + c d * / Notación polaca inversa
Estructura de datos
Variables
Las variables son estructura de datos usados para almacenar
información. Hay dos tipos de información que puede ser
almacenada: Números y texto. Antes de usar una variable ésta,
deberá primero ser definida:
Dim nombre_de_variable As Tipo
Ejemplo:
Dim precio As Long
Dim nombre_de_articulo As String
Tipo Rango permitido

Integer -32,768 a 32,767

Long -2,147,483,648 a 2,147,483,647

-3.402823E38 a -1.401298E-45
Single
1.401298E-45 a 3.402823E38

-1.79769313486232D308 a -4.94065645841247D-324
Double
4.94065645841247D-324 a 1.79769313486232D308

Currency -922337203685477.5808 a 922337203685477.5807

String 0 a 65,000 bytes

Valores de fechas: 1/1/0000 a 12/32/9999

Variant Numérico: igual que Double

Texto: Igual que String

Si una nueva variable es declarada sin especificación VB por default la

deberá tomar como tipo Variant

Una vez que una variable se ha creado, se le puede asignar un

valor. Para esto se usa el operador ' = '. En el primer ejemplo de
abajo a una variable se le asigna un valor constante, mientras que
en el segundo se le asigna el contenido de una variable
multiplicada por 10.
Ejemplo 1: precio = 29.95
Ejemplo 2: precio_total = precio * 10
El Alcance de una variable es definido como su rango de
operación. Hay tres tipos de alcance en una variable:
1. Local - La variable solo puede ser usada en el procedimiento
actual ( use Dim dentro del procedimiento requerido).
2.
3. Módulo - La variables pueden ser accesadas desde cualquier
procedieminento de la forma actual (use Dim dentro de la
sección de Declaraciones Generales de la forma).
4. Global - Pueden ser accesados desde cualquier
procedimiento y desde cualquier forma. (usa Global dentro
de la sección de Declaraciones Generales de un módulo).

Variables Estáticas
El declarar variables y arreglos como local en un
procedimieneto/función es muy usado, porque esto minimíza los
efectos extraños que pueden ocurrir cuando se usan variables
globales. Sin embargo, cuando usamos una variable local en un
procedimiento VB crea un espacio de memoria para mantener el
valor de esta variable , esto sucede cuando lee el estatuto Dim,
pero cuando llega al final del procedimiento (End Sub) VB libera el
espacio asigndo para el valor de la variable local. Agrega el
siguiente código a un botón de comando y observa que valores son
impresos:
Sub Command1_Click ()
Dim numero As Integer ' Crea una variable Local normal
numero = numero + 1
Print numero
End Sub
Después de dar clic varias veces al botón de comando deberás ver
una columna de unos en el lado izquierdo de la forma. El valor
nunca será arriba de uno a pesar de que el valor de la variable se
incrementa en uno cada vez. Esto es porque cada vez que el
procediemineto es llamado, haciendo clic en el botón, VB esta
trabajan con una variable diferente. Esta tiene exactamente el
mismo nombre en el programa pero es una variable
completamente diferente. Para que esto no suceda así, introduce
Staticen el lugar de Dim:
Sub Command1_Click ()
Static numero As Integer ' Crea una variable estática local
numero = numero + 1
Print numero
End Sub
Ahora en vez de que el valor de la variable se pierda cuando el
procedimiento termina, con este cambio (static) su valor
permanecerá hasta que todo el programa termine. De esta manera,
podemos ver una lista de números que se incrementan en uno
cada vez que se le da clic al botón de comando.
Nota: La nueva variable estática es una variable de alcance local, si
cualquier procedimiento trata de accesar esta variable no prodrá
lograrlo. Agrega a la forma un nuevo botón de comando, el cual
deberá tener un nuevo procedimiento 'Click', y trata de corregir o
imprimir el valor de la variable estática que contiene el primer
botón.
El contenido de un arreglo local, también puede mantenerse
mientras el programa se ejecute. Para hacer esto agrega el estatuto
'Static' en lugar de 'Dim' como lo hicimos en el ejemplo de arriba.
Static salarios(199) As Long
5. Variables Constantes
Las constantes son similares a una variable pero tienen un valor
determinado que se mantiene igual en toda la ejecución del
programa. El contenido de una varible puede cambiar tantas veces
sea necesario. ¿Porque usar una constante si no puede cambiar de
valor?. Hacemos esto cuando deseamos usar un mismo número o
una palabra (string) varias veces. Por ejemplo, en un programa
para calcular los impuestos de todo el año, deberá hacer referencia
a un valor en varias partes del programa, que puede ser el por
ciento de impuesto mensual con respecto a las ganancias. Par ello
podemos usar una variable llamada IMP, que mantendrá el valor
en el evento Form_Load.
En el siguiente ejemplo definimos una contante llamada ' IMP ' y
le asignamos el valor de 1.175. Ese es usado en estatuto Print con la
variable pago_total para calcular la cantidad total a pagar. Note
que en lugar de escribir 1.175 en la fórmula nos referimos a el
nombre de la constante.
Ejemplo:
Const IMP = 1.175 ' Declara y asigna un valor a la constante
Dim pago_total As Currency ' Declara una variable local para
almacenar el total a pagar
pago_total = 560.95
Print "Total = "; pago_total * IMP
Como las variables las constantes también tiene reglas de alcance.
Hay constantes globales que pueden ser accesadas por cualquier
módulo o cualquier forma del proyecto, las constantes de módulo
solo son accesadas por la foma que los contiene, y las contantes
locales son accesadas solamente por el objeto actual o
procedimiento/función.
1. Local - usa 'Const' dentro del procedimiento requerido.
2.
3. Módulo - usa 'Const' dentro de la sección deDeclaraciones
Generales de una forma o módulo.
 4. Global - usa 'Global Const' dentro de la sección
deDeclaraciones Generales de un módulo (ésto es
Module1.bas).

Arreglos (arrays)
La variables son muy usadas para lamacenar pequeñas cantidades
de información, pero no son convenientes para grandes cantidades
de información muy similar. Por ejemplo, para almacenar los
salarios de doscientos empleados, necesitaremos 200 variables
diferentes. Una mejor forma de almacenar esta información será
usra una estructura de datos llamada arreglos array.
Un arreglo es similar a las celdas en un panal de abejas. Todo el
arreglo tiene un nombre, y cada celda tiene una dirección. Para el
problema de los salarios planteado arriba, un arreglo el cual tiene
200 elementos (celdas) , usaremos el comando Dim para cerar un
nueva variable, pero marcaremos también el tamaño de esta
variable .
Dim nombre_del_arreglo (tamaño) [As Tipo]
Ejemplo: Dim salarios(199) As Long
En el ejemplo de arriba creamos un arreglo con 200 elementos. El
tamaño marcado es de 199 porque por default VB empieza la
numeración con 0.
Si sabemos que el nombre 'Jaime ' es el empleado número 24 y
tiene un salario de 25,000 pesos mensuales, podemos lintroducir
esta cantidad en el arreglo de la siguiente forma:
salarios(23) = 25000
Contrario a lo anterior, si deseamos saber cula es el salario del
empleado número 189, podemos usar:
lblvalor.Caption = salarios(188)
Nota: En los dos ejemplos anteriores, para accesar un elemento es
necesario colocar el número del elemento anterior (si deseamos el
150, pedimos el 149). esto es VB empieza un arreglo de 0, no de 1.
Sin embargo VB pude ser forzado a empezar con 1, agregando el
estatuto 'Option Base 1' en la sección de declaraciones generales de
la forma o el módulo.