c++ - 删除节点方法实际上并未删除二叉搜索树中的节点。C++
问题描述
当我调用我的 removeNode 方法时,它显示在本地删除节点并在调试器中将其设置为 null,但是当我在调试器中查看树时,应该删除的节点仍然存在。当我打印树时,应该被删除的节点会打印出来,但是分配给结构的 int 和字符串却指向打印出乱码。
我试过使用 free() 和 delete,但实际上都没有删除节点。
bool BinTree::addNode(int id, string info, DataNode *add_node) {
auto *temp_node = new DataNode;
temp_node->data.id = id;
temp_node->data.information = info;
temp_node->left = temp_node->right = nullptr;
if(id < add_node->data.id){
if(!add_node->left){
add_node->left = new DataNode;
add_node->left = temp_node;
count++;
}else{
addNode(id, info, add_node->left);
}
}else{
if(!add_node->right){
add_node->right = new DataNode;
add_node->right = temp_node;
count++;
}else{
addNode(id, info, add_node->right);
}
}
}
bool BinTree::removeNode(int id, DataNode *temp_root) {
cout << "Searching to remove: " << id << endl;
if(temp_root == nullptr){
return false;
}
else if(id < temp_root->data.id) {
removeNode(id, (temp_root->left);
}
else if(id > temp_root->data.id){
removeNode(id, temp_root->right);
}
else{
//no child
if(temp_root->left == nullptr && temp_root->right == nullptr){
cout << "Deleting no children node" << endl; //DEBUG ONLY
cout << "Temp root address:" << temp_root << endl; //DEBUG ONLY
delete temp_root;
temp_root->data.id = 123456; //DEBUG ONLY
cout << "no child deleted" << endl; //DEBUG ONLY
count--;
}
//one child
else if(temp_root->left == nullptr){
cout << "Deleting 1 child node" << endl;
DataNode *temp_node = temp_root;
temp_root = temp_root->right;
delete temp_node;
temp_node = nullptr;
count--;
}
else if(temp_root->right == nullptr){
cout << "Deleting 1 child node" << endl;
DataNode *temp_node = temp_root;
temp_root = temp_root->left;
free(temp_node);
temp_node = nullptr;
count--;
}
//two children
else if(temp_root->left && temp_root->right){
cout << "Deleting 2 child node" << endl;
DataNode temp_node = minValueNode(temp_root->right);
temp_root->data = temp_node.data;
removeNode(temp_node.data.id, temp_root->right);
}
return true;
}
}
DataNode BinTree::minValueNode(DataNode *temp_node) {
while(temp_node->left){
temp_node = temp_node->left;
}
return *temp_node;
}
我在方法中有一些调试输出,以验证它正在删除的 temp_root 地址是否与树对于给定节点的地址相同,这是正确的。它只是没有从实际的树中删除它。
解决方案
就我个人而言,我会编写删除以返回链接的新值。
void removeNode(int id) {
root = removeNode(id, root);
}
Node* removeNode(int id, Node* n) {
if (n == nullptr) {
return nullptr;
}
if (id < n->id) {
n->left = removeNode(id, n->left);
return n;
}
else if (n->id < id) {
n->right = removeNode(id, n->right);
return n;
}
else if (n->left == null) {
Node* result = n->right;
delete n;
return result;
}
else if (n->right == null) {
Node* result = n->left;
delete n;
return result;
}
else {
int v = findSmallestValue(n->right);
n->right = removeNode(v, n->right);
n->id = v;
return n;
}
}
推荐阅读
- java - 使用 Java HttpClient 强制立即不安全的 HTTP2 连接
- curl - unix curl 复选标记的含义
- objective-c - 中断时未显示 Xcode10 变量
- vue.js - vuex的表单处理
- c# - 无法连接到本地 MS CRM 365?
- xampp - 使用 Xampp 在 Windows 上安装 Mifos 后 Tomcat 未启动。Mifos 不工作,怎么了?
- sql - 将两个排序结果与间歇性的一对二合并
- c++ - 树莓派 OpenVG C/C++
- sql - SQL 查询查找:A 的 X% 归因于 B 的 Y%
- php - 如何从会话 Laravel 中删除价值?