0

这段代码：

  1. 刀片
  2. 搜索
  3. 打印各种遍历
  4. 删除

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

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

该程序的每个部分都运行正确，正确的输出（只是所有内容！），除非根是唯一剩下的节点并且我们试图删除根。

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

4 回答 4

1

root从树中删除单个节点时，您没有设置为 NULL。由于 root 是全局的，因此您可以在内部将其设置为 NULL del(struct bt **n,int key)。当您到达此检查时：

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

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

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

附带说明，您的删除算法非常复杂。要删除 BST 中的节点，只需将其键替换为左子树中最大节点或右子树中最小节点的键，然后删除替换的节点即可。

于 2013-10-20T23:04:02.807 回答
1

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

这个：

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

应该这样做：

else nonode(n);

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

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

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

于 2013-10-20T23:14:32.203 回答
0

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

else if(sp==&root)
{
    free(*sp);
    *sp = NULL;                                         // <-- add this line
    printf("\nYOU DELETED THE ONLY NODE IN MEMORY\n");
}
于 2013-10-20T22:59:31.517 回答
0

这是释放二叉树的一种非常令人困惑的方法。指向指针的指针，用于删除节点的不同函数。我相信这样的东西应该可以找到，你可以把你的印刷品放在想要的地方

void wrap_del(strut tree ** t)
{
    del(*t);
    *t = NULL;
}

void del(struct tree * t)
{
    if (*t == NULL)
        return; //called on a null ptr

    del(t->left);
    del(t->right);
    free(t);
}

这个递归调用会一直到树的底部，在空节点上调用时返回，删除左右返回后会释放自己

于 2013-10-20T23:04:11.443 回答