ex5.c

#include <stdio.h>
#include <stdlib.h>
#include "tree.h"

#define N 20
/*
Implemente una función que reciba un árbol binario y dos
nodos del mismo, y encuentre un camino entre los nodos.
*/
void findPath(TTree *tree,TData a, TData b);
int binarySearch(TData array[],int ini, int fin, TData k);
int eliminarComunes(TData array1[], int n1, TData array2[], int n2);
void invertir(TData array[], int n);
int find(TNode *node, TData a, TData array[]);
void printArray(TData array[], int n);

int main(){

    TTree arbol;
    crearArbol(&arbol);
    insertar(&arbol,15);
    insertar(&arbol,6);
    insertar(&arbol,3);
    insertar(&arbol,1);
    insertar(&arbol,4);
    insertar(&arbol,9);
    insertar(&arbol,7);
    insertar(&arbol,12);
    insertar(&arbol,20);
    insertar(&arbol,18);
    insertar(&arbol,24);
    insertar(&arbol,17);

    findPath(&arbol,9,17);

    return 0;
}

void findPath(TTree *tree,TData a, TData b){
    TData array1[N],array2[N],array[N];
    int n1, n2, n3, i;

    n1 = find(tree->root,a,array1);
    n2 = find(tree->root,b,array2);
    invertir(array1,n1);
    printArray(array1,n1);
    printArray(array2,n2);
    n3 = eliminarComunes(array1,n1,array2,n2);
    printArray(array1,n3);

}

void printArray(TData array[], int n){
    int i;
    for(i=0; i<n; i++)
        printf("%d ",array[i]);
    printf("\n");
}

int binarySearch(TData array[],int ini, int fin, TData k){
    int mid = (ini+fin)/2;
    if(array[mid] == k)
        return mid;
    if(array[mid]>k)
        return binarySearch(array,ini,mid-1,k);
    else
        return binarySearch(array,mid+1,fin,k);
}

int eliminarComunes(TData array1[], int n1, TData array2[], int n2){
    int count = 0;
    int pos = binarySearch(array1,0,n1-1,array2[0]);
    int i;
    count = pos+n2;
    for(i=0; i<count; i++)
        array1[i+pos] = array2[i];

    return count;
}

void invertir(TData array[], int n){
    int i;
    TData aux;
    for(i=0; i<(n/2); i++){
        aux = array[i];
        array[i] = array[n-1-i];
        array[n-1-i] = aux;
    }
}

int find(TNode *node, TData a, TData array[]){
    TNode *p = node;
    int i=0;
    while(p != NULL){
        if(p->info == a)
            break;
        array[i++] = p->info;
        if(p->info < a){
            p = p->der;
        }else{
            p = p->izq;
        }
    }
    return i;
}