#include <iostream>
#include<cstdlib>

using namespace std;

class kulka
{
public:
    int wartosc;
    int numer;
    kulka* prawa=NULL;
    kulka *lewa=NULL;
    kulka* next=NULL;

    kulka( int nr)
    {
        numer=nr;
        wartosc=rand()%100;
    }

    void lista(kulka* nowa)
    {
        if(nowa->wartosc < next-> wartosc)
        {
            if(next)
            {
                nowa->next=next;
                next=nowa;
            }
            else
                next->lista(nowa);
        }
        else
            {
                next=nowa;
            }

    }

    void show_lista()
    {
        cout<<"numer :"<<numer<<" "<<wartosc<<endl;
        if(next)
            next->show_lista();
    }

        void show_lista_rosnaco()
    {
        if(next)
            next->show_lista();
        cout<<"numer :"<<numer<<" "<<wartosc<<endl;

    }

    int zliczenie(int &suma)
    {
        suma=suma+wartosc;
        if(next)
            next->zliczanie(suma);

        return suma;
    }


    void drzewo(kulka *nowa)
    {
        if(nowa-> wartosc < wartosc)
            {
                if(lewa)
                    {
                    lewa->drzewo(nowa);
                    }
                else
                lewa=nowa;

            }
            else
            {
                if(prawa)
                   {
                       prawa->drzewo(nowa);
                   }
                   else
                    prawa=nowa;
            }
    }

    void show_drzewo()
    {
        if(lewa)
                lewa->show_drzewo();

            cout<<"numer: "<<numer<<" "<<wartosc<<endl;

        if(prawa)
            prawa->show_drzewo();
    }


};


int main()
{
    kulka*root_p=NULL;
    kulka*root_np=NULL;
    kulka*root=NULL;

        for(int i=0 i<30; i++)
        {
            kulka *nowa=new kulka(i);

                if (root==NULL)
                {
                    root=nowa;
                }
                else
                {

                 if(nowa->wartosc < root-> wartosc)
                    {
                    nowa->next=root;
                    root=nowa;
                    }
                else
                    root->lista(nowa);

                }
        }


cout<<"cala lista malejaco: "<<endl;
root->show_lista();
cout<<endl;

cout<<"cala lista rosnaco: "<<endl;
root->show_lista_rosnaco();
cout<<endl;


// dodawanie lista parzysta i nieparzytsa


kulka*pom=root;

while(roo->next)
{
pom=root;
pom->next=NULL;
    if(pom->wartosc%2==0)
    {
        if(root_p==NULL)
            root_p=pom;
        else
            root_p->lista(pom);
    }
    else
    {
        if(root_np==NULL)
            root_np=pom;
        else
            root_np->lista(pom);
    }

}

 if(root->wartosc%2==0)
    root_p->lista(root);
    else
    root_np->lista(root);


 cout<<"lista parzytsa malejaco"<<endl;
 root_p->show_lista();
 cout<<endl;

cout<<"lista parzytsa rosnaco"<<endl;
 root_p->show_lista_rosnaco();
 cout<<endl;



 cout<<"lista nieparzytsa malejaco"<<endl;
 root_np->show_lista();
 cout<<endl;

cout<<"lista nieparzytsa rosnaco"<<endl;
 root_np->show_lista_rosnaco();
 cout<<endl;



int sum=0;

	cout << "suma wartosci listy nieparzystej" << endl;
	cout << root_np->zliczanie(sum);

	cout << endl;

	cout << "suma wartosci calej listy" << endl;
	cout << root_p->zliczanie(sum);

	cout << endl;

	//drzewo z listy parzystej

	kulka *pom_drzewo1=NULL;
	kulka *root_drzewo=NULL;

	while(root_p->next)
	{
		pom_drzewo1=root_p;
		root_p=root_p->next;
		pom_drzewo1->next=NULL;
		if(root_drzewo==NULL)
		  root_drzewo=pom_drzewo1;
		else
		  root_drzewo->drzewo(pom_drzewo1);
	}

	if(root_p)
	  root_drzewo->drzewo(root_p);

	cout << "drzewo z listy parzystej" << endl;
	root_drzewo->show_drzewo();

	cout << endl;

	//drzewa z dwoch list

	kulka *pom_drzewo2=NULL;

	while(root_np->next)
	{
		pom_drzewo2=root_np;
		root_np=root_np->next;
		pom_drzewo2->next=NULL;
		root_drzewo->drzewo(pom_drzewo2);
	}

	if(root_np)
	  root_drzewo->drzewo(root_np);

	cout << "drzewo z obu list" << endl;
	root_drzewo->show_drzewo();


	return 0;
}