Representación en memoria de arboles binarios
Hay dos formas tradicionales de representar un árbol binario en memoria:
- Por medio de datos tipo punteros también conocidos como variables dinámicas o listas.
- Por medio de arreglos.
Sin embargo la más utilizada es la primera, puesto que es la más natural para tratar este tipo de estructuras.
Los nodos del árbol binario serán representados como registros que contendrán como mínimo tres campos. En un campo se almacenará la información del nodo. Los dos restantes se utilizarán para apuntar al subarbol izquierdo y derecho del subarbol en cuestión.
Cada nodo se representa gráficamente de la siguiente manera:
El algoritmo de creación de un árbol binario es el siguiente:
Procedimiento crear(q:nodo)
inicio
mensaje("Rama izquierda?")
lee(respuesta)
si respuesta = "si" entonces
new(p)
q(li) <-- nil
crear(p)
en caso contrario
q(li) <-- nil
mensaje("Rama derecha?")
lee(respuesta)
si respuesta="si" entonces
new(p)
q(ld)<--p
crear(p)
en caso contrario
q(ld) <--nil
fin
INICIO
new(p)
raiz<--p
crear(p)
FIN
Fuente: Apunte de Estructura de Datos del Instituto tecnológico de la Paz