红黑树插入操作的C++实现(2)

}
/*
将一棵红黑树按照层次结构输出
*/
ostream& operator<<(ostream& os,const Tree& tree)
{
TreeNode* root=tree.getRoot();
if(!root)
return os;
vector<TreeNode*> outQueue;
outQueue.push_back(root);
int level=0;
while(outQueue.size()>0)
{
vector<TreeNode*> tempQueue=outQueue;
outQueue.clear();
os<<"[ level= "<<level<<" ] { ";
for(int i=0;i<tempQueue.size();i++)
{
TreeNode* node=tempQueue[i];
TreeNode* parent=node->parent;
Color color=tempQueue[i]->getColor();
int value=node->getValue();
cout<<" [ "<<value;
if(node->getLeftChild()!=TreeNode::NIL)
outQueue.push_back(node->getLeftChild());
if(node->getRightChild()!=TreeNode::NIL)
outQueue.push_back(node->getRightChild());
if(color==red)
cout<<" red ";
else
cout<<" black ";
if(parent)
{
cout<<" parent ="<<parent->value;
if(node==parent->lchild)
cout<<" left ";
else
cout<<" right ";
}
else
cout<<" root";
cout<<" ] ";
}
os<<" }"<<endl;
level++;
tempQueue.clear();
}
return os;
}
/*
检查树是否符合红黑树的五条规定
同时还检查父子节点之间的数值大小是否符合二叉查找树的规定
父子节点之���的指针是否指向正确
*/
bool Tree::check_tree()
{
vector<TreeNode*> nodes;
/*
保存所有的指向叶子节点的节点，用于计算比较从此节点往上是否符合规则5
由于NIL是一个共享的节点，所以这里用指向NIL的节点来验证规则5
*/
vector<TreeNode*> leafs;
bool result=true;
if(!root)
return result;
nodes.push_back(root);
int i=0;
while(result&&i<nodes.size())
{
TreeNode* p=nodes[i];
if(p->lchild==TreeNode::NIL) //如果左子树为叶子
{
leafs.push_back(p);
/*如果右子树不为叶子。右子树也为叶子的情况在上一条语句中已经包含*/
if(p->rchild!=TreeNode::NIL) 
{
nodes.push_back(p->rchild);
result=result&&(p==p->rchild->parent);
result=result&&(p->value<=p->rchild->value);
}
}
else //如果左子树不为叶子
{
nodes.push_back(p->lchild);
result=result&&(p==p->lchild->parent);
result=result&&(p->value>=p->lchild->value);
if(p->rchild==TreeNode::NIL) //如果右子树为叶子
leafs.push_back(p);
else //左右子树都不是叶子
{
result=result&&(p==p->rchild->parent);
result=result&&(p->value<=p->rchild->value);
nodes.push_back(p->rchild);
}
}
if(p->color==red)
result=result&&(p->lchild->color==black)&&(p->rchild->color==black);
i++;
}
int num=-1;
for(i=0;result&&(i<leafs.size());i++)
{
if(num==-1)
num=leafs[i]->get_black_num();
else
result=result&&(num==leafs[i]->get_black_num());
}
return result;
}
int main()
{
Tree tree;
int testData[]={15,13,2,34,53,12,21,23,52,75,46,72,19,24,87,98,1,3,31,28,123,214,512,5,78,98};
tree.insert(testData,sizeof(testData)/sizeof(int));
cout<<tree<<endl;
}