0

考虑到算法，我的代码似乎应该可以工作，但我是 C++ 新手，当我多次调用 insert 时，这些指针似乎会覆盖自己。例如，如果我用值 1、3、5 调用 insert，那么根将为 1（如预期的那样），但 3 将被覆盖，并且根的右子节点将具有值 5 而不是 3。

virtual bool insert(const Data& item) {
if(root == NULL){
  BSTNode<Data> newNode (item);
  root = &newNode;
  isize++;
  return true;
}
BSTNode<Data>* nextNode = root;
BSTNode<Data>* prevNode = NULL;
bool isLeft;
while(nextNode!=NULL) {
  if (item < nextNode->data) {
    prevNode = nextNode;
    nextNode = nextNode->left;
    //std::cout << prevNode->data;
    isLeft = true;
  }
  else {
    prevNode = nextNode;
    nextNode = nextNode->right;
    //std::cout << prevNode->data;
    isLeft = false;
  }
}
BSTNode<Data> createNode (item);
createNode.parent = prevNode;
if (isLeft) prevNode->left = &createNode;
else prevNode->right = &createNode;
isize++;
return true;
}
4

2 回答 2

2

由于指向将要销毁的本地对象，您有一个无效的指针：

BSTNode<Data> newNode (item);
root = &newNode;

对象newNode是从该方法返回后的方法内的本地对象insert（超出范围），指针root将指向已销毁的对象。解决该问题的一种天真的可能性是newNode通过以下方式在堆中分配new：

root = new BSTNode<Data>(item);

但是您必须delete在某个地方使用它，并且对于createNode.

正如许多人所建议的那样，您应该使用诸如unique_ptr和之类的智能点shared_ptr。

于 2013-10-08T09:09:49.453 回答
0

假设这root是一个成员变量，您需要在堆上而不是在堆栈上分配它：

if(root == NULL){
  root = new BSTNode<Data>(item);
  isize++;
  return true;
}

否则，一旦超出if主体右括号的范围，节点就会被销毁。这同样适用于

if (isLeft) prevNode->left = new BSTNode<Data>(item);
else prevNode->right = new BSTNode<Data>(item);

不过，我还没有检查您的实际插入逻辑。您应该发布整个代码，这里的代码太少，无法检查。是二叉树吗？

编辑：根据 M M 的回答，如果在堆上创建节点，请不要忘记删除节点。

于 2013-10-08T09:09:17.607 回答