バイナリ検索ツリーのremoveNodeの実装

Question

私は、プログラム内のバイナリ検索ツリーのテキストブックで説明されている削除アルゴリズムを実装しようとしていますが、その意味を推測し、それが指定した機能と自分自身の機能を実装しました。私が抱えている問題は、012-の0-1-2子ケースを扱う機能です。それは、この機能で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 
} 

ための次の擬似コードを指定する本では

、はどのようにC Pの子作るのですか？あなたがツリーの親が誰であるかを理解するために何ができますか？通常、それを追跡するために後続ノードが必要ですが、書籍の最終草案のために、私はそれが意味するものではないと考えています。

「最終草案」

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

私は私がそうであるように、あなたが同様の問題を抱えていると思います。子供が1人しかいないときに何をしているのかは、ポインタをそれぞれ右または左に分岐するように設定することです。しかし、そのサブツリーからノードを置き換える必要があります。これは、左のサブツリー内の最小ノードを検索し、削除したいノードをこの最小ノードで置き換えることによって実行できます。次に、ノードの重複を防ぐために挿入したノードを削除する必要があります。それはとにかく理論です。私はそれを自分で正しく実装することはできませんでした。

編集：リンクをもう一度削除しました。私は答えで何かを尋ねることは悪いエチケットとみなされていました。私に恥/ o。