只是显示二叉树的节点是什么样子的。我不确定出了什么问题,但我有一种感觉,这与功能是私有的有关。如何比较私有数据,以便查看我正在寻找的值是否在该节点内?
class binarytree
{
private:
class node
{
public:
int data;
node * left;
node * right;
node (int x)
{
data = x;
left=NULL;
right=NULL;
}
};
node * root;
这就是我插入节点的方式
void insert(int x, node * &r)
{
if(r==NULL)
{
r= new node(x);
}
else
{
if(x < r->data)
{
//insert left
insert(x, r->left);
}
else
{
//insert right
insert(x, r->right);
}
}
}
这是我尝试将 x 与 r->data 进行比较时给我带来麻烦的代码部分,程序崩溃并给我错误消息"访问冲突读取位置0x00000000"
void remove(int x, node * &r)
{
if(x == r->data)
{
if(r->right == NULL && r->left == NULL)
{
r = NULL;
}
else if(r->right == NULL && r->left != NULL)
{
r = r->left;
}
else if(r->right != NULL && r->left == NULL)
{
r = r->right;
}
else
{
node * temp;
temp =r;
r = r->left;
while(r->right != NULL)
{
r = r->right;
}
r->right = temp->right;
delete temp;
}
}
else if ( x < r->data)
{
remove(x, r->left);
}
else if (x > r->data)
{
remove(x , r->left);
}
}
这是功能公开的地方。然后我调用私有函数,以便我可以操作私有树。
public:
binarytree()
{
root = NULL;
}
~binarytree()
{
//tooo: write this
}
//return true if empty, false if not
bool empty()
{}
void insert(int x)
{
insert(x, root);
}
void remove(int x)
{
remove(x,root);
}
};
编辑:这是程序的另一个功能,它可以工作,但可能导致r指向NULL。
int extractMin(node * &r)
{
if(r->left == NULL)
{
if(r->right == NULL)
{
return r->data;
}
else
{
int x = r->data;
r = r->right;
return x;
}
}
else
{
return extractMin(r->left);
}
}
这是检查 r 是否为 NULL 的新功能
void remove(int x, node * &r)
{
if(r == NULL)
{
cout<<"why am I null?"<<endl;
}
else
{
if(x == r->data)
{
if(r->right == NULL && r->left == NULL)
{
r = NULL;
}
else if(r->right == NULL && r->left != NULL)
{
r = r->left;
}
else if(r->right != NULL && r->left == NULL)
{
r = r->right;
}
else
{
node * temp;
temp =r;
r = r->left;
while(r->right != NULL)
{
r = r->right;
}
r->right = temp->right;
delete temp;
}
}
else if ( x < r->data)
{
remove(x, r->left);
}
else if (x > r->data)
{
remove(x , r->left);
}
}
}
尝试访问内部成员之前,您应该始终检查NULL
:
void remove(int x, node * &r)
{
if(r != NULL)
{
// Your code
}
}
您调用以r
作为NULL
删除,然后尝试检查r.Left
. 那么这里有访问冲突
我还必须问,这是否对你有用? 具体来说insert
不会这样工作。尝试
void insert(int x, node * &r)
{
if(r==NULL)
{
r= new node(x);
}
else
{
if(x < r->data)
{
if(r->left != NULL)
{
//insert left
insert(x, r->left);
}
else
{
r->left = new node(x);
}
}
else
{
if(r->right != NULL)
{
//insert right
insert(x, r->right);
}
else
{
r->left = new node(x);
}
}
}
}
r
以某种方式为空。您需要检查传入的r
是否NULL
,或者检查root
是否为非 null,并且仅在子项存在时才对子项调用remove
。
好吧,错误说,当你尝试取消引用它时,r 指向 NULL。所以你必须确保当你将记忆分配给r时,它不会返回NULL。
binarytree()
{
root = NULL;
}
void remove(int x)
{
remove(x,root);
}
在您的情况下,您正在尝试取消引用 NULL(如错误所述)当您在调用插入之前调用删除时,这发生在您的代码中。您只需在删除开始时检查 r 是否指向 NULL。或者更好的是,确保当 r 为 NULL 时不会在 r 中解析。
您正在将x
与root
进行比较。当您的树为空时,root == nullptr
.您应该先检查是否r == nullptr
,如下所示:
bool remove(int x, node * &r) {
if(!r) {
return false; // Indicate whether removal succeeded
}
//... etc.
}