calosc

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

typedef struct node
{
    int nr;
    struct node *nast;
    struct node *nastl;
    struct node *prev;
    struct node *rodzic;
    struct node *ost;
}node;

typedef node *tree;

int n;
tree t;
tree tab[];
void delete_subtree_pom(tree tmp2);

void ADD_NODE(int k)
{
    tree nowy;
    tree dany;
    tree poprz;
    dany=tab[k];
    nowy=malloc(sizeof(node));
    if(dany->nast==NULL)
    {
        dany->nast=nowy;
        dany->ost=nowy;
        nowy->rodzic=dany;
        nowy->prev=NULL;
        nowy->nast=NULL;
        nowy->nastl=NULL;
        ++n;
        nowy->nr=n;
        tab[n]=nowy;
        printf("OK\n");
    }
    else
    {
        poprz=dany->nast;
        nowy->prev=poprz;
        nowy->rodzic=dany;
        dany->nast=nowy;
        poprz->nastl=nowy;
        if(dany->ost!=poprz)
            poprz->rodzic=NULL;
        ++n;
        nowy->nr=n;
        nowy->nast=NULL;
        nowy->nastl=NULL;
        tab[n]=nowy;
        printf("OK\n");
    }
}

int RIGHTMOST_CHILD(int k)
{
    tree tmp;
    tmp=tab[k];
    if(tmp->nast==NULL)
    {
        printf("-1\n");
        return -1;
    }
    else
    {
        printf("%d\n", tmp->nast->nr);
        return tmp->nast->nr;
    }
}

void DELETE_NODE(int k)
{
    tree dany;
    tree next;
    tree tmp;
    tree ojciec;
    tree poprz;
    tree nextl;
    tree ostatni;
    dany=tab[k];
    if(dany->nast!=NULL)
    {
        next=dany->nast;
        ostatni=dany->ost;
        if(dany->nastl==NULL && dany->prev==NULL)
        {
            ojciec=dany->rodzic;
            if(next!=ostatni)
            {
                ojciec->nast=next;
                ojciec->ost=ostatni;
                next->rodzic=ojciec;
                ostatni->rodzic=ojciec;
            }
            else
            {
                ojciec->nast=next;
                ojciec->ost=ostatni;
                next->rodzic=ojciec;
            }
        }
        else if(dany->nastl==NULL)
        {
            poprz=dany->prev;
            poprz->nastl=ostatni;
            ostatni->prev=poprz;
            ojciec=dany->rodzic;
            ojciec->nast=next;
            next->rodzic=ojciec;
        }
        else if(dany->prev==NULL)
        {
            nextl=dany->nastl;
            next->nastl=nextl;
            nextl->prev=next;
            ojciec=dany->rodzic;
            ojciec->ost=ostatni;
            ostatni->rodzic=ojciec;
        }
        else
        {
            poprz=dany->prev;
            nextl=dany->nastl;
            nextl->prev=next;
            next->nastl=nextl;
            poprz->nastl=ostatni;
            ostatni->prev=poprz;
        }
    }
    else
    {
        if(dany->nastl==NULL && dany->prev==NULL && dany->rodzic!=NULL)
        {
            ojciec=dany->rodzic;
            ojciec->nast=NULL;
            ojciec->ost=NULL;
        }
        else if(dany->nastl==NULL && dany->rodzic!=NULL)
        {
            ojciec=dany->rodzic;
            poprz=dany->prev;
            ojciec->nast=poprz;
            poprz->rodzic=ojciec;
            poprz->nastl=NULL;
        }
        else if(dany->prev==NULL && dany->rodzic!=NULL)
        {
            ojciec=dany->rodzic;
            nextl=dany->nastl;
            nextl->prev=NULL;
            ojciec->ost=nextl;
            nextl->rodzic=ojciec;
        }
        else if(dany->prev!=NULL && dany->nastl!=NULL)
        {
            poprz=dany->prev;
            nextl=dany->nastl;
            poprz->nastl=nextl;
            nextl->prev=poprz;
        }
    }
    free(dany);
    printf("OK\n");
}

void DELETE_SUBTREE(int k)
{
    tree dany;
    tree tmp;
    tree ojciec;
    tree poprz;
    tree nextl;
    dany=tab[k];
    if(dany->nast!=NULL)
    {
        tmp=dany->nast;
        delete_subtree_pom(tmp);
    }
    if(dany->nastl==NULL && dany->prev==NULL && dany->rodzic!=NULL)
    {
        ojciec=dany->rodzic;
        ojciec->nast=NULL;
        ojciec->ost=NULL;
    }
    else if(dany->nastl==NULL && dany->rodzic!=NULL)
    {
        ojciec=dany->rodzic;
        poprz=dany->prev;
        ojciec->nast=poprz;
        poprz->rodzic=ojciec;
        poprz->nastl=NULL;
    }
    else if(dany->prev==NULL && dany->rodzic!=NULL)
    {
        ojciec=dany->rodzic;
        nextl=dany->nastl;
        nextl->prev=NULL;
        ojciec->ost=nextl;
        nextl->rodzic=ojciec;
    }
    else if(dany->prev!=NULL && dany->nastl!=NULL)
    {
        poprz=dany->prev;
        nextl=dany->nastl;
        poprz->nastl=nextl;
        nextl->prev=poprz;
    }
    free(dany);
    if(k!=0)
        printf("OK\n");
}

void delete_subtree_pom(tree tmp)
{
    tree tmp2;
    tree ojciec;
    if(tmp->nast!=NULL)
    {
        tmp2=tmp->nast;
        delete_subtree_pom(tmp2);
    }
    if(tmp->prev!=NULL)
    {
        tmp2=tmp->prev;
        delete_subtree_pom(tmp2);
    }
    if(tmp->nastl==NULL)
    {
        ojciec=tmp->rodzic;
        ojciec->nast=NULL;
        ojciec->ost=NULL;
        free(tmp);
    }
    else
    {
        ojciec=tmp->rodzic;
        tmp2=tmp->nastl;
        tmp2->prev=NULL;
        ojciec->ost=tmp2;
        tmp2->rodzic=ojciec;
        free(tmp);
    }
}

void SPLIT_NODE(int k, int w)
{
    tree nowy;
    tree danyw=tab[k];
    tree danypop=tab[w];
    tree tmp;
    tree tmp2;
    if(danypop->nastl==NULL)
    {
        ADD_NODE(k);
    }
    else
    {
        nowy=malloc(sizeof(node));
        tmp=danypop->nastl;
        tmp->prev=NULL;
        danypop->nastl=nowy;
        nowy->nastl=NULL;
        nowy->prev=danypop;
        nowy->rodzic=danyw;
        tmp->rodzic=nowy;
        nowy->ost=tmp;
        if(tmp->nastl==NULL)
        {
            nowy->nast=tmp;
        }
        else
        {
            tmp2=danyw->nast;
            tmp2->rodzic=nowy;
            nowy->nast=tmp2;
        }
        danyw->nast=nowy;
        ++n;
        nowy->nr=n;
        tab[n]=nowy;
        printf("OK\n");
    }
}
//***************************************
#ifndef DRZEWO_H
#define DRZEWO_H

typedef struct node
{
    int nr;
    struct node *nast;
    struct node *nastl;
    struct node *prev;
    struct node *rodzic;
    struct node *ost;
}node;

typedef node *tree;

extern int n;

extern tree t;

extern tree tab[];

extern void delete_subtree_pom(tree tmp2);

extern void ADD_NODE(int k);

extern int RIGHTMOST_CHILD(int k);

extern void DELETE_NODE(int k);

extern void DELETE_SUBTREE(int k);

extern void SPLIT_NODE(int k, int w);

#endif /* DRZEWO_H */
//***************************************************
#include <stdio.h>
#include<stdlib.h>

#include "drzewo.h"

int main(void)
{
    char nazwa;
    int numer;
    int pop;
    t=malloc(sizeof(node));
    t->nr=0;
    tab[0]=t;
    n=0;
    t->nast=NULL;
    t->nastl=NULL;
    t->prev=NULL;
    t->rodzic=NULL;
    while(scanf("%s %d", &nazwa, &numer)==2)
    {
        if((&nazwa)=="ADD_NODE")
        {
            ADD_NODE(numer);
        }
        else if((&nazwa)=="RIGHTMOST_CHILD")
        {
            RIGHTMOST_CHILD(numer);
        }
        else if((&nazwa)=="DELETE_NODE")
        {
            DELETE_NODE(numer);
        }
        else if((&nazwa)=="DELETE_SUBTREE")
        {
            DELETE_SUBTREE(numer);
        }
        else if((&nazwa)=="SPLIT_NODE")
        {
            scanf(" %d", &pop);
            SPLIT_NODE(numer, pop);
        }
    }
    DELETE_SUBTREE(0);
    return 0;
}