判断所给二叉树是否是红黑树_判断是否是红黑树

先总结下知识点。

红黑树就是带有颜色的平衡二叉搜索树加五个特殊属性

1，所有节点只能是红或黑色

2，所有叶子都是黑色，并且不存有效数据（如果你要自己构造一个红黑树，叶子节点设置为null就可以，其实就是你的结构存储完所有有效数据后把当前的叶子节点（这些叶子是存有有效数据的）当成内节点，给他们一个构造一个null的叶子节点）

3，根节点只能是黑色

4，每个红节点必有两个子黑节点，即不能有连续的两个红节点

5，树中任一节点到其子树内任意叶子的路径上黑色节点个数相同，此限制也使任意节点的两条叶子路径长度不超过2倍差别

如此，要判断一个给定的二叉树是不是红黑树就是要判断其是不是平衡搜索二叉树（BST)并且满不满足上面5个条件

结构类型：

#define RED 'r'
#define BLACK 'b'


typedef struct T
{
struct T * left;
struct T * right;
struct T * parent;
int key;
char colour;
int data;
}T;

根据输入文件里节点的数据创建红黑树：

void createR_B_BT(FILE* ft,T ** Root)
{
char buf[256]="";
char *ptr=buf,*qtr;
T * Node=NULL,*leaf=NULL;
T * ptrT[100];
int i=1;//,j=0;


memset(ptrT,0,sizeof(ptrT));
while(i==1)
{
i=fread(buf,256,1,ft);
printf("%s\n",buf);
while((ptr=strchr(ptr,'('))!=NULL)
{
Node= (T*)malloc(sizeof(T));
sscanf(ptr,"(%d,%d,%c)",&(Node->key),&(Node->data),&(Node->colour));
++ptr;
ptrT[Node->key]=Node;
}
}
*Root=ptrT[1];
ptrT[1]->parent=NULL;
ptrT[1]->left=NULL;
ptrT[1]->right=NULL;
for(i=2;i<=Node->key;i++)
{
if(ptrT[i]==NULL)
continue;
if(i%2==0)
{
ptrT[i]->parent=ptrT[i/2];
ptrT[i/2]->left=ptrT[i];
}
else
{
ptrT[i]->parent=ptrT[i/2];
ptrT[i/2]->right=ptrT[i];
}
ptrT[i]->left=NULL;
ptrT[i]->right=NULL;
}
}

判断是否是二叉搜索树：

bool  IsBST( T *Head ,int *Max,int *Min)
{ 

T* pNode = Head;
int nMax;
int nMin;
    if(pNode == NULL)
        return true;
if(pNode->left==NULL)
{
*Min=pNode->data;
}
else if(IsBST(pNode->left,&nMax,&nMin))
{
if(pNode->data >= nMax)
{
*Min=nMin;
}
else
return false;
}
else
return false;
if(pNode->right==NULL)
{
*Max=pNode->data;
}
else if(IsBST(pNode->right,&nMax,&nMin))
{
if(pNode->data <= nMin)
{
*Max=nMax;
}
else
return false;
}
else
return false;
return true;
}

判断是否是红黑树：
int  IsR_B_Tree(T *Node,int *result)
{
if(Node==NULL)return 0;
*result=1;
int numBlack_L=0;
int numBlack_R=0;
if(Node->colour!=BLACK && Node->colour!=RED)
{
printf("This is not a R&B_Tree: a node's colour is not red or black\n");
*result=0;
return -1;
}
if(Node->parent==NULL)
{
if(Node->colour!=BLACK)
{
printf("This is not a R&B_Tree: The root is not BLACK\n");
*result=0;
return -1;
}
}
else
{
if(Node->colour==RED && Node->parent->colour==RED)
{
printf("this is not R&B_Tree: a red node has a red child\n");
*result=0;
return -1;
}
}
if(*result!=0)
numBlack_L+=IsR_B_Tree(Node->left,result);
if(*result!=0)
numBlack_R+=IsR_B_Tree(Node->right,result);
if(*result==0)
return -1;
if(Node->left&&Node->left->colour==BLACK)
{
++numBlack_L;
}
if(Node->right&&Node->right->colour==BLACK)
{
++numBlack_R;
}
if( numBlack_L!=numBlack_R)
{
printf("this is not a R&B_Tree:  paths from a node to descendant leaves contain different number of black nodes\n");
*result=0;
return -1;
}
return numBlack_L;
}