红黑树的创建、插入和删除等源代码 (三)
f ( w->lchild->color == BLACK && w->rchild->color == BLACK ) // case 2
{
w->color = RED;
x = x->parent;
}
else
{
if ( w->lchild->color == BLACK )
{
w->color = RED;
w->rchild->color = BLACK;
LeftRotate( w );
w = x->parent->lchild;
}
w->color = x->parent->color;
x->parent->color = BLACK;
w->lchild->color = BLACK;
RightRotate( x->parent );
x = root;
}
} //end if
} //end while
x->color = BLACK;
}
TreeNode* RB_Tree::RB_Delete( TreeNode *z )
{
TreeNode *y = Nil;
TreeNode *x = Nil;
if ( z->lchild == Nil || z->rchild == Nil )
{
y = z;
}
else
{
y = TreeSuccessor( z );
}
if ( y->lchild != Nil )
{
x = y->lchild;
}
else if ( y->rchild != Nil )
{
x = y->rchild;
}
x->parent = y->parent;
if ( y->parent == Nil )
{
x = root;
}
else if ( y == y->parent->lchild )
{
y->parent->lchild = x;
}
else if ( y == y->parent->rchild )
{
y->parent->rchild = x;
}
if ( y != z )
{
z->key = y->key;
}
if ( y->color == BLACK )
{
RB_DeleteFixUp( x );
}
return y;
}
void RB_Tree::PrintElem( TreeNode *x )
{
cout << x->key << "(" << x->color << ")" << " ";
}
void RB_Tree::LevelOrderTraverse()
{
queue q;
if ( root != Nil )
{
q.push( root );
}
while ( !q.empty() )
{
TreeNode *x = q.front();
PrintElem( x );
if ( x->
lchild != Nil )
{
q.push( x->lchild );
}
if ( x->rchild != Nil )
{
q.push( x->rchild );
}
q.pop();
}
}
void RB_Tree::PreOrderTraverse()
{
stack stk;
TreeNode *p = root;
while ( p != Nil || !stk.empty() )
{
while ( p != Nil )
{
PrintElem( p );
stk.push( p );
p = p->lchild;
}
if ( !stk.empty() )
{
p = stk.top()->rchild;
stk.pop();
}
}
}
void RB_Tree::InOrderTraverse()
{
stack stk;
TreeNode *p = root;
while ( p != Nil || !stk.empty() )
{
while ( p != Nil )
{
stk.push( p );
p = p->lchild;
}
if ( !stk.empty() )
{
PrintElem( stk.top() );
p = stk.top()->rchild;
stk.pop();
}
}
}
void RB_Tree::PostOrderTraverse()
{
stack stk;
TreeNode *pre = Nil;
TreeNode *cur = Nil;
stk.push( root );
while ( !stk.empty() )
{
cur = stk.top();
if ( ( cur->lchild == Nil && cur->rchild == Nil ) ||
( pre != Nil && ( pre == cur->lchild || pre == cur->rchild ) ) )
{
PrintElem( cur );
pre = cur;
stk.pop();
}
else
{
if ( cur->rchild != Nil )
{
stk.push( cur->rchild );
}
if ( cur->lchild != Nil )
{
stk.push( cur->lchild );
}
}
}
}