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