二元搜索树只包含根，删除会导致打印无限多个地址

Question

此代码：

1. 插入

删除是问题所在，我已经自己完成了这段代码（所以这可能不是常规方法）。我将删除分为三个部分进行检查：

1. 如果目标节点有两个子节点

这个程序的每个部分都运行相关的、正确的输出（只是一切！），除非root是唯一剩下的节点并且我们正在尝试删除root。

它进入nonode函数（在函数中有root的特殊情况），甚至打印“您已删除内存中唯一的节点”。一旦选择任何选项again.however显示错误，就会给出所有选项。例如，在尝试打印各种遍历时，它会在检查遍历时打印无限的地址列表，最终. exe文件会停止，而不是打印“内存中没有二叉树”。

#include <stdio.h>
#include <stdlib.h>

struct bt
{
    struct bt *left;
    int data;
    struct bt *right;
};

struct bt *root=NULL,**sp=NULL;

void insertion(struct bt**,int);
void prtraversal(struct bt**);
void intraversal(struct bt**);
void potraversal(struct bt**);
void search(struct bt**,int);
void del(struct bt **n,int key); 
void nonode(struct bt **n); 
void onenode(struct bt **n);
void bothnode(struct bt **n);

main()
{
    int ch,key;
    printf("******\n\n The program automatically avoids inclusion of repeat numbers\n\n**********");
    while(1)
    {
        printf("\nenter your choice\n1 for insertion\n2 for search\n3 for Various Traversal\n4 for deletion\n5 for exit\n");
        scanf("%d",&ch);
        switch(ch)
        {
        case 1:
            printf("Enter your Key for insertion\n");
            scanf("%d",&key);
            insertion(&root,key);
            break;
        case 2:
            if(root!=NULL)
            {
                printf("Enter your Key for search\n");
                scanf("%d",&key);
                search(&root,key);
            }
            else
            {
                printf("\n NO BINARY TREE IN MEMORY\n");
            }
            break;
        case 3:
            if(root!=NULL)
            {
                printf("\n\nPREORDER TRAVERSAL:");
                prtraversal(&root);
                printf("\n\nINORDER TRAVERSAL:");
                intraversal(&root);
                printf("\n\nPOSTORDER TRAVERSAL:");
                potraversal(&root);
            }
            else
            {
                printf("\n NO BINARY TREE IN MEMORY\n");
            }
            break;
        case 4:
            if(root!=NULL)
            {
                printf("Enter your Key for Delete\n");
                scanf("%d",&key);
                del(&root,key);
            }
            else
            {
                printf("\n NO BINARY TREE IN MEMORY\n");
            }
            break;
        case 5:
            exit(1);
        default:
            printf("\n Wrong Choice\n");
        }
        sp=NULL;
    }
}

void del(struct bt **n,int key)
{
    if((*n)!=NULL)
    {
        if(key<(*n)->data)
            del(&((*n)->left),key);
        else if(key>(*n)->data)
            del(&((*n)->right),key);
        else if(key==(*n)->data)
        {
            printf("\nELEMENT FOUND\n");
            printf("\n DELETION UNDERWAY\n");
            sp=n;
            if(((*n)->right)!=NULL && ((*n)->left)!=NULL)
            {
                bothnode(&((*n)->left));
            }
            else if(((*n)->right)!=NULL && ((*n)->left)==NULL)
            {
                onenode(&((*n)->right));
            }
            else if(((*n)->left)!=NULL && ((*n)->right)==NULL)
            {
                onenode(&((*n)->left));
            }
            else if(((*n)->left)==NULL && ((*n)->right)==NULL)
            {
                nonode(&root);
            }
        }
    }
    else
    {
        printf("\nELEMENT NOT FOUND\n");
    }
}

void nonode(struct bt **n) //deletes the target node without any child,root address is provided to struct bt **n
{
    struct bt **parent=n;//stores address of node just before target node,will be updated in this function
    if(sp!=&root)//target node address stored in sp from a previous function
    {
        while((*n)->data!=(*sp)->data)//to find address of node just before target node and store it in struct bt **parent
        {
            parent=n;//frequent parent update as struct bt **n traverses tree
            if(((*sp)->data)<((*n)->data))
                n=&((*n)->left);
            if(((*sp)->data)>((*n)->data))
                n=&((*n)->right);
        }
        if((*parent)->right==(*sp))//checks if parent's right contains address of target node
        {
            (*parent)->right=NULL;
            free(*sp);
        }
        else if((*parent)->left==(*n))//else checks if parent's left contains address of target node
        {
            (*parent)->left=NULL;
            free(*n);
        }
    }
    else if(sp==&root)//if the root node has to be deleted,no child on either side,only one node in tree
    {
        free(*sp);
        printf("\nYOU DELETED THE ONLY NODE IN MEMORY\n");
    }
}

Answer 1

删除后忘记将根设置为NULL：

else if(sp==&root)
{
    free(*sp);
    *sp = NULL;                                         // <-- add this line
    printf("\nYOU DELETED THE ONLY NODE IN MEMORY\n");
}

Answer 2

从树中删除单个节点时，您没有将root设置为NULL。因为根是全局的，所以可以在del（struct bt**n，int key）中将其设置为NULL。当您到达此支票时：

else if(((*n)->left)==NULL && ((*n)->right)==NULL)

您已经知道要删除根节点，因为之前的条件已经用尽了所有其他可能性。所以您可以简单地释放根节点并将其设置为NULL

else
{
    free(*n);
    *n = NULL;
}

另一方面，您的删除算法非常复杂。要删除BST中的节点，只需将其键替换为左子树中最大节点的键或右子树中最小节点的键，然后删除替换的节点。

Answer 3

您发布的代码在删除叶节点的函数中有缺陷。假设叶节点是根节点。可能是，但这不是重点。

这是：

else if(((*n)->left)==NULL && ((*n)->right)==NULL)
{
    nonode(&root);
}

应该简单地这样做：

else nonode(n);

原因：您已经检查了前两个条件，您已经知道此指针没有chidden。实际上，甚至不需要nonode（）。您可以简单地执行以下操作：

else
{
    free(*n);
    *n = NULL;
}

按地址传入指针的关键在于您有权修改它们。那么就这么做吧。正在删除此节点，您有引用它的指针的地址。删除节点并将该指针设置为NULL。如果该指针恰好是根，那么就这样吧；当函数完成时，它将为NULL。