# Demo entry 6657641

q

Submitted by q on Nov 04, 2017 at 06:23
Language: C. Code size: 6.0 kB.

```#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define RED 1
#define BLACK 0
#define MAXSIZE 30           //the max length of array

typedef struct Node* PNode;  //the point which points to the node
struct Node
{
int key;                 //the element
PNode Left;              //the point which points to its left child
PNode Right;             //the point which points to its right child
int color;               //the color of the node
};

PNode create_tree(int a[],int l,int r);   //create a binary tree, and return the root
int is_root_black(PNode T);               //(2) to judge whether the root is black
int red_single(PNode T);                  //(3) to judge whether a red node's father and children are red
int same_black(PNode T);                  //(5) to judge whether all simple path contains same number of black nodes
int count_black(PNode T,int count,int n); //subfunction of same_black
void is_BRT(PNode T);                     //to judge 5 properties

int main()
{
int looptimes,i,j,N;
int a[MAXSIZE];
PNode BT;

scanf("%d",&looptimes);
for(i=0;i<looptimes;i++)
{
scanf("%d",&N);
for(j=0;j<N;j++)
scanf("%d",&a[j]);              //to store the numbers into an array
BT=create_tree(a,0,N-1);
is_BRT(BT);
}
system("pause");
}

// PNode create_tree(int a[],int l,int r)
// *************
// input:    an array which stores the information of nodes;
//           l and r which represent the subscript of the array;
// function: create a tree using the number from a[l] to a[r];
// procedure:
//     1. first create a root which stores a[l]
//     2. if the number is positive, then the node is black
//        if the number is negative, then the node is red
//     3. if l>r, then the left subtree or the right subtree is empty
//     4. look for the subscript "t" which guarantees a[t]>a[l]
//        if there is no such t, then t=r+1, return to the case "l>r"
//     6. recursive left subtree and right subtree

PNode create_tree(int a[],int l,int r)
{
int i,t;
PNode root;

root=(PNode)malloc(sizeof(struct Node));
if(a[l]>0)
{
root->key=a[l];
root->color=BLACK;
}
else if(a[l]<0)
{
root->key=-a[l];
root->color=RED;
}

if(l>r) return NULL;

for(i=l+1;i<=r;i++)
{
if(abs(a[i])>abs(a[l]))
break;
}
t=i;
root->Left=create_tree(a,l+1,t-1);
root->Right=create_tree(a,t,r);
return root;
}

// int is_root_black(PNode T)
// *********
// input:    a point which points to the tree;
// function: to check whether the root is black;

int is_root_black(PNode T)
{
if(!T)  return 1;
if(T)
{
if(T->color==BLACK) return 1;
else return 0;
}
}

// int red_single(PNode T)
// **********
// input:    a point which points to the tree;
// function: to check whether the red node's father or son is red;
// procedure:
//     1. check whether the tree is empty, empty tree also meets the requirements;
//     2. if the red node's father or son is red, return 0;
//     3. recursive left subtree and right subtree;
//     4. if there is no chance to return 0, then return 1

int red_single(PNode T)
{
PNode P=T;
if(!T)  return 1;
if(P->color==RED)
{
if(P->Left&&P->Left->color==RED) return 0;
if(P->Right&&P->Right->color==RED) return 0;
}
return (red_single(P->Left)&&red_single(P->Right));
return 1;
}

// int same_black(PNode T)
// **********
// input:    a point which points to the tree;
// output:   1 (success) or 0 (fail)
// function: to check whether each paths contains same number of black nodes;
// procedure:
//     1. if the tree is empty, return 1;
//     2. if the root is red, fails to meet requirement (3), return 0;
//     3. choose the leftmost path to be the standard;
//     4. run subfunction: count_black;
//     5. add 1 for the node "NULL";

int same_black(PNode T)
{
PNode P=T;
int num_of_black=0;

if(!P)  return 1;
if(P->color==RED) return 0;
if(P->color==BLACK)
{
num_of_black++;
P=P->Left;
while(P)
{
if(P->color==BLACK)
num_of_black++;
P=P->Left;
}
}
num_of_black++;
return count_black(T,0,num_of_black);
}

// int same_black(PNode T)
// **********
// input:    a point which points to the tree;
//           count;
//           standard number of black nodes;
// output:   1 (success) or 0 (fail)
// function: subfunction of same_black;
// procedure:
//     1. while the node is not NULL, recursive left subtree and right subtree;
//     2. if the node is NULL, add 1 for "NULL", and check whether count==standard;
//     3. if the node is black, count++;

int count_black(PNode T,int count,int num_of_black)
{
if(!T)
{
count++;
if(count!=num_of_black) return 0;
else return 1;
}
if(T->color==BLACK)
count++;
return (count_black(T->Left,count,num_of_black)&&
count_black(T->Right,count,num_of_black));
}

// void is_BRT(PNode T)
// **********
// input:    a point which points to the tree;
// output:   print "Yes" for success; or "No" for fail
// function: to check whether the tree meets all the requirements;

void is_BRT(PNode T)
{
if (is_root_black(T)&&red_single(T)&&same_black(T))
printf("Yes\n");
else printf("No\n");
}
```

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.