0

私のコードはアルゴリズムを考えるとうまくいくように見えますが、私は C++ が初めてで、insert を複数回呼び出すと、これらのポインターが自分自身を上書きしているようです。たとえば、insert を値 1、3、5 で呼び出すと、ルートは (予想どおり) 1 になりますが、3 は上書きされ、ルートの右の子の値は 3 ではなく 5 になります。

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内のローカル オブジェクトであり、ポインターは破棄されたオブジェクトを指します。問題を解決するための素朴な可能性は、次の方法でヒープに割り当てることです。insertrootnewNodenew

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 に答える