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.

Delete this entry (admin only).