#include <stdio.h>
typedef struct tree_data{
	char *sentence;
	int index;
}DATA;
typedef struct tree_elem{
	DATA dat;
	struct tree_elem *left,*right,*parrent;
}ELEM;
FILE * fp;

void show_tree(ELEM *head)
{
	ELEM *p;
	p=head;
	if(p!= NULL)
	{
		show_tree(p->right);
		puts(p->dat.sentence);
		printf("\n");
		show_tree(p->left);
	}
}

ELEM* find_elem(int ind,ELEM *root)
{
	ELEM *p = root;
	while(p!=NULL)
	{
		if(p->dat.index==ind)
		return root;
		if(ind>p->dat.index)
		p=p->right;
		else
		p=p->left;

	}
	printf("Elem isn't found\n");
	return NULL;

}

ELEM* del_elem(ELEM* root,int ind)
{
	ELEM *p,*x,*y;
	p=find_elem(ind,root);
	if(p->left!=NULL&&p->right!=NULL)
	{
		y=p->right;
		x=NULL;
		if(y==y->parrent->left)
		{
			y->parrent->left=NULL;
		}
		else
		{
			y->parrent->right=NULL;
		}
		p->dat=y->dat;
	}
		 if(p->left!=NULL||p->right!=NULL)
				{
					y=p;
					if(y->left!=NULL)
					x=y->left;
					else
					x=y->right;
				}
					else
					{
						y=p;
						x=NULL;
					}

		if(x!=NULL)
		x->parrent=y->parrent;
		if(y->parrent==NULL)
		root=x;
		else{
			if(y==y->parrent->left)
			y->parrent->left=x;
			else
			y->parrent->right=x;
		}
	return root;
}

ELEM* add_elem(ELEM* root,char *sent,int ind)
{	ELEM *x = (ELEM*)malloc(sizeof(ELEM));
	x->dat.index=ind;
	x->dat.sentence=sent;
	ELEM *pointer;
	ELEM *pointer_prev;
	if(!root)
	{	x->parrent=NULL;
		x->left=NULL;
		x->right=NULL;
		return x;
	}
	else{
		pointer=root;
		pointer_prev=root;
		while(pointer)
		{
			pointer_prev=pointer;
			if((x->dat.index)>(pointer->dat.index))
			pointer=pointer->right;
			else
			pointer=pointer->left;
		}
			if((x->dat.index)>(pointer_prev->dat.index))
			{x=pointer_prev->right;
				x->parrent=pointer_prev;
			}
			else
			{x=pointer_prev->left;
				x->parrent=pointer_prev;
			}
	}
}

int main()
{
	fp = fopen("D:\\C-Free 5\\Projects\\Tree\\text.txt","r");
	ELEM* head=NULL;
	char buf [150];
	while(!feof(fp))
	{	int num;
		fgets(buf,10,fp);
		num = atoi(buf);
		//int *p;
		//while((p=fgetc(fp))!='\n')
	 //	num=num*10+(*p-'0');
	 	fgets(buf,150,fp);
	 	char *sent = strdup(buf);
	 	head = add_elem(head,sent,num);

	}
	return 0;
}