修改递归中的调用指针

因此，我正在研究BST，构建删除工具。修改递归中的调用指针

我的代码序列似乎工作正确 - 保存没有更新父或根，并设置将它发送到删除的节点的地址为NULL的指针。

我传递了一个指针指向我的Erase和RemoveNode函数中的一个指针，以便直接影响实际导致递归调用的左，右或根数据成员。在遍历代码时，它将removeN函数中的* N设置为NULL，但这不会在调用对象的数据中反映出来。我在使用指针指针方法时不正确吗？如果是这样，是否有一种方法可以递归地删除并能够修改先前的节点，如果链接被销毁？

节点结构：

struct tNode 
{ 
    tNode(int n) 
    { 
     data = n; 
     left = NULL; 
     right = NULL; 
    } 

    //Works, cleans all linked objects. 
    //Must remember to null links when removing wanted nodes 
    ~tNode(void) 
    { 
     //cout << "Deleting " << data << endl; 
     delete left; 
     delete right; 
    } 

    // Data members 
    int data; 
    tNode* left; 
    tNode* right; 
};

橡皮擦功能递归在树：

void BinSearchTree::Erase(int n, tNode** N) 
    { 
     tNode* node = *N; 
     if (root) 
     { 
      if (node->data > n) // post order, to avoid moving many times over 
      { 
       if (node->left) 
       { 
        Erase(n, &node->left); 
       } 
      } 
      else 
      { 
       if (node->right) 
       { 
        Erase(n, &node->right); 
       } 
      } 

      if (node->data == n) 
      { 
       RemoveNode(&node); 
      } 
     } 
    }

而且的removeNode函数来处理实际删除：

void BinSearchTree::RemoveNode(tNode** N) 
{ 
    tNode* node = *N; 
    if (!node->left && !node->right) // is leaf 
    { 
     delete node; // remove node 
     size--; 
     *N = NULL; // null pointer for above node/structure 
    } 
    else if (!node->left) // right child 
    { 
     tNode* temp = node->right; // to strip out copied node when finished 
     node->data = node->right->data; // copy right node into current node 
     node->right = node->right->right; 
     node->left = node->right->left; 

     temp->right = NULL; // NULL because node destructor is recursive 
     temp->left = NULL; // ^^ 
     delete temp; 
     size--; 
    } 
    else if (!node->right) // left child 
    { 
     tNode* temp = node->left; // to strip out copied node when finished 
     node->data = node->left->data; // copy left node into current node 
     node->right = node->left->right; 
     node->left = node->left->left; 

     temp->right = NULL; // NULL because node destructor is recursive 
     temp->left = NULL; // ^^ 
     delete temp; 
     size--; 
    } 
    else // 2 children 
    { 
     tNode* temp = node->right; // find ideal child -> left-most right child 
     tNode* parent = NULL; // keep track of owner of ideal child 
     while (temp->left) 
     { 
      parent = temp; 
      temp = temp->left; 
     } 

     node->data = temp->data; // copy ideal child to root 
     if (parent) 
     { 
      parent->left = temp->right; // case that left-most child has right child of it's own 
     } 
     RemoveNode(&temp); 
     size--; 
    } 
}

来源

2011-11-07 DivinusVox

您是否有真正的问题？ –

@KerrekSB对不起，我一定领先于自己。感谢您指出。 – DivinusVox

我想我看到它。当您从Erase()拨打电话RemoveNode()时，您将其传递给值&node。改为传入N。

发生了什么事情：行tNode* node = *N;在堆栈上创建一个局部变量。 A 的副本的*N。尽管该变量具有与* N（最初）相同的值，但它存储在内存中的不同位置：node位于堆栈中，而*N位于堆中的某处。

所以，既然你传递&node到RemoveNode()，node就是得到改变。不是*N - 它在别的地方。但是，如果你通过，你正在改变你想要的。

希望有帮助！ PS：如果还不清楚，请告诉我！写关于双指针可能只是比使用它们更难...

来源

2011-11-07 01:49:21

本地范围的好处，使这个错误在几个地方（没有想到它我猜）。谢谢！ – DivinusVox

保存自己使用双指针的麻烦，只使用指针的引用。它们具有与普通指针相同的语义，但分配它们实际上会更改传递的指针。

void BinSearchTree::Erase(int item, tNode*& node);

此外，使用表现力的名称和保存单个字母的变量名for循环。

来源

2011-11-07 02:21:50 Xeo

修改递归中的调用指针

回答

相关问题