修改遞歸中的調用指針

因此，我正在研究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

修改遞歸中的調用指針

回答

相關問題