我几乎完成了一棵红黑树,但我的删除出现故障。它可能会删除一个它可能不会删除的节点。在我删除根目录并按下打印选项后,我的屏幕上充斥着我在树中已有的节点。在测试树中,2,1,7,5,8,11,14,15,4
如果我删除root=7
并按我得到的按顺序打印2,4,5,8,1,2,4,5,8,1,.....
等等,直到程序崩溃。如果我删除 2,程序会立即崩溃。节点 11 像 1-4-15 一样删除所有叶子。我试图通过调试找到问题,但一切似乎都正常。该代码基于 Cormen 对算法的介绍。谢谢!
void RB_delete(struct node* z,struct node* y) //delete z y=z on call
{
struct node *x;
enum type originalcolor; //x moves into y's original position
originalcolor=y->color; // Keep track of original color
if (z->LC==nill) //case 1: (z has no LC)
{
x=z->RC;
RB_transplant(z,z->RC);
else if (z->RC==nill) //case 2: z has LC but no RC
{
x=z->LC;
RB_transplant(z,z->LC);
}
else // two cases: z has both Children
{
y=tree_minimum(z->RC); //find successor
originalcolor=y->color; //save color of successor
x=y->RC;
if (y->P==z) //successor has no LC cause its nill
x->P=y;
else
{
RB_transplant(y,y->RC);
y->RC=z->RC;
y->RC->P=y;
}
RB_transplant(z,y);
y->LC=z->LC;
y->LC->P=y;
y->color=z->color;
}
if (originalcolor == black)
RB_delete_fix(x);
free(z);
}
void io_print(struct node *aux,struct node *auxnill)
{
HANDLE hConsole;
hConsole = GetStdHandle(STD_OUTPUT_HANDLE);
if(aux != auxnill)
{
io_print(aux->LC,auxnill);
if (aux->color==red)
{
SetConsoleTextAttribute(hConsole, 12);
printf("%d,\n",aux->key);fflush(stdout);
SetConsoleTextAttribute(hConsole, 15);
}
if (aux->color==black)
{
SetConsoleTextAttribute(hConsole, 9);
printf("%d,\n",aux->key);fflush(stdout);
SetConsoleTextAttribute(hConsole, 15);
}
io_print(aux->RC,auxnill);
}
}