[AiSD] 7. BST

#include <iostream>
using namespace std;

struct wezel{
    wezel *left;
    wezel *right;
    wezel *parent;
    int key;
};

void preorder(wezel *root)
{
    if(root)
    {
        cout<<root->key<< " ";
        preorder(root->left);
        preorder(root->right);
    }
}

void inorder(wezel *root)
{
    if(root)
    {
        inorder(root->left);
        cout<<root->key<< " ";
        inorder(root->right);
    }
}

void postorder(wezel *root)
{
    if(root)
    {
        postorder(root->left);
        postorder(root->right);
        cout<<root->key<< " ";
    }
}

void dodaj(wezel *&root, int key)
{
    wezel *p;
    p = new wezel;
    p->key = key;
    if(root == NULL)
    {
        root = p;
        root->left = 0;
        root->right = 0;
        root->parent = 0;
    }
    else
    {
        wezel *x, *q;
        x = root;
        q = 0;
        while(x != 0)
        {
            q = x;
            if(p->key < x->key)
                x = x->left;
            else
                x = x->right;
        }
        if(p->key < q->key)
        {
            q->left = p;
            p->parent = q;
        }
        else
        {
            q->right = p;
            p->parent = q;
        }
        p->left = 0;
        p->right = 0;
    }
}

wezel *maximum(wezel * root)
{
    if(root == NULL)
        return NULL;
    while(root->right)
        root = root->right;
    return root;
}

wezel *minimum(wezel * root)
{
    if(root == NULL)
        return NULL;
    while(root->left)
        root = root->left;
    return root;
}

wezel *nastepnik(wezel * root)
{
    wezel * r;
    if(root)
    {
        if(root->right)
            return minimum(root->right);
        else
        {
            r = root->parent;
            while(r && (root == r->right))
            {
                root = r;
                root = root->parent;
            }
            return r;
        }
    }
    return root;
}

wezel *poprzednik(wezel * root)
{
    wezel * r;
    if(root)
    {
        if( root->left)
            return maximum(root->left);
        else
        {
            r = root->parent;
            while(r && (root == r->left))
            {
                root = r;
                r = r->parent;
            }
            return r;
        }
    }
    return root;
}

void searchBST(wezel *root, int key)
{
    if(root == NULL)
        cout<<"[SZUKAJ] Wartosc: "<<key<< " nie wystepuje w BST"<<endl;
    else if(root && root->key == key)
    {
        cout<<"[SZUKAJ] Wartosc: "<<key<< " wystepuje w BST"<<endl;
    }
    else
    {
        if(key < root->key)
            searchBST(root->left, key);
        else
            searchBST(root->right, key);
    }
}

wezel *szukaj(wezel *root, int key)
{
    while(root && root->key != key)
    {
        if(key < root->key)
            root = root->left;
        else
            root = root->right;
    }
    return root;
}

void removeWezel(wezel *& root, wezel *X)
{
    wezel *Y, *Z;
    if(X)
    {
        // Jeśli X nie ma synów lub ma tylko jednego, to Y wskazuje X
        // Inaczej Y wskazuje następnik X
        Y = !X->left || !X->right ? X : nastepnik(X);
        // Z wskazuje syna Y lub NULL
        Z = Y->left ? Y->left : Y->right;
        // Jeśli syn Y istnieje, to zastąpi Y w drzewie
        if(Z)
            Z->parent = Y->parent;
        // Y zostaje zastąpione przez Z w drzewie
        if(!Y->parent)
            root = Z;
        else if(Y == Y->parent->left)
            Y->parent->left  = Z;
        else
            Y->parent->right = Z;
        // Jeśli Y jest następnikiem X, to kopiujemy dane
        if(Y != X)
            X->key = Y->key;
        delete Y;
    }
}

bool deleteWezel(wezel *& root, int key)
{
    wezel *p, *q;
    p = root;
    q = 0;
    while(p!=0 && key != p->key){
        q = p;
        if(key > p->key)
            p = p->right;
        else
            p = p->left;
    }
    //p wskazuje element do usuniecia, q - poprzedni element
    if( p == 0 )    //jesli BST jest puste
        return false;
    if( p->left == 0 || p->right == 0 ) //jesli NIE ma przynajmniej jednego potomka
    {
        if( p->left == 0 )  //jesli nie ma lewego
        {
            if( q == 0 )    //jak usuwamy korzen
                root = p->right;    //nowy korzen
            else{
                if( key > q->key )  //jestesmy w prawym poddrzewie
                    q->right = p->right;
                else                //jestesmy w lewym poddrzewie
                    q->left = p->right;
            }
        }
        else    //jesli jest lewy
        {
            if( q == 0 )    //jak usuwamy korzen
                root = p->left;
            else{
                if( key > q->key)   //jestesmy w prawym poddrzewie
                    q->right = p->left;
                else                //jestesmy w lewym poddrzewie
                    q->left = p->left;
            }
        }
    }
    else    //jesli ma obu potomkow
    {
        wezel *naj, *pnaj;
        naj = p->left;
        pnaj = p;
        while( naj->right != 0 ){
            pnaj = naj;
            naj = naj->right;
        }
        if( pnaj->left == 0 )
            pnaj->right = naj->left;
        else
            pnaj->left = naj->left;
        if( p->left != naj ){
            naj->left = p->left;
            naj->right = p->right;
        }
        if( q == 0 )
            root = naj;
        else{
            if( key > q->key )
                q->right = naj;
            else
                q->left= naj;
        }
        delete p;
    }
  return true;
}




int main(){

    wezel *root = 0;
    dodaj(root,5);
    dodaj(root,7);
    dodaj(root,3);
    dodaj(root,10);
    dodaj(root,8);
    dodaj(root,13);
    dodaj(root,1);
    dodaj(root,4);

    inorder(root);

    cout<<endl;
    cout<<maximum(root)->key<<endl;
    cout<<minimum(root)->key<<endl;
    removeWezel(root, szukaj(root,3));
    deleteWezel(root, 5);

    inorder(root);
    return 0;
}