Árboles etiquetados

Algunas veces es útil etiquetar los vértices o aristas de un dígrafo para indicar su uso para un propósito específico. Esto es particularmente cierto para muchos usos de los árboles en las ciencias de la computación. 

Ejemplo. Considere la expresión algebraica dada a continuación

En esta expresión no es posible realizar la suma central hasta tanto no se hayan evaluado los argumentos de la izquierda y de la derecha. Es fácil ver que ese último cálculo constituye el operador central. La expresión algebraica anterior se puede representar gráficamente en un árbol binario etiquetado como se muestra a continuación. 

Ejemplo: Construya el árbol de la expresión algebraica dada.

El árbol posicional binario es de particular importancia. En el siguiente dígrafo, por razones obvias se etiqueta las posiciones de los hijos como izquierda y derecha, en vez de 1 y 2. Los árboles etiquetados pueden tener varios conjuntos de etiquetas. Por lo general se omite las etiquetas izquierda – derecha en un árbol binario posicional para enfatizar otras etiquetas útiles. Se dice que un árbol posicional también es un árbol ordenado. Al trazar los dígrafos de un árbol posicional, se supondrá que las posiciones de los n hijos para cada vértice son ordenados de forma simétrica bajo el vértice, y se coloca en la posición adecuada cada hijo realmente existente. Cuando no existen todos los hijos, entonces se indica las posiciones de los hijos mediante la dirección de las aristas, como en la figura siguiente.

Representación de los árboles binarios posicionales en computadora

Para representar un árbol binario posicional como datos de computadora se necesita extender el concepto de lista enlazada al de una lista doblemente enlazada, donde cada celda contenga dos apuntadores y un elemento de datos. Se utilizará el siguiente símbolo gráfico.

para representar estas nuevas celdas. El espacio central representa el almacenamiento de datos y los dos apuntadores, llamados apuntador izquierdo y apuntador derecho representados mediante puntos y flechas. Implementaremos la representación con tres arreglos: Left, que contiene los apuntadores dirigidos a los hijos de la izquierda; Right, los apuntadores a los hijos de la derecha y Data con la información o las etiquetas relacionadas con cada vértice. El valor 0, utilizado como apuntador, indica que el hijo correspondiente no existe.

Ejemplo: Considere de nuevo el siguiente árbol binario.

La siguiente es la representación como una lista doblemente enlazada en forma simbólica.