bstree.c

数据结构基础（ C）： splay 树； BS 树； AVL 树

/*Binary Search Tree*/
#include<stdio.h>
#include <time.h>
clock_t  start, stop; /* clock_t is a built-in type for processor time (ticks) */
double  duration;  /* records the run time (seconds) of a function */
struct BSTreeNode { int Num;
			  struct BSTreeNode* Left;
			  struct BSTreeNode* Right;	/*Declaration*/
			};                     
typedef  struct BSTreeNode* Tree; 
Tree Root=NULL;/*initial empty tree */

int BSTree_Isempty(Tree root)    /* test empty */
{
	return (root==NULL);
}


Tree BSTree_FinMax( Tree root)
{ 
	if(!BSTree_Isempty(root))
	{ 
	while(root->Right!=NULL)	/*find the max */
		root=root->Right;
	return root;
	}									
	else
	{
	printf("NO MAX IN NULL\n");
	return(NULL);
	}
}
Tree BSTree_Insert( int key, Tree root)
{	
	if(BSTree_Isempty(root))
	{ 
		root=(Tree)malloc(sizeof(struct BSTreeNode));
		root->Num=key;
		root->Left=root->Right=NULL; /*for a empty tree */
	}
	else
	{	if(key<root->Num)
			root->Left =BSTree_Insert( key , root->Left );
		if(key>root->Num)
			root->Right=BSTree_Insert( key , root->Right);/*non-empty recurse in the subtree */
		
	}
	return(root);

}

Tree BSTree_Delete( int key, Tree root)
{   
	Tree temp;
	if(!BSTree_Isempty(root))
	{ 
		if(key<root->Num)		/*non-empty recurse in the subtree */
			root->Left =BSTree_Delete( key , root->Left );
		else if(key>root->Num)
			root->Right=BSTree_Delete( key , root->Right);
		else if(key==root->Num) 
		{				/*find the node to delete */
			if(root->Left!=NULL&&root->Right!=NULL)
			{
				
				temp=BSTree_FinMax( root->Left);
				root->Num=temp->Num; /*use the max in left sub to replace the deleted*/
				root->Left=BSTree_Delete(temp->Num,root->Left);
			}
			else
				if(root->Left==NULL)
				{
					temp=root;
					root=root->Right;  /*has no subtree */
				    	free(temp);
				}
				else if(root->Right==NULL)
				{	
					temp=root;
					root=root->Left;
				    	free(temp);
				}
		}
		return (root);	/*not in the tree do nothing */
	}

	else			/*for a empty tree */
	{
		printf("CAN'T DELETE %d\n",key);
		return(NULL);
	}
}
void input()
{
	int i,key;
	int n=1;
	while(n>=0)/*if n is negative stop */
	{
		scanf("%d", &n);
		if(n>=0 && n<=10001)/*if n is negative stop ; more than 10000 ineffect test*/
		{	
			for(i=1;i<=n;i++)/*read in n  integer to insert */
			{
				scanf("%d",&key);
				Root=BSTree_Insert (key,Root);
			}
			for(i=1;i<=n;i++)
			{
				scanf("%d",&key); /*read in n  integer to delete */
				Root=BSTree_Delete (key,Root);
			}
		
		}
		else continue;

	}
}
void output(Tree root)			/* inorder travesal*/
{
	if(root!=NULL)
	{	
		output(root->Left);
		printf("%d\n",root->Num);
		output(root->Right);
	}
}
int main ( )
{	
	int i;
	/* clock() returns the amount of processor time (ticks) that has elapsed
		since the program began running */
	start = clock(); 	/* records the ticks at the beginning of the function call */
	for(i=0;i<=100;i++)
	{
	freopen("Input.txt","r",stdin);
    freopen("Output.txt","w",stdout);
	input();
	output(Root); 		
	}
	stop = clock();	/* records the ticks at the end of the function call */
	duration = ((double)(stop - start))/CLK_TCK; 
											/* CLK_TCK is a built-in constant = ticks per second */
	printf("%lf",duration);/*the whole time*/
	return 1;
}