ImpossibleAlgoTrans

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

struct stack{
    struct stack* Top;
    void * elem;
};
typedef struct stack* Stack;

struct tree{
    int K;
    struct tree* Dx;
    struct tree* Sx;
};
typedef struct tree* Tree;


Stack pop(Stack S){
    if(S != NULL){
        Stack tmp=S;
        S= S->Top;
        free(tmp);
    }
    return S;
}

Stack push(Stack S, void * E){
    Stack TMP=NULL;
    if( S == NULL ){
        TMP=(Stack)malloc(sizeof(struct stack));
        TMP->elem= E;
        TMP->Top=NULL;
    }
    else{
        TMP=(Stack)malloc(sizeof(struct stack));
        TMP->elem= E;
        TMP->Top= S;

    }
    return TMP;
}

void * top(Stack S){
    if(S != NULL){
        return S->elem;
    }
    return NULL;
}

Tree addDx(Tree T, int K){
    if(T == NULL){
        T= (Tree)malloc(sizeof(struct tree));
        T->K=K;
        T->Dx= NULL;
        T->Sx= NULL;
    }
    else{
        T->Dx= addDx(T->Dx, K);
    }
    return T;
}

Tree addSx(Tree T, int K){
    if(T == NULL){
        T= (Tree)malloc(sizeof(Tree));
        T->K=K;
        T->Dx= NULL;
        T->Sx= NULL;
    }
    else{
        T->Sx= addSx(T->Sx, K);
    }
    return T;
}

void Cancella_Tree(Tree T){
    printf("Sono stata invocata su %d!", T->K);
    return ;
}

int AlgoRic(Tree T, int h){
    int ret=-1;
    int s=0;
    int d=0;
    if (T != NULL){
        if(T->Sx != NULL){
            s= AlgoRic(T->Sx, h+1);
        }
        if(T->Dx != NULL){
            d= AlgoRic(T->Dx, h+1);
        }
        if( s == 0 && d == 0){
            ret=h;
        }
        else{
            ret=s+d;
        }
    }
    return ret;
}

int AlgoIt(Tree T, int h){
    Stack S_r=NULL, S_t=NULL, S_s=NULL, S_d=NULL, S_ir=NULL;
    Tree currT=T;
    Tree last=T;
    Tree nextT=NULL;
    int ret=-1;
    int currH=h;
    int nextH=0;
    int s=0;
    int d=0;
    int prevs=0;
    int prevd=0;

    while( currT != NULL || S_ir != NULL){
        if(currT != NULL){

            if( currT->Sx != NULL){
                S_t=push(S_t, (void*) currT);
                S_ir=push(S_ir, (void*) 1);
                nextH=currH+1;
                nextT=currT->Sx;
                s=0;
                d=0;
                ret=-1;
            }
            else if( currT->Dx != NULL ){
                S_t=push(S_t, (void*) currT);
                S_ir=push(S_ir, (void*) 0);
                nextH=currH+1;
                nextT=currT->Dx;
                s=0;
                d=0;
                ret=-1;
            }
            else{
                nextT=NULL;
                s=0;
                d=0;
                ret=-1;
                nextH=currH+1;//3(NULL)
            }
        }
        else{
            int ir= top(S_ir);
            S_ir=pop(S_ir);
            currT=(Tree)top(S_t);
            currH=currH-1;//2

            printf("FIRST|CURR:%d|S:%d|D:%d|H:%d\n",currT->K,s,d, currH);


            if( s == 0 && d == 0){
                ret=currH;
            }
            else{
                ret=s+d;
            }
                printf("RET:%d\n",ret);

            if(ir == 1){
                s=ret;
                if(currT->Dx != NULL){ // scnedo a DX
                    S_s=push(S_s,(void *) s);
                    S_ir=push(S_ir, (void*) 0);
                    nextT=currT->Dx;
                    nextH=currH;
                    s=0;
                    d=0;
                    ret=-1;
                }
                else{ //Risalgo da SX
                    d= top(S_s);
                    S_t=pop(S_t);
                    nextT=NULL;
                    nextH=currH;

                }
            }
            else{ // Risalgo da DX
                d=ret;
                s=top(S_s);
                S_s=pop(S_s);
                S_t=pop(S_t);
                nextT=NULL;
                nextH=currH;
            }
            printf("SECOND|CURR:%d|S:%d|D:%d|H:%d\n\n",currT->K,s,d, currH);
        }
        currT=nextT;
        currH=nextH;
    }

    return ret;
}

void visita(Tree T){
    if(T != NULL){
        visita(T->Sx);
        visita(T->Dx);
        printf("%d\n", T->K);
    }
}

int main(){
    Tree t= NULL;
    Tree t1= NULL;
    t1= addDx(t1, 1);
    t1= addDx(t1, 3);
    t1= addDx(t1, 6);
    t1= addDx(t1, 5);
    t1= addSx(t1, 2);
    t1= addSx(t1, 4);
    // Secondo albero di test-----------------
    t=addDx(t,1);
    t=addSx(t,2);
    t=addDx(t,3);
    addSx(t->Dx,4);
    int r=0;
    printf("OUTPUT 1:\n");
    r=AlgoRic(t, 1);
    printf("R_RIC:%d\n", r);
    printf("----EOF-----\n\n");
    printf("OUTPUT 2:\n");
    r=AlgoIt(t, 1);
    printf("R_ITR:%d\n", r);
    printf("----EOF-----\n\n");
    visita(t);

    return 0;
}