红黑树的创建+线索化+性质检验+笔画输入法(三)
left_rotate(root, z->p->p);
return;
}
else if( z == z->p->left)
{
z = z->p;
right_rotate(root, z);
z->p->color = Black;
z->p->p->color = Red;
left_rotate(root, z->p->p);
}
}
else
{
if(y->color == Red)
{
z->p->color = Black;
y->color = Black;
z->p->p->color = Red;
z = z->p->p;
}
else
{
if( z == z->p->left)
{
z = z->p;
right_rotate(root, z);
}
z->p->color = Black;
z->p->p->color = Red;
left_rotate(root, z->p->p);
}
}
}
}
(*root)->color = Black;
}
void check_rb_tree_child(RedBlackTree root, int i)
{
if(root->color == Red && root->left != NULL && root->right != NULL)
{
if(root->left->color == Black && root->right->color == Black)
{
}
else printf("9\n");
}
if(root->left != NULL)
{
check_rb_tree_child(root->left, i + 1);
}
if(root->right != NULL)
{
check_rb_tree_child(root->right, i + 1);
}
}
BOOL check_rb_tree(RedBlackTree root)
{
int i = 0;
if(root->color == Red)
{
printf("root ERR!\n");
return 1;
}
check_rb_tree_child(root, ++i);
return 0;
}
void check_black_num(RedBlackTree root, int n)
{
if(root == NULL)
{
printf("%d \n", n);
}else
{
if(root->color == Black)
{
n+=1;
}
check_black_num(root->left, n);
check_black_num(root->right, n);
}
}
void inorder_traverse_rb_tree(RedBlackTree root)
{
RedBlackNode *p = NULL;
p = root->left;
while(p != root)
{
while(p->ltag == Link)
{
p = p->left;
}
printf("%s\n",p->data.bihua);
while(p->rtag == Thread && p->right != root)
{
p = p->right;
printf("%s\n",p->data.bihua);
}
p = p->right;
}
}
void negative_inorder_traverse_rb_tree(RedBlackTree root)
{
RedBlackNode *p = NULL;
p = root->right;
while(p != root)
{
while(p->rtag == Link)
{
p = p->right;
}
printf("%s\n",p->data.bihua);
while(p->ltag == Thread && p->left != root)
{
p = p->left;
printf("%s\n",p->data.bihua);
}
p = p->left;
}
}
void InThreading(RedBlackTree p, RedBlackTree * pre)
{
if(p)
{
InThreading(p->left, pre);
if(p->left == NULL)
{
p->ltag = Thread;
p->left = *pre;
}
if((*pre)->right == NULL)
{
(*pre)->rtag = Thread;
(*pre)->right = p;
}
(*pre) = p;
InThreading(p->right, pre);
}
}
void inorder_threading_rb_tree(RedBlackTree *thrt, RedBlackTree root)