Wstęp do Programowania, semestr zimowy, 2018/2019

void wstaw_pierwszy_lisc(stack<drzewo *> &s, drzewo *d) {
    while(d!=NULL) {
        s.push(d);
        if (d->lsyn != NULL)
            d = d->lsyn;
        else
            d = d->psyn;
    }
}

void nastepny_lisc(stack<drzewo *> &s) {
    drzewo *d = s.top(); s.pop();
    while((s.size() > 0) && ((s.top()->psyn==NULL) || (s.top()->psyn==d))) {
        d = s.top(); s.pop();
    }
    if ((s.size() > 0) && (s.top()->psyn!=NULL)) {
        wstaw_pierwszy_lisc(s, s.top()->psyn);
    }
}

int wspolne_liscie_ze_stosem(drzewo *d1, drzewo *d2) {
    stack<drzewo *> s1;
    stack<drzewo *> s2;
    int wynik = 0;
    wstaw_pierwszy_lisc(s1, d1);
    wstaw_pierwszy_lisc(s2, d2);
    while(!s1.empty() && !s2.empty()) {
        drzewo *w1 = s1.top();
        drzewo *w2 = s2.top();
        assert(w1->lsyn==NULL && w1->psyn==NULL);
        assert(w2->lsyn==NULL && w2->psyn==NULL);
        if (w1->w == w2->w) {
            wynik++;
            nastepny_lisc(s1);
            nastepny_lisc(s2);
        } else if (w1->w > w2->w) {
            nastepny_lisc(s2);           
        } else {
            nastepny_lisc(s1);
        }
    }
    return wynik;
}