我编写了一个函数来删除其值等于BST中给定键的节点,我尝试了一个简单的示例[5,3,6],并删除键=3。但是当我运行此代码时,不会删除3。此代码的输出:
根= 5左= 3右= 6
为什么?谢谢!

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// delete key in the tree
TreeNode* deleteNode(TreeNode* root, int key) {
    TreeNode* cur = root;
    // find the node to delete
    while(cur) {
        if(cur->val == key) break;
        if(cur->val > key) cur = cur->left;
        else cur = cur->right;
    }
    if(!cur) return root;
    // I want to delete the node of val 3 here
    // here cur == root->left, I though when I do cur = 0, root->left will also be set to 0
    if(!cur->left && !cur->right) {
        assert(cur == root->left);
        delete cur;
        cur = 0;
    }
    if(root) cout << "root = " << root->val << endl;
    // but root->left is not nullptr when I ran this, and 3 still exists
    if(root->left) cout << "left = " << root->left->val << endl;
    if(root->right) cout << "right = " << root->right->val << endl;
    return root;
}

int main() {
    TreeNode* root = new TreeNode(5);
    TreeNode* l = new TreeNode(3);
    TreeNode* r = new TreeNode(6);
    root->left = l;
    root->right = r;
    deleteNode(root, 3);
}

最佳答案

问题是您有一个悬空的指针。您需要将“父”节点中的left设置为NULL。同样,如果删除右侧的节点,则需要将父节点的right指针设置为NULL

关于c++ - 为什么在这种情况下我尝试删除的Treenode没有删除?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/41339389/

10-11 22:05
查看更多