0

我目前正在执行一项任务，我要实现一个简单版本的红黑树。我目前在 Xcode 中工作，它目前给了我一个错误GDB: Program received signal: EXC_BAD_ACCESS......我假设这是内存泄漏......但我似乎无法找到任何原因来解释为什么会发生这种情况。调试器向我展示了问题出在我的RedBlackTree::treeInsert(char *data)函数中......特别是 if 循环体中的 if 语句if (strcmp(data, x->data) < 0)。

调试器显示，this = 0x7fff5fc01052它data = 0x100001a61正在存储一个字符（字母 A）。然而，它表明，x = 0x4810c48348ec8948但它的所有属性（父、左、右、数据）都是空的。

因此，我尝试的下一件事是确保像Nil在node()构造函数中一样初始化这些变量。但这给了我错误：'Nil' was not declared in this scope......所以我目前将它们注释掉。不知道这里发生了什么..？任何帮助将不胜感激。

class node
{
public:
char         *data;         // Data containing one character
node         *parent;       // pointer to this node's parent
node         *left;          // pointer to this node's left child
node         *right;          // pointer to this node's right child
bool         isRed;         // bool value to specify color of node
node();
};

node::node(){
this->data = new char[1];
isRed = true;
//this->parent = Nil;
//this->left = Nil;
//this->right = Nil;
}

红黑树类和方法

class RedBlackTree {
public: 
/*constructor*/
RedBlackTree();

node* getRoot(){
    return this->Root;
}

/*RB-INSERT*/
void rbInsert(char *data);
node treeInsert(char *data);
void rbInsertFixup(node *z);

/*ROTATE*/
void leftRotate(node *z);
void rightRotate(node *z);

/*INORDER TRAVERSAL*/
void inOrderPrint(node *root);



private:
node    *Root;    /*root*/
node    *Nil;    /*leaf*/

};



RedBlackTree::RedBlackTree() 
{
this->Nil = new node();
this->Root = Nil;
}

void RedBlackTree::rbInsert(char *data){
node z = treeInsert(data);
rbInsertFixup(&z);  

} // end rbInsert()

node RedBlackTree::treeInsert(char *data){

node *x;
node *y;
node *z;

y = Nil;
x = Root;
while (x!= Nil) {
    y = x;
    if (strcmp(data, x->data) < 0) {
        x = x->left;
    } else {
        x = x->right;
    }
}
z = new node(); // create a new node
z->data = data;
z->parent = y;
z->isRed = true; // set  new node as red 
z->left = Nil;
z->right = Nil;

if (y == Nil) {
    Root = z;
} else {
    if (strcmp(data, y->data)<= 0) {
        y->left = z;
    } else {
        y->right = z;
    }

}
return *z;
}

这是我的主要功能

int main(){


RedBlackTree *RBT;
node* root = RBT->getRoot();
RBT->rbInsert((char *)"A");
RBT->inOrderPrint(root);
return 0;

}
4

2 回答 2

1

您到处都有缓冲区溢出！包含一个字符的字符串实际上是两个字符，因为它也有一个特殊的终止字符。您为数据的单个字符分配内存，但使用字符串会使这些缓冲区溢出。

于 2013-06-17T01:26:06.843 回答
0

一般来说，您只需在 RBT 中有一个指向树的指针，而无需对其进行初始化，然后调用未定义的行为区域。

（并且代码还有很多其他可疑点）

于 2013-06-17T01:24:53.660 回答