Tree Traversal

[eirrag]

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

# define clrscr() printf("\033[H\033[2J");
struct treeNode
{ 
	struct treeNode *leftPtr; 
	int data; 					
	struct treeNode *rightPtr;
};

typedef struct treeNode TreeNode; 
typedef TreeNode *TreeNodePtr; 

struct queueNode {
   TreeNodePtr data;                 /* define data as a char */
   struct queueNode *nextPtr; /* queueNode pointer */
}; /* end structure queueNode */

typedef struct queueNode QueueNode;
typedef QueueNode *QueueNodePtr;


void insertNode( TreeNodePtr *treePtr, int value );
void inOrder( TreeNodePtr treePtr );
void preOrder( TreeNodePtr treePtr );
void postOrder( TreeNodePtr treePtr );
void delete ( TreeNodePtr treePtr, int value );
TreeNodePtr binaryTreeSearch( TreeNodePtr treePtr, int value );
void printTree( TreeNodePtr treePtr, int space );
void levelOrder(TreeNodePtr treePtr);
//void instructions(void);
void enqueue( QueueNodePtr *headPtr, QueueNodePtr *tailPtr, TreeNodePtr value );
int isEmpty( QueueNodePtr headPtr );

int main()
{ 
	int i; 
	int item,del; 
	int choice;
	TreeNodePtr rootPtr = NULL; 
	TreeNodePtr	returnPtr = NULL;
	
   srand( time( NULL ) ); 
   printf( "The numbers being placed in the tree are:\n" );

   
   for ( i = 1; i <= 10; i++ ) { 
      item = rand() % 15;
     printf( "%3d", item );
      insertNode( &rootPtr, item );
   } 

  
   printf( "\n\nThe preOrder traversal is:\n" );
   preOrder( rootPtr );

   
   printf( "\n\nThe inOrder traversal is:\n" );
   inOrder( rootPtr );

  
   printf( "\n\nThe postOrder traversal is:\n" );
   postOrder( rootPtr );

while(choice!=5)
{
	printf("\n\n\t\t*PLEASE PRESS THE NUMBER OF YOUR CHOICE*\n\n");
	printf("1 - level order traversal || 2 - delete || 3 - search || 4 - display || 5 - exit\n\n");
	scanf("%d", &choice);
	clrscr();
	switch (choice)
	       {
			case 1:
				levelOrder( rootPtr );
				break;
			case 2:
				printf("\n\nplease enter the number to be deleted\n");
				scanf("%d", &del);
				delete( rootPtr, del );
				
				printf("after the deletion\n\n");
				
				printf( "\n\nThe preOrder traversal is:\n" );
				preOrder( rootPtr );
				printf( "\n\nThe inOrder traversal is:\n" );
				inOrder( rootPtr );
				printf( "\n\nThe postOrder traversal is:\n" );
				postOrder( rootPtr );
				break;
			case 3:
				printf("enter the number to search\n");
				scanf("%d", &del );
				returnPtr = binaryTreeSearch( rootPtr, del );
				if( returnPtr == 0)
				{
					printf("\n");
				}
				else
				{
					printf("the pointer is %d\n", returnPtr->data );
				}
				break;
			case 4:
				printTree( rootPtr, 0 );
				break;
			
			default:
				printf("Program ends here.\n\n");
				break;
		}
	}
	

	return 0; 

}
	            
	       
	
void insertNode( TreeNodePtr *treePtr, int value )
{ 
   
   
	if ( *treePtr == NULL )
	{   
		*treePtr = malloc( sizeof( TreeNode ) );

		
		if ( *treePtr != NULL )
		{ 
			( *treePtr )->data = value;
			( *treePtr )->leftPtr = NULL;
			( *treePtr )->rightPtr = NULL;
		}
		else
		{
			printf( "%d not inserted. No memory available.\n", value );
		}
	
	}
	else
	{
		
		if ( value < ( *treePtr )->data )
		{
			insertNode( &( ( *treePtr )->leftPtr ), value );
		}
		
		else if ( value > ( *treePtr )->data )
		{
			insertNode( &( ( *treePtr )->rightPtr ), value );
		}
		
	}

}


void inOrder( TreeNodePtr treePtr )
{ 

  
   if ( treePtr != NULL ) 
   { 
      inOrder( treePtr->leftPtr );
      printf( "%3d", treePtr->data );
      inOrder( treePtr->rightPtr );
   }

}


void preOrder( TreeNodePtr treePtr )
{ 

  
   if ( treePtr != NULL ) 
   { 
      printf( "%3d", treePtr->data );
      preOrder( treePtr->leftPtr );
      preOrder( treePtr->rightPtr );
   } 

}


void postOrder( TreeNodePtr treePtr )
{ 

  
   if ( treePtr != NULL ) 
   { 
      postOrder( treePtr->leftPtr );
      postOrder( treePtr->rightPtr );
      printf( "%3d", treePtr->data );
   }

}
//void instructions(void)
//{
	 // printf("Enter you choice");
	//   printf("\n\n1 for delete || 2 for search || 3 for display|| 4 for exit\n\n");
//}
	
void delete( TreeNodePtr treePtr, int value )
{
	int root; 
	int direction;
	
	TreeNodePtr prePtr = NULL; //  parent node
	TreeNodePtr tempPtr = NULL; //  with 2 childs
	TreeNodePtr pPtr = NULL; 
	
	if( treePtr == NULL )
	{
		printf("no data inserted");
	} 
	else
	{
		root = 0;
		while( value != treePtr->data )
		{
			root = 1;
			prePtr = treePtr;
			
			if( value < treePtr->data )
			{
				direction = 0;
				if( treePtr->leftPtr == NULL )
				{
					printf("dos not exist\n");
					break;
				}
				else
				{
					treePtr = treePtr->leftPtr;
				}
			}
			else if(value > treePtr->data )
			{
				direction = 1;
				if( treePtr->rightPtr == NULL )
				{
					printf("does not  exist\n");
					break;
				}
				else
				{
					treePtr = treePtr->rightPtr;
				}
			}
		}
		
		if( value == treePtr->data )
		{
			if( treePtr->leftPtr == NULL && treePtr->rightPtr == NULL ) 
			{
				if( direction == 0 )
				{
					prePtr->leftPtr = NULL;
				}
				else if( direction == 1 )
				{
					prePtr->rightPtr = NULL;
				}	
			}
			else if( treePtr->leftPtr == NULL || treePtr->rightPtr == NULL ) // one children
			{
				if( treePtr->leftPtr == NULL )
				{
					if( direction == 0 )
					{
						prePtr->leftPtr = treePtr->rightPtr;
					}
					else if( direction == 1 )
					{
						prePtr->rightPtr = treePtr->rightPtr;
					}
					
				}
				else if( treePtr->rightPtr == NULL )
				{
					if( direction == 0 )
					{
						prePtr->leftPtr = treePtr->leftPtr;
					}
					else if( direction == 1 )
					{
						prePtr->rightPtr = treePtr->leftPtr;
					}
				}
			}
			
			else if( treePtr->leftPtr != NULL && treePtr->rightPtr != NULL ) // two childs
			{
				tempPtr = treePtr->leftPtr; 
				while( tempPtr->rightPtr != NULL ) 
				{
					pPtr = tempPtr;  
					tempPtr = tempPtr->rightPtr;
				}
				
				if( tempPtr->rightPtr == NULL && tempPtr->leftPtr == NULL )
				{
					if( direction == 0 )
					{
						prePtr->leftPtr = tempPtr;
					}
					else if( direction == 1 )
					{
						prePtr->rightPtr = tempPtr;
					}
					tempPtr->rightPtr = treePtr->rightPtr;
					tempPtr->leftPtr = treePtr->leftPtr;
					pPtr->rightPtr = NULL;
				}
				else if( tempPtr->rightPtr == NULL && tempPtr->leftPtr != NULL )
				{
					if( direction == 0 )
					{
						prePtr->leftPtr = tempPtr;
					}
					else if( direction == 1 )
					{
						prePtr->rightPtr = tempPtr;
					}
					pPtr->rightPtr = tempPtr->leftPtr;
					tempPtr->rightPtr = treePtr->rightPtr;
					tempPtr->leftPtr = treePtr->leftPtr;
					
				}
			}
		}
	}

}

TreeNodePtr binaryTreeSearch( TreeNodePtr treePtr, int value )
{
	while( value != treePtr->data )
	{

		printf("%d -> ",treePtr->data );
		if( value > treePtr->data )
		{
			if( treePtr->rightPtr == NULL )
			{
				printf("item doesnt exist\n");
				break;
			}
			else
			{
				treePtr = treePtr->rightPtr;
			}
		}
		else if( value < treePtr->data )
		{
			if( treePtr->leftPtr == NULL )
			{
				printf("item doesnt exist\n");
				break;
			}
			else
			{
				treePtr = treePtr->leftPtr;
			}
		}
		
	}
	printf("\n");
	if( value == treePtr->data )
	{
		printf("number succesfully searched\n");
		return treePtr;
	}
	else
	{
		printf("number not found\n");
		return treePtr = NULL;

	}
}

void printTree( TreeNodePtr treePtr, int space )
{
	int x;
	while( treePtr != NULL )
	{ 
		printTree ( treePtr->rightPtr, space + 5 );
		for( x = 1; x <= space; x++ )
		{
			printf(" ");
		}
		printf( "%d\n",treePtr->data );
		treePtr = treePtr->leftPtr;
		space = space + 5;
	}
}
void levelOrder( TreeNodePtr treePtr )
{
	QueueNodePtr headPtr = NULL;
	QueueNodePtr tailPtr = NULL;
	
	enqueue( &headPtr, &tailPtr, treePtr );

	while( headPtr != NULL )
	{
		printf("%d \t", headPtr->data->data);
		if( headPtr->data->leftPtr != NULL )
		{
			enqueue( &headPtr, &tailPtr, headPtr->data->leftPtr);
		}
		if( headPtr->data->rightPtr != NULL )
		{
			enqueue( &headPtr, &tailPtr, headPtr->data->rightPtr );
		}
		headPtr = headPtr->nextPtr;
	}
}

void enqueue( QueueNodePtr *headPtr, QueueNodePtr *tailPtr, TreeNodePtr value )
{
	QueueNodePtr newPtr;

   newPtr = malloc( sizeof( QueueNode ) );

   if ( newPtr != NULL ) 
   { 
      newPtr->data = value;
      newPtr->nextPtr = NULL;


      if ( isEmpty( *headPtr ) )
       {
         *headPtr = newPtr;
      }
      else 
      {
         ( *tailPtr )->nextPtr = newPtr;
      }

      *tailPtr = newPtr;
   }
   else 
   {
      printf( "%d not inserted. No memory available.\n", value->data );
   }
}

int isEmpty( QueueNodePtr headPtr )
{
	return headPtr == NULL;
}