Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- //Juanjose Tenorio Peña
- typedef struct nodo{
- int valor;
- struct nodo* ptrHI;
- struct nodo* ptrHD;
- } TNodo;
- void crear_arbol(TNodo ** ptrRaiz);
- void inserta_nodo(TNodo **ptrRaiz, int valor);
- int Encontrar_camino(TNodo * , TNodo *, TNodo*);
- void crear_arbol(TNodo ** ptrRaiz){
- *ptrRaiz = NULL;
- }
- void inserta_nodo(TNodo **ptrRaiz, int valor){
- TNodo *ptrHoja, *ptrRecorrido, *ptrPadre;
- ptrHoja = (TNodo*)malloc(sizeof(TNodo));
- ptrHoja->valor = valor;
- ptrHoja->ptrHI=ptrHoja->ptrHD=NULL;
- if(*ptrRaiz){
- ptrRecorrido = *ptrRaiz;
- ptrPadre = NULL;
- while (ptrRecorrido){
- ptrPadre = ptrRecorrido;
- if (ptrRecorrido->valor > valor)
- ptrRecorrido = ptrRecorrido->ptrHI;
- else
- ptrRecorrido = ptrRecorrido->ptrHD;
- }
- if (ptrPadre->valor > valor)
- ptrPadre->ptrHI = ptrHoja;
- else
- ptrPadre->ptrHD = ptrHoja;
- }
- else{
- *ptrRaiz = ptrHoja;
- }
- }
- /*funcion que determina si los nodos pertenecen a hijos distintos*/
- int hijos_distintos(int v1,int v2,int vraiz){
- if(v1<vraiz && v2>vraiz) return 1;
- if(v2<vraiz && v1>vraiz) return 1;
- return 0;
- }
- int hijo(int v1,int v2,int vraiz){
- if(v1<vraiz && v2<vraiz) return 0;//hijo izquierdo
- else{
- return 1; //hijo derecho
- }
- }
- void Imprimir_Camino(TNodo*raiz , int padre,int hijo){
- TNodo* ptrecorrido=raiz;
- while(ptrecorrido!=NULL && ptrecorrido->valor!=padre ){
- if (ptrecorrido->valor > padre)
- ptrecorrido = ptrecorrido->ptrHI;
- else
- ptrecorrido = ptrecorrido->ptrHD;
- }
- //una vez encontrado padre comienzo la impresion
- printf("%d -",padre);
- while(ptrecorrido!=NULL && ptrecorrido->valor!=hijo ){
- if (ptrecorrido->valor > hijo){
- ptrecorrido = ptrecorrido->ptrHI;
- printf("%d -",ptrecorrido->valor);
- } else{
- ptrecorrido = ptrecorrido->ptrHD;
- printf("%d -",ptrecorrido->valor);
- }
- }
- }
- int Encontrar_camino(TNodo* raiz, TNodo *p1, TNodo*p2){
- int v1,v2,vraiz,num;TNodo*ptrecorrido;
- /*leo el valor de cada uno de los nodos*/
- if (raiz==NULL){
- printf("No existe camino\n");
- return 0;
- }
- v1=p1->valor;
- v2=p2->valor;
- vraiz=raiz->valor;
- if (hijos_distintos(v1,v2,vraiz)){
- printf("No existe camino para dichos nodos\n");
- return 0;
- }else{
- if(v1!=vraiz && v2!=vraiz){
- num=hijo(v1,v2,vraiz);//verifico a que hijo pertenecen
- //num=0 es hijo izquierdo, num=1 es hijo derecho
- if (num==0){
- ptrecorrido=raiz->ptrHI;
- //verifico quien puede ser el padre
- if (v1>v2){
- Imprimir_Camino(ptrecorrido,v2,v1);
- }else{
- Imprimir_Camino(ptrecorrido,v1,v2);
- //verifico quien puede ser el padre
- }
- }else{
- ptrecorrido=raiz->ptrHD;
- //verifico quien es el padre
- if (v1>v2){
- Imprimir_Camino(ptrecorrido,v2,v1);
- }else{
- Imprimir_Camino(ptrecorrido,v1,v2);
- //verifico quien puede ser el padre
- }
- }
- }else{//caso en que la raiz sea parte del camino
- if (v1==vraiz){
- ptrecorrido=raiz;
- Imprimir_Camino(ptrecorrido,v1,v2);
- }else{
- ptrecorrido=raiz;
- Imprimir_Camino(ptrecorrido,v2,v1);
- }
- }
- }
- }
- int main(int argc, char** argv) {
- TNodo *ptrRaiz;TNodo *p1;TNodo *p2;
- crear_arbol(&ptrRaiz);
- inserta_nodo(&ptrRaiz, 15);
- inserta_nodo(&ptrRaiz, 10);
- inserta_nodo(&ptrRaiz, 17);
- inserta_nodo(&ptrRaiz, 19);
- inserta_nodo(&ptrRaiz, 16);
- inserta_nodo(&ptrRaiz, 5);
- inserta_nodo(&ptrRaiz, 14);
- inserta_nodo(&ptrRaiz, 20);
- inserta_nodo(&ptrRaiz, 21);
- inserta_nodo(&ptrRaiz, 18);
- /*creo 2 nodos*/
- p1 = (TNodo*)malloc(sizeof(TNodo));
- p1->valor = 17;
- p1->ptrHI=p1->ptrHD=NULL;
- /*-----*/
- p2 = (TNodo*)malloc(sizeof(TNodo));
- p2->valor = 21;
- p2->ptrHI=p2->ptrHD=NULL;
- //asumo que me dan valores validos para los nodos
- //no me daran nodos que no existan ya que para eso
- // tendria que implementar una funcion que verifique
- // que existan
- Encontrar_camino(ptrRaiz,p1,p2);
- return (EXIT_SUCCESS);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement