0

これが私がこれまでに持っているコードです。ほとんどの部分でロジックがダウンしていると思いますが、2 人の子を持つ部分で立ち往生しています..それを機能させるためにどのような種類のアルゴリズムを使用する必要があるかを理解しました (コメントで注釈を付けました)関数の一番下にあります)、開始方法がわかりません...誰かが私を正しい方向に向けることができますか??

私がこれまでに持っているものは次のとおりです。

void BinaryTree::remove(int data){
// Is the data valid?
if(data < 0){
    cerr << data << " is not valid.  Must be a positive integer value."  << endl;
}
else{
    // Find the node
    BinNode* loc = root;
    BinNode* parent = nullptr;
    bool found = false;
    while(!found && loc != nullptr){
        if(data > loc->data){
            parent = loc;
            loc = loc->right;
        }
        else if(data < loc->data){
            parent = loc;
            loc = loc->left;
        }
        else found = true;
    }

    // If there is a parent, take care of the pointer
    if(parent != nullptr){
        if(loc->data < parent->data)
            parent->left = nullptr;
        else if(loc->data > parent->data)
            parent->right = nullptr;
    }
    // If there are children, save pointers to them
    BinNode* leftChild = nullptr;
    BinNode* rightChild = nullptr;  
    if(loc->left != nullptr)
        leftChild = loc->left;
    if(loc->right != nullptr)
        rightChild = loc->right;

    // So now pointers to the children have been saved (if they exist) and
    // parent pointers have been taken care of (if they exist) the node can be deleted
    // If no children exist simply just delete the node and return
    delete loc;
    // If one child exists
    if(leftChild != nullptr || rightChild != nullptr){  
        if(leftChild != nullptr){
            if(leftChild->data < parent->data)
                parent->left = leftChild;
            else if(leftChild->data > parent->data)
                parent->right = leftChild;
        }
        else if(rightChild != nullptr){
            if(rightChild->data < parent->data)
                parent->left = rightChild;
            else if(rightChild->data > parent->data)
                parent->right = rightChild;
        }       
    }

    // Both children exist...this sucks.
    else if(leftChild != nullptr && rightChild != nullptr){
        // Find a minimum in the right subtree
        BinNode * min = root;
        BinNode * minParent = nullptr;
        while(min->left != nullptr){
            minParent = min;
            min = min->left;
        }
        // Replace value of the node to be removed with the found minimum
        loc = new BinNode(min->data);

        // Delete the remaining duplicate node
        if(minParent != nullptr)
            minParent->left = nullptr;
        delete min;
    }
}
}
4

1 に答える 1

0

ここにいます。これはうまくいくようです。これを最適化する方法や修正が必要な問題について何か提案がある場合は、ご意見をお寄せください。ありがとう！

void BinaryTree::remove(int data){
// Is the data valid?
if(data < 0){
    cerr << data << " is not valid.  Must be a positive integer value."  << endl;
}
else{
    // Find the node
    BinNode* loc = root;
    BinNode* parent = nullptr;
    bool found = false;
    while(!found && loc != nullptr){
        if(data > loc->data){
            parent = loc;
            loc = loc->right;
        }
        else if(data < loc->data){
            parent = loc;
            loc = loc->left;
        }
        else found = true;

    // If there are children, save pointers to them
    BinNode* leftChild = nullptr;
    BinNode* rightChild = nullptr;  
    if(loc->left != nullptr)
        leftChild = loc->left;
    if(loc->right != nullptr)
        rightChild = loc->right;

    // So now pointers to the children have been saved (if they exist) and
    // parent pointers have been taken care of (if they exist) the node can be deleted
    // If no children exist simply just delete the node and return

    // Check if two children exist
    if(leftChild != nullptr && rightChild != nullptr){

        // Find a minimum in the right subtree
        BinNode * min = loc->right;
        BinNode * minParent = loc;
        while(min->left != nullptr){
            minParent = min;
            min = min->left;
        }
        // Replace value of the node to be removed with the found minimum
        loc->data = min->data;

        // Delete the duplicate
        if(minParent != loc)
            minParent->left = nullptr;
        else minParent->right = nullptr;
        delete min;
    }

    // If one child exists
    // Need to handle if it is the root here
    // change root pointer to remaining child
    else if(leftChild != nullptr || rightChild != nullptr){ 
        // If there is a parent, take care of the pointer
        if(parent != nullptr){
            if(loc->data < parent->data)
                parent->left = nullptr;
            else if(loc->data > parent->data)
                parent->right = nullptr;

        // Now loc can be deleted
        delete loc;
        if(leftChild != nullptr){
            if(parent != nullptr){
                if(leftChild->data < parent->data)
                    parent->left = leftChild;
                else if(leftChild->data > parent->data)
                    parent->right = leftChild;
            }
            // If it is the root
            else{
                root = leftChild;
            }
        }
        else if(rightChild != nullptr){
            if(parent != nullptr){
                if(rightChild->data < parent->data)
                    parent->left = rightChild;
                else if(rightChild->data > parent->data)
                parent->right = rightChild;
            }
            // If it is the root
            else{
                root = rightChild;
            }
        }       
    }

    // If there are no children
    else if (leftChild == nullptr && rightChild == nullptr){
        // If there is a parent, take care of the pointer
        if(parent != nullptr){
            if(loc->data < parent->data)
                parent->left = nullptr;
            else if(loc->data > parent->data)
                parent->right = nullptr;
        }
        // If it is the root
        else 
            root = nullptr;
        delete loc;
    }
}
于 2013-11-11T19:42:24.357 に答える