removeNode爲二叉搜索樹的實現

Question

我想實現在一個程序中的二叉搜索樹的教科書中討論的移除算法，但該書是缺乏一些功能的細節描述，所以我已經猜測它們的意義並實現它指定的功能和我自己的功能。我遇到的問題是關於處理0-1-2兒童病例的removeNode函數。

在它指定爲removeNode

removeNode(N: BinaryNode) 
{ 
if(N is a leaf) 
    Remove N from the tree 
else if (N has only one child C) 
{ 
    if(N was a left child of its parent P) 
     Make C the left child of P 
    else 
     Make C the right child of P 
} 
else //Node has two children 
{ 
    //Find S, the node that contains N's inorder successor 
    //Copy the item from node S into node N 
    //Remove S from the tree by using the previous 
    //technique for a leaf or a node with one child 
} 

下面的僞代碼在這個函數的書，你如何讓P c^的孩子？給定一個沒有任何東西指向父節點的節點，你可以做什麼來弄清楚樹的父親是誰？通常你需要一個尾隨節點來跟蹤這個結果，但是由於這些書的最終草稿'我懷疑這不是他們所暗示的。

「最終稿」

removeNode(nodePtr: BinaryNodePointer): BinaryNodePointer 
{ 
if(N is a leaf) 
{ 
    //Remove leaf from the tree 
    delete nodePtr 
    nodePtr = nullPtr 
    return nodePtr 
} 
    else if (N has only one child C) 
    { 
     if(N was a left child of its parent P) 
      nodeToConnectPtr = nodePtr->getleftChildPtr() //<---I assume this means nodePtr->left 
     else 
      nodeToConnectPtr = nodePtr->getRightChildPtr() //<--nodePtr->right? 
     delete nodePtr 
     nodePtr = nullptr 
     return nodeToConnectPtr 
    } 
    else //Node has two children 
    { 
     //Find the inorder succesor of the entry in N: it is in the left subtree rooted 
     //at N's Child 
     tempPtr = removeLeftMosstNode(nodePtr->getRightChild(), newNodeValue) 
     nodePtr->setRightChildPtr(tempPtr) //<--nodePtr->right = tempPtr? 
     nodePtr->setItem(newNodeValue) // nodePtr->vendorData = newNodeValue? 
     return nodePtr 
    } 

這是我想出了基於關閉上述設計的實現。我知道有些部分是錯的，但我不確定我還能做些什麼來修復它們。任何人都可以提出修復兒童案件和我可能錯過的任何其他問題嗎？

我實現

aBst::treeNode * aBst::removeNode(aBst::treeNode * nodePtr) 
    { 
     //This functions deletes a node and then returns the pointer to the child to take the place of deleted child 
     aVendor * tempVendorPtr; 
     treeNode * nodeToConnectPtr, *tempPtr; 

     //The node passed is the node that needs to be removed 
     if (nodePtr->right == NULL && nodePtr->left == NULL) //----No Child---- 
     { 
      delete nodePtr; 
      nodePtr = NULL; 
      return nodePtr; 
     } 
     else if ((nodePtr->right != NULL) != (nodePtr->left != NULL))//----One Child---- 
     { 
      if (nodePtr->left != NULL)//left child 
      { 
       nodeToConnectPtr = nodePtr->left; //Wrong 
      } 
      else if (nodePtr->right != NULL) //right child 
      { 
       nodeToConnectPtr = nodePtr->right; //Wrong 
      } 

      delete nodePtr; 
      nodePtr = NULL; 
      return nodeToConnectPtr; 
     } 
     else //-----Two Child----- 
     { 
      //find minimum value of right subtree, stores the pointer to the vendorData it carries through the parameter and calls removeNode 
      tempPtr = removeLeftMostNode(nodePtr->right, tempVendorPtr); 
      nodePtr->vendorData = tempVendorPtr; 
      nodePtr->right = tempPtr; 
      return nodePtr; 
     } 

    } 

所有功能

int aBst::countKids(aBst::treeNode * subTreePtr) 
{ 
    if (subTreePtr == NULL) //Empty Tree 
    { 
     return -1; 
    } 
    else if (subTreePtr->right == NULL && subTreePtr->left == NULL) //----No Child---- 
    { 
     return 0; 
    } 
    else if ((subTreePtr->right != NULL) != (subTreePtr->left != NULL))//----One Child---- 
    { 
     return 1; 
    } 
    else if ((subTreePtr->right != NULL) && (subTreePtr->left != NULL))//----Two Child---- 
    { 
     return 2; 
    } 
    //Something unexpected occurred   
    return -1; 
} 

bool aBst::remove(char nameOfVendor[]) 
{ 
    bool failControl = false; 

    removeValue(root, nameOfVendor, failControl); 

    return failControl; 
} 

aBst::treeNode * aBst::removeValue(aBst::treeNode * subTreePtr, char nameOfVendor[], bool& success) 
{ 
    //Note: the subTreePtr should be root in initial call 
    treeNode * tmpPtr; 
    char name[MAX_CHAR_LENGTH]; 

    //Make sure passed success bit is false 
    success = false; 

    subTreePtr->vendorData->getName(name); 

    if (subTreePtr == NULL) //Empty Tree 
    { 
     success = false; 
     return NULL; 
    } 
    else if (strcmp(name, nameOfVendor) == 0) //Evaluates to true if there is a match 
    { 
     subTreePtr = removeNode(subTreePtr); 
     success = true; 
     return subTreePtr; 
    } 
    else if (strcmp(name, nameOfVendor) > 0) // Go left 
    { 
     //Protects algorithm from bad data crash 
     if (subTreePtr->left == NULL) 
     { 
      return subTreePtr; 
     } 

     tmpPtr = removeValue(subTreePtr->left, nameOfVendor, success); 
     subTreePtr->left = tmpPtr; 
     return subTreePtr; 
    } 
    else // Go Right 
    { 
     //Protects algorithm from bad data crash 
     if (subTreePtr->right == NULL) 
     { 
      return subTreePtr; 
     } 

     tmpPtr = removeValue(subTreePtr->right, nameOfVendor, success); 
     subTreePtr->right = tmpPtr; 
     return subTreePtr; 
    } 

    //For loop was broken and function returns false 
    return subTreePtr; 
} 



aBst::treeNode * aBst::removeNode(aBst::treeNode * nodePtr) 
{ 
    aVendor * tempVendorPtr; 
    treeNode * nodeToConnectPtr, *tempPtr; 

    //The node passed is the node that needs to be removed 
    if (nodePtr->right == NULL && nodePtr->left == NULL) //----No Child---- 
    { 
     delete nodePtr; 
     nodePtr = NULL; 
     return nodePtr; 
    } 
    else if ((nodePtr->right != NULL) != (nodePtr->left != NULL))//----One Child---- 
    { 
     if (nodePtr->left != NULL)//left child 
     { 
      nodeToConnectPtr = nodePtr->left; 
     } 
     else if (nodePtr->right != NULL) //right child 
     { 
      nodeToConnectPtr = nodePtr->right; 
     } 

     delete nodePtr; 
     cout << "called\n"; 
     nodePtr = NULL; 
     return nodeToConnectPtr; 
    } 
    else //-----Two Child----- 
    { 
     //find minimum value of right subtree, stores the pointer to the vendorData it carries through the parameter and calls removeNode 
     tempPtr = removeLeftMostNode(nodePtr->right, tempVendorPtr); 
     nodePtr->vendorData = tempVendorPtr; 
     nodePtr->right = tempPtr; 
     cout << "\nleaving Two Child\n"; 
     return nodePtr; 
    } 

} 

aBst::treeNode * aBst::removeLeftMostNode(aBst::treeNode * nodePtr, aVendor*& vendorDataRef) 
{ 
    if (nodePtr->left == NULL) 
    { 
     //Target acquired 
     vendorDataRef = nodePtr->vendorData; 
     return removeNode(nodePtr); 
    } 
    else 
     return removeLeftMostNode(nodePtr->left, vendorDataRef); 
} 

Answer 1

我覺得你有類似的問題，因爲我做的。當只有一個孩子時，你正在做什麼，只是將指針分別設置爲向右或向左分支。但是您需要用該子樹中的節點替換該節點。這可以通過搜索左側子樹中的最小節點並用此最小節點替換要刪除的節點來完成。然後，您需要刪除剛插入的節點以防止節點重複。無論如何，這是理論。我沒有設法正確地執行它自己。

編輯：我再次刪除鏈接。我看到在答案中提出問題被認爲是不禮貌的禮儀。在我身上感到羞恥。