#include<iostream>
#include<cstdlib>
using namespace std;

class kulka
{
	public:
	int value_1, value_2;
	kulka *next;
	kulka *left;
	kulka *right;
	kulka(int arg)	 //konstruktor
	{
		value_1=rand()%100;
		value_2=arg;
		next=NULL;
		left=NULL;
		right=NULL;
	}
	void show()  //wyswietlanie
	{
		cout<<endl<<"Wartosc 1: "<<value_1<<"    Wartosc 2: "<<value_2<<"    ";
		if(next!=NULL) next->show();
	}

	void show_tree()
	{
		if(left!=NULL)   left->show_tree();
		else             cout<<"v1="<<value_1<<"  v2="<<value_2<<"  ";
		if(right!=NULL)  right->show_tree();
		else             cout<<"v1="<<value_1<<"  v2="<<value_2<<"  ";
	}

//////////////////////////////////////////////////////////////////////////////////
	void add(kulka *nowa)    //dodawanie na liste
	{
		if(next==NULL)  next=nowa;  //gdy nie ma nexta dodaje kulke na koniec
		else
		{
			if(nowa->value_1 < next->value_1)
			{
				nowa->next=next;
				next=nowa;
			}
			else next->add(nowa);
		}
	}
//////////////////////////////////////////////////////////////////////////////////
	void add_tree(kulka *nowa)  //dodawanie na drzewo
	{
		if(nowa->value_1 <= this->value_1)
		{
			if(this->left==NULL)
			{
				nowa->right=this;
				this->left=nowa;
			}
			else left->add_tree(nowa);
		}
		else
		{
			if(nowa->value_1 > this->value_1)
			{
				if(this->right==NULL)
				{
					nowa->left=this;
					this->right=nowa;
				}
				else  right->add_tree(nowa);
			}
		}
	}
};

int main()
{
	kulka *nowa=NULL;
	kulka *lista=NULL;
	kulka *drzewo=NULL;
	int arg;
	cout<<endl<<"Podaj wartosc 2: ";   //tworzenie pierwszej kulki
	cin>>arg;
	nowa=new kulka(arg);
	while(nowa->value_1 != nowa->value_2)
	{
		if(nowa->value_1 > nowa->value_2)    //gdy val1 > val2 dodaje na liste
		{
			if(lista==NULL)
			{
				nowa->next=lista;
				lista=nowa;
			}
			else
			{
				if(nowa->value_1 < lista->value_1)
				{
					nowa->next=lista;
					lista=nowa;
				}
				else lista->add(nowa);
			}
			lista->show();
		}

		else                        //gdy val1 < val2 dodaje na drzewo
		{
			if(drzewo==NULL)   drzewo=nowa;
			else
			{
				if(nowa->value_1 <= drzewo->value_1)
				{
					if(drzewo->left==NULL)
					{
						nowa->right=drzewo;
						drzewo->left=nowa;
					}
					else drzewo->add_tree(nowa);
				}
				else
				{
					if(drzewo->right==NULL)
					{
						nowa->left=drzewo;
						drzewo->right=nowa;
					}
					else drzewo->add_tree(nowa);
				}
			}
			cout<<"Drzewo:  "<<endl;
		//	drzewo->show_tree();
		}

		cout<<endl<<"Podaj wartosc 2: ";   //tworzenie kolejnej kulki
		cin>>arg;
		nowa=new kulka(arg);
	}
	return 0;
}