代码如下：
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <stdbool.h>
typedef struct node
{
unsigned long int val;
bool black;
struct node* parent;
struct node* lchild;
struct node* rchild;
}mynode;
mynode* createNode(unsigned long int ival, mynode* father);
mynode* createLeaf(unsigned long int ival, mynode* father);
mynode* search (unsigned long int ival, mynode *root);
void insert ( unsigned long int ival, mynode *root);
mynode * getFather (mynode* child);
mynode * getUncle (mynode* child);
void doubleRotate (mynode* myptr);
void rotate(mynode* myptr);
void myRotate(mynode* myptr);
void changeRed(mynode* myptr);
void changeBlack(mynode* myptr);
void colorFlip( mynode* myptr);
void subtreeRepair (mynode* myptr);
bool isRoot(mynode* myptr);
void rootRepair (mynode* myptr);
void repair (mynode* myptr);
bool isRed (mynode* myptr);
void smallRotate(mynode* myptr);
int main()
{
mynode myroot;
mynode *myrootptr;
mynode *myleafptr;
FILE *fp;
int ch;
unsigned long long lines=0, i=0;
unsigned long *myArr;
unsigned long int ival;
fp = fopen("integers.txt","r");
if(fp == NULL)
{
printf("Error in opening file.");
return(-1);
}
while(!feof(fp))
{
ch = fgetc(fp);
if(ch == 'n')
{
lines++;
}
}
lines++;
printf("lines = %lu", lines);
myArr = (unsigned long*)calloc(lines, sizeof(unsigned long));
fseek(fp, 0, SEEK_SET);
while(!feof(fp))
{
fscanf(fp, "%lu,", &myArr[i] ); // des ta pos k giati tou input.
i++;
}
fclose(fp);
myroot.val = myArr[0];
myroot.parent = NULL;
myroot.lchild = NULL;
myroot.rchild = NULL;
myroot.black = true;
myrootptr = &myroot;
myleafptr = createLeaf(myrootptr->val, myrootptr);
myrootptr->lchild = myleafptr;
myleafptr = createLeaf(myrootptr->val, myrootptr);
myrootptr->rchild = myleafptr;
for(i=1; i<lines; i++)
{
ival = myArr[i];
insert(ival, myrootptr);
}
return 0;
}
mynode* createNode(unsigned long int ival, mynode* father)
{
mynode* nodeptr = (mynode* )malloc(sizeof(mynode));
nodeptr->val = ival;
nodeptr->lchild = NULL;
nodeptr->rchild = NULL;
nodeptr->parent = father;
nodeptr->black = false;
return nodeptr;
}
mynode* createLeaf(unsigned long int ival, mynode* father)
{
mynode* leafptr = (mynode* )malloc(sizeof(mynode));
leafptr->val = ival;
leafptr->lchild = NULL;
leafptr->rchild = NULL;
leafptr->parent = father;
leafptr->black = true;
return leafptr;
}
mynode* search (unsigned long int ival, mynode *rootptr)
{
mynode* myptr = (mynode* )malloc(sizeof(mynode));
myptr = rootptr;
while ( ( (myptr->lchild) != NULL) && ( (myptr->rchild) != NULL))
{
if ( ival < myptr->val)
{
myptr = myptr->lchild;
}
else
{
myptr = myptr->rchild;
}
}
return myptr;
}
void insert (unsigned long int ival, mynode *root)
{
mynode * current = (mynode* )malloc(sizeof(mynode));
mynode * insertleafptr = (mynode* )malloc(sizeof(mynode));
mynode * father = (mynode* )malloc(sizeof(mynode));
unsigned long int max, min;
unsigned long int num;
current = search(ival, root);
num = current->val;
if((current->val) == ival)
{
return ;
}
else
{
if(ival>(current->val))
{
max = ival;
min = current->val;
}
else
{
max = current->val;
min = ival;
}
father = current->parent;
current = createNode(min, father);
if(num == (father->lchild)->val)
{
father->lchild = current;
}
else
{
father->rchild = current;
}
insertleafptr = createLeaf(min, current);
current->lchild = insertleafptr;
insertleafptr = createLeaf(max, current);
current->rchild = insertleafptr;
repair(current);
return ;
}
}
mynode * getFather (mynode* child)
{
return child->parent;
}
mynode * getUncle (mynode* child)
{
mynode * randNode1 = (mynode* )malloc(sizeof(mynode));
mynode * randNode2 = (mynode* )malloc(sizeof(mynode));
randNode1 = getFather(child);
randNode2 = getFather(randNode1);
if((randNode1->val) == ((randNode2->lchild)->val))
{
return randNode2->rchild;
}
else
{
return randNode2->lchild;
}
free(randNode1);
}
bool isRed (mynode* myptr)
{
if ((myptr->black) != true)
{
return true;
}
else
{
return false;
}
}
void changeColor (mynode* myptr)
{
if ((myptr->black) == true)
{
myptr->black = false;
}
else
{
myptr->black = true;
}
}
bool sameType(mynode* myptr)
{
int counter = 0;
unsigned long int val;
mynode* father;
father = myptr->parent;
val = myptr->val;
if ( val == (father->lchild)->val)
{
counter++;
}
else
{
counter--;
}
val = father->val;
father = father->parent;
if ( val == (father->lchild)->val)
{
counter++;
}
else
{
counter--;
}
if( (counter == 2) || (counter == -2))
{
return true;
}
else
{
return false;
}
}
void repair (mynode* myptr)
{
rootRepair(myptr);
subtreeRepair(myptr);
return ;
}
void rootRepair (mynode* myptr)
{
if(isRoot(myptr))
{
myptr->black = true;
}
return ;
}
bool isRoot(mynode* myptr)
{
if ((myptr->parent) == NULL)
{
return true;
}
return false;
}
void subtreeRepair (mynode* myptr)
{
mynode* father = (mynode* )malloc(sizeof(mynode));
mynode* uncle = (mynode* )malloc(sizeof(mynode));
father = getFather(myptr);
uncle = getUncle(myptr);
if( (isRed(father)) || (isRoot(myptr) == false))
{
if( isRed(uncle))
{
colorFlip(myptr);
}
else
{
myRotate(myptr);
}
}
return ;
}
void colorFlip( mynode* myptr)
{
mynode* cfather = (mynode* )malloc(sizeof(mynode));
mynode* cuncle = (mynode* )malloc(sizeof(mynode));
mynode* cgrandpa = (mynode* )malloc(sizeof(mynode));
cfather = getFather(myptr);
cuncle = getUncle(myptr);
cgrandpa = getFather(cfather);
changeBlack(cfather);
changeBlack(cuncle);
changeRed(cgrandpa);
repair(cgrandpa);
return ;
}
void changeBlack(mynode* myptr)
{
myptr->black = true;
return ;
}
void changeRed(mynode* myptr)
{
myptr->black = false;
return ;
}
void myRotate(mynode* myptr)
{
if( sameType(myptr))
{
rotate(myptr);
}
else
{
doubleRotate(myptr);
}
return ;
}
void rotate(mynode* myptr)
{
mynode* rfather = (mynode* )malloc(sizeof(mynode));
mynode* runcle = (mynode* )malloc(sizeof(mynode));
mynode* rgrandpa = (mynode* )malloc(sizeof(mynode));
mynode* current = (mynode* )malloc(sizeof(mynode));
rfather = getFather(myptr);
runcle = getUncle(myptr);
rgrandpa = getFather(rfather);
changeColor(rfather);
changeColor(rgrandpa);
if((rfather->lchild)->val == ((myptr)->val) )
{
current = rfather->rchild;
}
else
{
current = rfather->lchild;
}
if((rgrandpa->lchild)->val == (runcle->val))
{
rgrandpa->rchild = current;
}
else
{
rgrandpa->lchild = current;
}
rfather->parent = rgrandpa->parent;
current = rgrandpa->parent;
if((current->lchild)->val == (rgrandpa)->val)
{
current->lchild = rfather;
}
else
{
current->rchild = rfather;
}
if((rfather->rchild)->val == (myptr)->val)
{
rfather->lchild = rgrandpa;
}
else
{
rfather->rchild = rgrandpa;
}
free(current);
return ;
}
void doubleRotate (mynode* myptr)
{
mynode* current = (mynode* )malloc(sizeof(mynode));
current = myptr->parent;
smallRotate(myptr);
rotate(current);
return ;
}
void smallRotate(mynode* myptr)
{
mynode* srfather = (mynode* )malloc(sizeof(mynode));
mynode* srgrandpa = (mynode* )malloc(sizeof(mynode));
mynode* srcurrent = (mynode* )malloc(sizeof(mynode));
int flag = 0;
srfather = getFather(myptr);
srgrandpa = getFather(srfather);
if( (srgrandpa->lchild)->val == (srfather->val))
{
srgrandpa->lchild = myptr;
}
else
{
srgrandpa->rchild = myptr;
flag = 1;
}
if(flag = 0)
{
srcurrent = myptr->lchild;
myptr->lchild = srfather;
srfather->rchild = srcurrent;
}
else
{
srcurrent = myptr->rchild;
myptr->rchild = srfather;
srfather->lchild = srcurrent;
}
return ;
}
程序直到"插入"功能运行没有问题。当我向数据结构添加修复函数(在插入函数中(和所有实现红黑树属性的函数时，发生了分段错误。
R&B校正(或平衡，如果你喜欢(算法主要来自这里
重要编辑：
使用调试器使我获得了Uncle函数，我认为那里发生了分段错误。我的预测是，它不能返回"叔叔"，因为它靠近根部。因此，当数组开头的信息存储在树中或平衡达到树的高度时，我遇到了问题......有什么想法吗？
您有以下行：
if(flag = 0)
最有可能的是：
if(flag == 0)
请注意，=是分配，==是比较。
另请注意，如果您启用了编译器警告(例如gcc -Wall ...(，这将在编译时被标记，以及有关可疑代码的其他有用警告：
rbtree.c:64:31: warning: format specifies type 'unsigned long' but the argument has type 'unsigned long long' [-Wformat]
printf("lines = %lu", lines);
~~~ ^~~~~
%llu
rbtree.c:436:17: warning: using the result of an assignment as a condition without parentheses [-Wparentheses]
if(flag = 0)
~~~~~^~~
rbtree.c:436:17: note: place parentheses around the assignment to silence this warning
if(flag = 0)
^
( )
rbtree.c:436:17: note: use '==' to turn this assignment into an equality comparison
if(flag = 0)
^
==
2 warnings generated.