Ensamblador

Ejercicio nº3:

Implementar una función no recursiva para recorrer un árbol binario en inorden.

 void inordenNR(ArbolB T,void (* EscribirElemento)(void *),int tamano)

{

  NodoB nodoActual,aux;

  void *et;

  Pila p;

  int fin;

  int faltaHD;                        /*Indica si falta el hijo derecho*/

  p=CrearPila(sizeof(NodoB));

  et=malloc(tamano);

  if(!et){

    ....                             /*Error:Sin memoria*/

  }

  aux=NODOB_NULO;

  Push(&aux,p);

  nodoActual=RaizB(T);

  fin=0;

  while(!fin){

    while(nodoActual!=NODOB_NULO){

      Push(&nodoActual,p);

      nodoActual=HijoIzqdaB(nodoActual,T);

    }

    Tope(&nodoActual,p);

    Pop(p);

    if (nodoActual!=NODOB_NULO){

      EtiquetaArbolB(et,nodoActual,T);

      (*EscribirElemento)(et);

      nodoActual=HijoDrchaB(nodoActual,T);

    }

    else fin=1;

  }

  free(et);

  DestruirPila(p);

Ejercicio nº2:

El recorrido en preorden de un determinado árbol binario es: GEAIBMCLDFKJH y en inorden IABEGLDCFMKHJ .

A)Dibujar el árbol binario.

B)Dar el recorrido en postorden.

C)Diseñar una función para dar el recorrido en postorden dado el recorrido en preorden e inorden y escribir un programa para comprobar el resultado del apartado anterior.

RESPUESTA

B)El recorrido en postorden es IBAEDLFCHJKMG.

C)El código solución al tercer apartado es el siguiente:

/*Fichero: comprobar.c */

char *preorden="GEAIBMCLDFKJH";

char *inorden="IABEGLDCFMKHJ";

char *postorden;

void post(char *pre,char *in,char *pos,int n)

{

  int longIzqda;

  if(n!=0){

    pos[n-1]=pre[0];

    longIzqda=strchr(in,pre[0])-in;

    post (pre+1,in,pos,longIzqda);

    post (pre+1+longIzqda,in+1+longIzqda,pos+longIzqda,n-1-longIzqda);

  }

Ejercicio nº5:

Escribir una función que realice la reflexión de un árbol binario.

void Refleja(ArbolB T)

{

  ArbolB Ti,Td;

  if(T!=ARBOLB_VACIO){

    Ti=PodarHijoIzqdaB(RaizB(T),T);

    Td=PodarHijoDrchaB(RaizB(T),T);

    Refleja(Ti);

    InsertarHijoDrchaB(RaizB(T),Ti,T);

    Refleja(Td);

    InsertarHijoIzqdaB(RaizB(T),Td,T);

  }

Ejercicio nº6:

Escribir una función recursiva que encuentre el número de nodos de un árbol binario. 

int numero(NodoB n,ArbolB T)

{

  if (n==NODOB_NULO)

    return 0;

  else 

    return 1+numero(HijoIzqdaB(n,T),T)+numero(HijoDrchaB(n,T),T);

}

Para calcular el número de nodos de un árbol T se haría mediante la llamada numero(RaizB(T),T).

 Ejercicio nº7:

Escribir una función recursiva que encuentre la altura de un árbol binario.

#define MAXIMO(a,b) ((a) < (b)?(b):(a))

int altura(NodoN n,ArbolB T)

{

  if(n==NODOB_NULO)

    return -1;

  else

    return 1+MAXIMO(altura(HijoIzqdaB(n,T),T),altura(HijoDrchaB(n,T),T));

- Recorrido en amplitud:

Consiste en ir visitando el árbol por niveles. Primero se visitan los nodos de nivel 1 (como mucho hay uno, la raíz), después los nodos de nivel 2, así hasta que ya no queden más.
Si se hace el recorrido en amplitud del árbol de la figura una visitaría los nodos en este orden: a,b,c,d,e,f
En este caso el recorrido no se realizará de forma recursiva sino iterativa, utilizando una cola como estructura de datos auxiliar. El procedimiento consiste en encolar (si no están vacíos) los subárboles izquierdo y derecho del nodo extraido de la cola, y seguir desencolando y encolando hasta que la cola esté vacía.
En la codificación que viene a continuación no se implementan las operaciones sobre colas.

void amplitud(tarbol *a)

{

  tCola cola;   /* las claves de la cola serán de tipo árbol binario */

  arbol *aux;

  if (a != NULL) {

    CrearCola(cola);

    encolar(cola, a);

    while (!colavacia(cola)) {

      desencolar(cola, aux);

      visitar(aux);

      if (aux->izq != NULL) encolar(cola, aux->izq);

      if (aux->der != NULL) encolar(cola, aux->der);

    }

  }

}