Arboles binarios extendidos: arboles-2

Un árbol binario T se dice que es un árbol-2 o árbol binario extendido si cada nodo N tiene 0 o 2 hijos. En se caso, los nodos con dos hijos se denomina nodos internos y los nodos con 0 hijos se denominan nodos externos. A veces los nodos se distinguen en los diagramas mediante el uso de círculos para los nodos internos y de los cuadrados para los nodos externos.

El termino <<árbol binario extendido>> viene de la siguiente operación. Considere un árbol binario T, como el de la figura 7-5(a). Entonces T puede ser <> a un árbol-2 reemplazando cada subárbol vacía por un nuevo nodo, como se ve en la figura 7-5(b). un ejemplo importante de árbol-2 es el árbol T correspondiente a una expresión algebraica E que usa solo operaciones binarias.