c - 在二叉搜索树中删除

Question

我做了一个二叉树。它插入元素，删除它们并打印输出。代码中的删除功能有些问题。删除某些元素后出现段错误。请帮我找到错误删除代码。

#include<stdio.h>
#include<stdlib.h>
struct Node
{
    int info;
    struct Node *right;
    struct Node *left;
    struct Node *parent;
};
typedef struct Node node;

node *createnode(node *temp,int number)
{
    temp=(node*)malloc(sizeof(node));
    temp->info=number;
    temp->right=NULL;
    temp->left=NULL;
    temp->parent=NULL;
return temp;
}

node *insert(node *head,int number)
{
    node *temp;
    temp=createnode(temp,number);
    node *traverse=head;
    if(head==NULL)
    {
        head=temp;
        temp->parent=NULL;
        return head;
    }
    else
    {
        while(traverse!=NULL)
        {
            if(number < traverse->info)
            {
                if(traverse->left==NULL)
                {
                    traverse->left=temp;
                    temp->parent=traverse;
                    break;
                }
                traverse=traverse->left;
            }
            else if(number>traverse->info)
            {
                if(traverse->right==NULL)
                {
                    traverse->right=temp;
                    temp->parent=traverse;
                    break;
                }
                traverse=traverse->right;
            }
            else
                break;
        }
    }
return head;
}

node *find(node *head,int number)
{
    node *traverse=head;
    if(traverse==NULL)
        return NULL;
    else
    {
        while(traverse!=NULL)
        {
            if(number<traverse->info)
            {
                if(traverse->left==NULL)
                {
                    printf("Number not found\n");
                    return NULL;
                }
                traverse=traverse->left;
            }
            else if(number>traverse->info)
            {
                if(traverse->right==NULL)
                {
                    printf("Number not found\n");
                    return NULL;
                }
                traverse=traverse->right;
            }
            else
                break;
        }
    }
return traverse;
}
int find_children(node *temp)
{
    int count=0;
    if(temp->left!=NULL)
        count+=1;
    if(temp->right!=NULL)
        count+=1;
return count;
}
node *delete(node *head,int number)
{
    int children;
    node *temp=head;
    temp=find(temp,number);
    if(temp==NULL)
        return head;
    else
    {
        children=find_children(temp);
        if(children==0)
        {
            if(temp->parent->left==temp)
            {
                temp->parent->left=NULL;
            }
            else if(temp->parent->right==temp)
            {
                temp->parent->right=NULL;
            }
        }
        if(children==1)
        {
            if(temp->parent==NULL)
            {
                if(temp->right!=NULL)
                {
                    temp->right->parent=NULL;
                    head=temp->right;
                }
                else if(temp->left!=NULL)
                {
                    temp->left->parent=NULL;
                    head=temp->left;
                }
            }
            else
            {
                if(temp->parent->left==temp)
                {
                    if(temp->right!=NULL)
                    {
                        temp->right->parent=temp->parent;
                        temp->parent->left=temp->right;
                    }
                    else if(temp->left!=NULL)
                    {
                        temp->left->parent=temp->parent;
                        temp->parent->left=temp->left;
                    }
                }
                if(temp->parent->right==temp)
                {
                    if(temp->right!=NULL)
                    {
                        temp->right->parent=temp->parent;
                        temp->parent->right=temp->right;
                    }
                    else if(temp->left!=NULL)
                    {
                        temp->left->parent=temp->parent;
                        temp->parent->right=temp->left;
                    }
                }
            }
        }
        if(children==2)
        {
            node *temp1;
            node *temp2;
            temp1=temp;
            temp2=temp->right;
            while(temp2->left!=NULL)
            {
                temp1=temp2;
                temp2=temp2->left;
            }
            temp->info=temp2->info;
            if(temp1->left==temp2)
            {
                    temp1->left=temp2->left;
            }
            else
            {
                temp1->right=temp2->right;
            }
        }

    }
return head;
}
void printing(node *head)
{
    if(head==NULL)
        return ;
    printing(head->left);
       printf("%d ",head->info);
    printing(head->right);
}

int main()
{
    node *head;
    int number,choice;
    printf("Choose one of the option\n");
    while(1)
    {
        printf("\n1.Enter a element\n2.Delete an element\n3.print tree\n4Reverse the tree\n5.Sort\n6.Exit\n");
        scanf("%d",&choice);
        switch(choice)
        {
            case 1:
            {
                scanf("%d",&number);
                head=insert(head,number);
                break;
            }
            case 2:
            {
                scanf("%d",&number);
                head=delete(head,number);
                break;
            }
            case 3:
            {
                printing(head);
                break;
            }
           /* case 4:
            {
                reverse();
            }
            case 5:
            {
                sort();
                break;
            }*/
            case 6:
            {
                exit(0);
                break;
            }
        }
    }
    return 0;
}

Answer 1

删除 BST(二叉搜索树)中的元素:

要删除二叉搜索树中的一个元素，我们首先需要查看它的子节点，并根据它来决定删除节点的方法。删除节点基本上有三种奇怪的情况。

该节点没有子节点(换句话说，它是叶节点)。该节点有左 child 或右 child 。该节点有两个 child 。

public object DeleteNode (object data)
{
     TNode tempDelete = this.GetNode(data);
     if (tempDelete != null)
     {
        if ((tempDelete.Left == null ) &&(tempDelete.Right == null)) //Its a Leaf node
        {
           tempParent = tempDelete.Parent;
           if(tempDelete == tempParent.Left) //Justremove by making it null
               tempParent.Left = null;
           else
               tempParent.Right = null;
        }
        else if ((tempDelete.Left == null ) ||(tempDelete.Right == null)) //It has either Left orRight child
        {
           tempChild = tempDelete.Left == null? tempDelete.Right : tempDelete.Left; //Get the child
           tempParent = tempDelete.Parent; //Getthe parent
           if(tempDelete == tempParent.Left) //Makeparent points to it's child so it will automatically deleted like Linked list
               tempParent.Left = tempChild;
           else
               tempParent.Right = tempChild;
          }
          else if ((tempDelete.Left != null) ||(tempDelete.Right != null)) //It has both Left andRight child
         {
            TNodepredNode = this.GetNode(this.TreePredecessor_Ite(data));  //Findit's predecessor
            if(predNode.Left != null) // Predecessor node canhave no or left child. Do below two steps only if it has left child
            {
                 tempChild = predNode.Left;
                 predNode.Parent.Right = tempChild; //Assignleft child of predecessor to it's Parent's right.
             }
             tempDelete.Data = predNode.Data; //Replace the value of predecessor nodeto the value of to be deleted node
                   //predNode = null; //Remove predecessornode as it's no longer required.
         }

         return data + " Deleted";
     }
     else
          return "Please enter the valid tree element!";
}