Hola, tengo la duda de si esta bien compilado el algoritmo para la solucion del ejercicio 2 del parctico 10.
Si alguien lo resolvio de otra forma o encuentra un error en el algoritmo por favor avise!
Gracias
Dejo la letra y debajo la solucion:
Ejercicio 2 (Básico)
Se considera la siguiente estructura de árbol binario:
type nodo =
record of
dato: integer;
hijoIzq,hijoDer: byte;
end
arbol = array 0..(MAX_NODOS-1) of nodo;
donde:
dato es un entero de 16 bits.
hijoIzq e hijoDer son índices a los subárboles izquierdo y derecho
respectivamente.
El árbol tiene por lo menos un elemento. El valor 0 en hijoIzq o hijoDer significa que
ese nodo no tiene el sucesor correspondiente.
Se pide:
(a) Escribir en alto nivel una función RECURSIVA que busca un entero en el árbol
y devuelve TRUE si está y FALSE en caso contrario. La función recibe como
argumentos el entero a buscar y un índice al árbol o subárbol donde buscar.
Compilar la rutina en assembler 8086 sabiendo que en AX se recibe el entero y
en BX el puntero al árbol o subárbol. El árbol esta cargado en memoria como
un array de nodos a partir de la posición 0 del Extra-Segment. El resultado se
devuelve en el registro CL (1 es TRUE y 0 es FALSE). Se deben conservar
todos los demás registros.
(b) Calcular el tamaño mínimo que debe tener el stack para que la función pueda
ser ejecutada en todos los casos, cualquiera sea el tamaño del árbol.
SOLUCION:
ALTO NIVEL:
//arbol es una variable global
bool Buscar (int n, int i ) {
if (arbol[i].dato == n )
return true
else
return ( Buscar(n, arbol[i].hijoIzq) or ( Buscar(n, arbol[i].hijoDer )
}
ASM:
XOR CL, CL
Buscar PROC
CMP[BX], 0x00 // no tiene sucesor
JE fin
CMP[AX], ES:[BX]
JE encontro
ADD BX, 2
PUSH BX
MOV BX, [BX] //hijo izquierdo
CALL Buscar // busco en el arbol del hijo izquierdo
POP BX
ADD BX, 1
MOV BX, [BX] //hijo derecho
CALL Buscar // busco en el arbol del hijo derecho
RET
encontro:
MOV CL, 1
RET
fin:
RET