#include <assert.h>

struct UzelStromu {
    int data;

    UzelStromu *levy, *pravy;

    UzelStromu(const int hodnota) {
        data = hodnota;
        levy = NULL;
        pravy = NULL;
    }
};

struct BinarniStrom {
    UzelStromu *koren;

    BinarniStrom() {
        koren = NULL;
    }

    bool pridejPrvek(const int hodnota);

    bool najdiPrvek(const int hodnota);

    void smazPrvek(const int hodnota);

    ~BinarniStrom();


    /****
     * Pomocne metody
     */
protected:


    bool hledejPrvek(const UzelStromu* podstrom,
            const int hodnota,
            UzelStromu** predchudce,
            UzelStromu** prvek);
    
    void smazPodstrom( UzelStromu* podstrom );
    
    void smazList( UzelStromu* prvek, UzelStromu* predchudce );
    
    void smazVeVetvi( UzelStromu* prvek, UzelStromu* predchudce );
    
    void smazVeStromu(UzelStromu* prvek)

};

bool BinarniStrom::hledejPrvek( UzelStromu* podstrom,
                                const int hodnota,
                                UzelStromu** predchudce,
                                UzelStromu** prvek)
{
    if (podstrom != NULL)
    {        
        if (podstrom->data == hodnota)
        {
            (*prvek) = podstrom;
            return true;
        }
        (*predchudce)=podstrom;
        if (podstrom->data < hodnota)
            return hledejPrvek(podstrom->levy, hodnota, predchudce, prvek);
        else
            return hledejPrvek(podstrom->pravy, hodnota, predchudce, prvek);
    }    
    *prvek = NULL;
    return false;
}

bool BinarniStrom::pridejPrvek(const int hodnota)
{
    if (koren == NULL)
    {
        koren = new UzelStromu(hodnota);
        return true;
    }
    UzelStromu * predchudce, *prvek;
    if (hledejPrvek(koren, hodnota, &predchudce, &prvek))
        return false;
    if (predchudce->data<hodnota)
        predchudce->pravy=new UzelStromu(hodnota);
    else
       predchudce->levy= new UzelStromu(hodnota);
    return true;
}

bool BinarniStrom::najdiPrvek(const int hodnota)
{
    UzelStromu *predchudce, *prvek;
    return hledejPrvek(koren, hodnota, &predchudce, &prvek);
}

void BinarniStrom::smazPodstrom( UzelStromu* podstrom )
{
    if(podstrom->levy!=NULL){
        smazPodstrom(podstrom->levy);}
    if(podstrom->pravy!=NULL){
        smazPodstrom(podstrom->pravy);}
    delete podstrom;
}

BinarniStrom::~BinarniStrom()
{
    if( koren != NULL ) smazPodstrom( koren );
}

bool BinarniStrom::smazPrvek(const int hodnota)
{
    
    UzelStromu *predchudce, *prvek;
    predchudce = NULL;
    prvek = NULL;
    
    if(hledejPrvek(koren, hodnota, &predchudce, &prvek)==false) 
    {
        return false;
    }
    
    if ( prvek->pravy == NULL && prvek->levy == NULL) 
    {
        smazList(prvek, predchudce );
        return true;
    }
    
    if ( prvek->pravy != NULL && prvek->levy != NULL)
    {
        smazVeStromu(prvek, predchudce);
        return true;
    }
    
    smazVeVetvi(prvek, predchudce);
    return true;   
}
void BinarniStrom::smazList(UzelStromu* prvek, UzelStromu* predchudce)
{
    assert( prvek->levy == NULL && prvek->pravy == NULL );
    if (predchudce->levy == prvek)
        predchudce->levy = NULL;
    else
        predchudce->pravy = NULL;       
    delete prvek;
}
void BinarniStrom::smazVeVetvi(UzelStromu* prvek, UzelStromu* predchudce)
{
    assert( ( prvek->pravy == NULL && prvek->levy != NULL ) ||
            ( prvek->pravy != NULL && prvek->levy == NULL ) );
    UzelStromu* nasledovnik;
    if (prvek->levy == NULL)
        nasledovnik = prvek->pravy;
    else
        nasledovnik = prvek->levy;
    
    UzelStromu** spoj;
    
    if (predchudce->levy == prvek)
        spoj = &predchudce->levy;
    else
        spoj = &predchudce->pravy;
    
    *spoj = nasledovnik;
    delete prvek;
}
void BinarniStrom::smazVeStromu(UzelStromu* prvek)
{
    assert( prvek->pravy != NULL && prvek->levy != NULL );
    UzelStromu *pomocny, *predchudce;
    pomocny = prvek->levy;
    predchudce = prvek;
    while (pomocny->pravy != NULL)
    {
        predchudce = pomocny;
        pomocny = pomocny->pravy;
    }
    prvek->data = pomocny->data;
    if (pomocny->levy == NULL)
        smazList (pomocny, predchudce);
    else
        smazVeVetvi (pomocny, predchudce);
}

void BinarniStrom::zapisPodstrom( UzelStromu* podstrom, Soubor s )
{
    if( podstrom != NULL )
    {
        s.zapis( podstrom->data );
        zapisPodstrom( podstrom->levy, s );
        zapisPodstrom( podstrom->pravy, s);
    }
}

void BinarniStrom::zapis( Soubor s )
{
    zapisPodstrom( koren, s );
}