[engranaje]

Yo si he de ser sincero, tras leer tu descripción del problema y en base a lo que he entendido harías lo siguente para este caso en concreto y dando por sentado que para un caso genérico lo mejor sería crear los objetos necesarios y usar herencia.

Basandonos en tu tipo

Código Delphi [-]
type      
  RegistroDatosArbol = record                                   
    Clave : TipoClave;                                   
    Padre : TipoPosicion;                                   
    HijoDerecho : TipoPosicion;                                  
    HijoIzquierdo : TipoPosicion;                            
  end;

y en que tu

TipoDatoMascota es un registro con datos propios (nombre mascota, peso, edad, etc)

Lo mejor sería que añadieras tu tipo TipoDatoMascota clave,padre,hijoDerecho e hijo izquierdo tal y como los tiene RegistroDatosArbol.

Despues deberias asegurarte de que tu TipoDatoMascota está definida en unit de tipos que pudieras añadir al uses de las units en la que vayas a usar y añadiria esa unit al uses de la unit Arbol.

Finalmente eliminina la declaración de RegistroDatosArbol de la unit Arbol y sustituye los sitios en los que se utiliza por TipoDatoMascota .

Deberias llamar a tu árbol "árbol de mascotas" ya que solo servirá para organizar records del tipo TipoDatoMascota pero deberas creo leyendo tu descripción del problema no necestias nada más porque en principio tu árbol solo va a ser usado para trabajar con tipoDatoMascota. Sospecho que posteriormente quien te esté enseñanado añadira la necesidad de poder utilizar el arbol (y los otros tipos de estrucutras de datos) para poder utilizar disintos tipos y no siempre el mismo y en ese punto comenzará a explicar los punteros o la orientación a objetos.

Creo que normalmente cuando alquien eseña a programar primero da pocas herramientas y despues pide que se ejerciten esas herramientas problemas que pueder solucionarse utilizandolas. Posteriormente se añaden complejidades que no pueden solucionarse con las herramientas que se conocen y se enseña una nueva herramienta para solucionar el problema. La orientación a objetos es la herramienta óptima para crear un árbol genérico. Los punteros y los tipos genéricos son herramientas que pueden utilizarse para conseguirlo si no se permite utilizar objetos. Pero siempre hay que aprender primero lo básico.