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

我觉得你有类似的问题，因为我做的。当只有一个孩子时，你正在做什么，只是将指针分别设置为向右或向左分支。但是您需要用该子树中的节点替换该节点。这可以通过搜索左侧子树中的最小节点并用此最小节点替换要删除的节点来完成。然后，您需要删除刚插入的节点以防止节点重复。无论如何，这是理论。我没有设法正确地执行它自己。

编辑：我再次删除链接。我看到在答案中提出问题被认为是不礼貌的礼仪。在我身上感到羞耻。