我编写了一个函数来删除其值等于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/