程序填空题：IsRBTree

IsRBTree (3)

The functions `IsRBTree` is to check if a given binary search tree `T` is a red-black tree. Return `true` if `T` is, or `false` if not.

The red-black tree structure is defined as the following:

```
typedef enum { red, black } colors;
typedef struct RBNode *PtrToRBNode;
struct RBNode{
int Data;
PtrToRBNode Left, Right, Parent;
int BH; /* black height */
colors Color;
};
typedef PtrToRBNode RBTree;
```

Please fill in the blanks.

```c++
bool IsRBTree( RBTree T )
{
int LeftBH, RightBH;
if ( !T ) return true;
if ( T->Color == black ) T->BH = 1;
else {
if ( T->Left && (T->Left->Color == red)) return false;
if ( T->Right && @@[(T->Right->Color == red)](2) ) return false;
}
if ( !T->Left && !T->Right ) return true;
if ( @@[IsRBTree( T->Left ) && IsRBTree( T->Right )](2)) {
if ( T->Left ) LeftBH = T->Left->BH;
else LeftBH = 0;
if ( T->Right ) RightBH = T->Right->BH;
else RightBH = 0;
if ( LeftBH == RightBH ) {
@@[T->BH += LeftBH](2);
return true;
}
else return false;
}
else return false;
}
```






答案：
第1空：(T->Right->Color == red)

第2空：IsRBTree( T->Left ) && IsRBTree( T->Right )

第3空：T->BH += LeftBH