c - 仅包含根的二叉搜索树，删除会导致打印无限个地址

Question

这段代码:

1. 插入
2. 搜索
3. 打印各种遍历
4. 删除

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

1. 如果目标节点有两个子节点
2. 如果目标节点有一个子节点
3. 如果目标节点没有子节点

这个程序的每个部分都运行正确，正确的输出(只是一切!)除非根节点是唯一剩下的节点并且我们正在尝试删除根节点。

它进入nonode函数(在函数中有root的特殊情况)甚至打印“你已经删除了内存中唯一的节点”。再次给出所有选项。但是选择之后的任何选项都显示错误。在尝试打印各种遍历，例如它在检查遍历时打印无限地址列表，最终 .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

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

这个:

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

应该简单地这样做:

else nonode(n);

原因:你已经检查了前两个条件，你已经知道这个指针没有 child 。实际上，甚至不需要 nonode()。你可以简单地这样做:

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

按地址传递指针的全部意义在于您有权修改它们。所以就这样做吧。该节点正在被删除，您有引用它的指针的地址。删除节点并将that 指针设置为NULL。如果该指针恰好是 root，那就这样吧；函数完成后将为 NULL。