Demo entry 6655736

C

   

Submitted by vayne on Oct 27, 2017 at 19:49
Language: C. Code size: 6.6 kB.

/*
 * File: RBTree.c
 * -------------
 * This program firstly allow you to enter some numbers
 * to build an binary search tree, then it will judge whether
 * the Tree is a Red-Black Tree. If it is, the program will
 * output "Yes\n", else it will out put"No\n" 
 */
#include <stdio.h>
#include <stdlib.h>

/*
 * Constants
 * ---------
 * The following constants control the ...
 *  in the display.
 */
#define BOOL int
#define TRUE  1
#define FALSE 0
#define RED   0
#define BLACK 1

/*
 * The following code form
 * the node struct of the 
 * Tree in the display.
 */
typedef struct TreeNode *PtrToNode;
typedef PtrToNode RBTree;
struct TreeNode
{
	int 	Element;  	//Store the Element number
	int		NodeColor;	//Store the color of the Node
	RBTree	Left;		//store point to the node's left child tree
	RBTree 	Right; 		//store point to the node's right child tree
};

/*
 * Function: BuildTree
 * Usage: Tree = BuildTree();
 * -----------------------
 * This function Build an 
 * Binary search tree(RBT) 
 * on account of your input
 * and return the root node
 */
RBTree BuildTree( void );

/*
 * Function: Insert
 * Usage: Tree = Insert(Element,Tree);
 * -----------------------
 * This function Insert the Element
 * into the Binary search tree and
 * decide the color of the node 
 * and return the tree Node
 */
RBTree Insert( int Element, RBTree CurTree );

/*
 * Function: CheckTree 
 * Usage: BOOL IsRBT = CheckTree(CurTree->Left, CurTree->Color, &LBlackNum); 
 * -----------------------
 * This function is to judge whether 
 * the binary search tree satisfy the 
 * requirement of the Red-Black tree 
 * if yes ,it return Ture, else, 
 * return False.(the third arguements 
 * is to judge whether the number of 
 * Blacknodes in left child tree is 
 * equal to it in Right child tree)
 */
BOOL CheckTree( RBTree CurTree, int LastColor, int *BlackNum );

/*
 * Function: MakeEmpty
 * Usage: Tree = MakeEmpty(Tree);
 * -----------------------
 * This function free the Binary search
 * tree when the judge is finished. 
 * Avoiding the waste of space.
 */
RBTree MakeEmpty( RBTree CurTree );


//The Main program
int main( void )
{
	int CaseNum; //The number of the case need to test
	scanf_s("%d", &CaseNum);
	if( CaseNum <= 0 )
	{
		printf("Your input is Wrong. "
			"The question need a positive interger");
	}

	while( CaseNum > 0 )
	{
		CaseNum--;// One Case has been checked
		RBTree CaseTree = BuildTree();//Build the Tree on account of the input
		
		// To check whether the root is Black
		if( CaseTree == NULL || CaseTree->NodeColor == RED ) 
		{
			printf("No\n"); //If not ,output No
			continue;		//go to next case
		}
		int BlackNum = 0;	//the variable is no use
		//it is only to satisfy the usage of the function: CheckTree
		
		//To check whether the Tree satisfy the requirements
		BOOL IsRBT = CheckTree(CaseTree, BLACK, &BlackNum);
		
		//out put the Yes or No on account of the result
		if( IsRBT == TRUE )
		{
			printf("Yes\n");
			continue;
		}
		else if( IsRBT == FALSE )
		{
			printf("No\n");
			continue;
		}
		
		//when the Check is over ,Free the CaseTree
		MakeEmpty( CaseTree );
	}
	
	return 0;
} 

RBTree BuildTree( void )
{
	int NodeNum;//The number of Node in the Tree need to input
	scanf_s("%d", &NodeNum);
	
	if( NodeNum <= 0 ) // if input is wrong ,return NULL
	{
		return NULL;
	}
	
	RBTree CurTree = NULL;//initalize the Tree;
	int Element;// store the ELement of the Node
	
	// begin to Build Tree
	while( NodeNum > 0 )
	{
		NodeNum--;	//One Node has been insert
		scanf_s("%d", &Element);
		CurTree = Insert( Element, CurTree );//Insert the num in to the Tree
	}
	
	return CurTree;
}

RBTree Insert( int Element, RBTree CurTree )
{
	 // if the CurTree is NULL, Create and return a one Node tree
	if( CurTree == NULL )
	{
		CurTree = (RBTree)malloc(sizeof(struct TreeNode));//Apply for a memory space
		//initalize the Node
		CurTree->Left = NULL;
		CurTree->Right = NULL;
		//if it is a Red Node
		if( Element < 0 )
		{
			CurTree->NodeColor = RED;
			CurTree->Element = Element * -1;
		}
		else//if it is a Black Node
		{
			CurTree->NodeColor = BLACK;
			CurTree->Element = Element;
		}
	}//if the number is smaller than the current element number, insert it into the left child Tree
	else if( abs(Element) < CurTree->Element )
	{
		CurTree->Left = Insert(Element, CurTree->Left);
	}//if the number is bigger than the current element number, insert it into the Right child Tree
	else if( abs(Element) > CurTree->Element )
	{
		CurTree->Right = Insert(Element, CurTree->Right);
	}
	//else the X is in Tree Already; we will do nothing
	
	return CurTree;
}

RBTree MakeEmpty( RBTree CurTree )
{
	//I think the function MakeEmpty is so easy 
	//to understand so I don't add Note in it.
	if( CurTree != NULL )
	{
		MakeEmpty(CurTree->Left);
		MakeEmpty(CurTree->Right);
		free(CurTree);
	}
	return NULL;
}

BOOL CheckTree( RBTree CurTree, int LastColor, int *BlackNum )
{
	//If Now the Tree is NULL, we think it is True and make the BlackNum as 0;
	if(CurTree == NULL) 
	{
		*BlackNum = 0;
		return TRUE;
	}
	
	//if the Red Node's child is not Black, it is not a Red-Black tree,and it Return False
	if( LastColor == RED && CurTree->NodeColor == RED )
	{
		return FALSE;
	}
	int LBlackNum;//store the num of the left child tree's BlackNode
	int RBlackNum;//store the num of the Right child tree's BlackNode
	
	//if it's left child Tree or Right child tree is not a Red-Black
	//tree,It can't be a Red-Black Tree, we return False
	if( CheckTree(CurTree->Left, CurTree->NodeColor, &LBlackNum) == FALSE )
	{
		return FALSE;
	}
	if( CheckTree(CurTree->Right, CurTree->NodeColor, &RBlackNum) == FALSE )
	{
		return FALSE;
	}
	
	//if the Number of the Black nodes in Left child tree is not equal to it in Right child tree
	//it doesn't satisfy the requirement of the Red-Black tree, so it return false
	if( LBlackNum != RBlackNum )
	{
		return FALSE;
	}
	
	//if the above requirements are all satisfied
	//first we return back(by the pointer) the number of black Nodes in that child Black Tree
	*BlackNum = LBlackNum;
	if( CurTree->NodeColor == BLACK )
	{
		*BlackNum += 1;
	}
	// then we return TRUE
	return TRUE;
	
	//by the recursive function we finish the judge of the Red-Black Tree
	//ps:the all Note :number of Black nodes means the Number of black
	//nodes in one path from the node to the NULL,not the all Black node nums.
}

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).