NODOS CABECERA; ÁRBOLES ENHEBRADOS

Nodos con cabecera

Suponga  un árbol binario T dispuesto en memoria por representación enlazada. A veces se añade al principio de T un nodo extra, especial, llamada nodo cabecera. Cuando se usa este nodo extra, la variable puntero el árbol, que llamaremos CABEZA (en lugar de raíz), apuntara al nodo cabecera, el puntero izquierdo del nodo cabecera apuntara a la raíz de T.

Hebras; enhebrado inorden

Considere de nuevo  la representación enlazada de un árbol binario T. aproximadamente la mitad de las entradas de los campo puntero IZQ  y DER contendrá valores nulos. Este espacio se puede aprovechar más eficientemente reemplazados las entradas nulas por algún otro tipo de información. Específicamente, reemplazaremos ciertas entradas nulas con punteros especiales que apuntaran a nodos supriores de árbol. Estos punteros especiales se llaman hebras, y los árboles binarios con este tipo de punteros se llaman árboles enhebrados.

Las hebras de un árbol enhebrado se deben distinguir de alguna forma de los punteros normales. Las hebras en los diagramas de un árbol enhebrado se indican normalmente con las líneas discontinuas. En la memoria de la computadora se pude usar un campo extra INDICADOR de un bit para distinguir las hebras de los punteros ordinarios, o, alternativamente, denotar las hebras por enteros negativos y los punteros normales por enteros positivos.