我正在尝试用 C++ 实现一个二叉搜索树，我在其中实现了一个
删除节点()
使用双指针的方法，但使用 free() 和 delete 等预定义方法不会删除我的节点。请帮帮我好吗？
我一直在 youtube 上搜索视频或文章以及极客对极客的搜索，但它们都是使用单个指针实现的，因此在这种情况下我无法找到引用，尤其是在它附近。我试图解决上周无法成功实现的问题，有些节点正在被删除有些不是我无法找到这背后的原因，还请告诉我为什么我的代码没有按预期工作
#include <bits/stdc++.h>
using namespace std;
typedef struct node {
struct node *left = NULL;
int key;
struct node *right = NULL;
} node;
void addNode(node **r, int k)
{
if (*r == NULL)
{
node *q = (struct node*)malloc(sizeof(struct node));
q->key = k;
*r = q;
(*r)->left = NULL;
(*r)->right = NULL;
return;
}
node *q = (struct node*)malloc(sizeof(struct node));
if (k > ((*r)->key))
{
addNode(&((*r)->right), k);
}
else if (k < ((*r)->key))
{
addNode(&((*r)->left), k);
}
}
void searchNode(node **r, int k)
{
if (*r == NULL)
{
cout << "\n NOT FOUND \n";
return;
}
if ((*r)->key == k)
{
cout << "\n FOUND \n";
return;
}
else if (k > ((*r)->key))
{
searchNode(&((*r)->right), k);
}
else if (k < ((*r)->key))
{
searchNode(&((*r)->left), k);
}
}
void del(node **r, int k)
{
if (*r == NULL)
return;
if ((*r)->key == k)
{
if ((*r)->left == NULL && (*r)->right == NULL)
{
(*r) = NULL;
(*r) = NULL;
free(r);
return;
}
if ((*r)->left == NULL)
{
node* q = (struct node*)malloc(sizeof(struct node));
q = (*r)->right;
(*r)->key = q->key;
(*r)->left = q->left;
(*r)->right = q->right;
free(q);
return;
}
if ((*r)->right == NULL)
{
node* q = (struct node*)malloc(sizeof(struct node));
q = (*r)->left;
(*r)->key = q->key;
(*r)->left = q->left;
(*r)->right = q->right;
free(q);
return;
}
node* q = (struct node*)malloc(sizeof(struct node));
q = (*r)->right;
while (q->left != NULL)
q = q->left;
(*r)->key = q->key;
if (((*r)->right) == q)
{
(*r)->right = NULL;
}
else
{
del(&q, q->key);
}
}
else if (k > ((*r)->key))
{
del(&((*r)->right), k);
}
else if (k < ((*r)->key))
{
del(&((*r)->left), k);
}
}
void print(node* r)
{
if (r == NULL)
return;
print(r->left);
cout << r->key << " ";
print(r->right);
}
int main()
{
node* root = NULL;
addNode(&root, 11);
addNode(&root, 5);
addNode(&root, 4);
addNode(&root, 8);
addNode(&root, 6);
addNode(&root, 10);
addNode(&root, 9);
addNode(&root, 19);
addNode(&root, 12);
addNode(&root, 30);
addNode(&root, 20);
addNode(&root, 50);
addNode(&root, 31);
addNode(&root, 37);
addNode(&root, 35);
addNode(&root, 38);
print(root);
del(&root, 9);
cout << "\n 9 should be missing" << endl;
print(root);
searchNode(&root, 9);
del(&root, 30);
cout << "\n 30 should be missing" << endl;
print(root);
searchNode(&root, 30);
del(&root, 8);
cout << "\n 8 should be missing" << endl;
print(root);
searchNode(&root, 8);
del(&root, 10);
cout << "\n 10 should be missing" << endl;
print(root);
searchNode(&root, 10);
del(&root, 11);
cout << "\n 11 should be missing" << endl;
print(root);
searchNode(&root, 11);
return 0;
}
当我删除根节点时，输出应该是
4 5 6 12 19 20 31 35 37 38 50
而它是 4 5 6 12 12 19 20 31 35 37 38 50
最佳答案
你的代码太复杂了。存在多个问题:
addNode()分配一个新节点，但在递归时不使用它。searchNode()有一个冗余比较，可能应该采用一个简单的常量node指针。del应在将r指向的节点设置为NULL之前释放该节点。del不应该分配新节点，而只是修改当前节点。
这是一个经过简化和更正的版本:
#include <iostream>
using namespace std;
typedef struct node {
struct node *left = NULL;
int key;
struct node *right = NULL;
} node;
void addNode(node **r, int k) {
if (*r == NULL) {
node *q = (struct node *)malloc(sizeof(struct node));
q->key = k;
q->left = NULL;
q->right = NULL;
*r = q;
return;
}
if (k > (*r)->key) {
addNode(&(*r)->right, k);
} else
if (k < (*r)->key) {
addNode(&(*r)->left, k);
}
}
void searchNode(const node *p, int k) {
if (p == NULL) {
cout << k << " NOT FOUND\n";
return;
}
if (p->key == k) {
cout << k << " FOUND\n";
return;
}
if (k > p->key) {
searchNode(p->right, k);
} else {
searchNode(p->left, k);
}
}
void del(node **r, int k) {
node *p = *r;
if (p == NULL)
return;
if (k > p->key) {
del(&p->right, k);
} else
if (k < p->key) {
del(&p->left, k);
} else {
if (p->left == NULL) {
(*r) = p->right;
free(p);
return;
}
if (p->right == NULL) {
(*r) = p->left;
free(p);
return;
}
node *q = p->right;
while (q->left)
q = q->left;
p->key = q->key;
del(&p->right, p->key);
}
}
void printrec(const node *r) {
if (r != NULL) {
printrec(r->left);
cout << r->key << " ";
printrec(r->right);
}
}
void print(const node *r) {
printrec(r);
cout << endl;
}
int main() {
node *root = NULL;
addNode(&root, 11);
addNode(&root, 5);
addNode(&root, 4);
addNode(&root, 8);
addNode(&root, 6);
addNode(&root, 10);
addNode(&root, 9);
addNode(&root, 19);
addNode(&root, 12);
addNode(&root, 30);
addNode(&root, 20);
addNode(&root, 50);
addNode(&root, 31);
addNode(&root, 37);
addNode(&root, 35);
addNode(&root, 38);
print(root);
cout << "deleting 9" << endl;
del(&root, 9);
print(root);
searchNode(root, 9);
cout << "deleting 30" << endl;
del(&root, 30);
print(root);
searchNode(root, 30);
cout << "deleting 8" << endl;
del(&root, 8);
print(root);
searchNode(root, 8);
cout << "deleting 10" << endl;
del(&root, 10);
print(root);
searchNode(root, 10);
cout << "deleting 11" << endl;
del(&root, 11);
print(root);
searchNode(root, 11);
return 0;
}
输出:
4 5 6 8 9 10 11 12 19 20 30 31 35 37 38 50 deleting 9 4 5 6 8 10 11 12 19 20 30 31 35 37 38 50 9 NOT FOUND deleting 30 4 5 6 8 10 11 12 19 20 31 35 37 38 50 30 NOT FOUND deleting 8 4 5 6 10 11 12 19 20 31 35 37 38 50 8 NOT FOUND deleting 10 4 5 6 11 12 19 20 31 35 37 38 50 10 NOT FOUND deleting 11 4 5 6 12 19 20 31 35 37 38 50 11 NOT FOUND
关于c++ - 为什么我的节点在使用 free() 或 delete 时没有被删除，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/57259637/