删除不在二叉搜索树中工作。 [英] Deletion not working in binary search tree.

问题描述

 / * 12 
 / \ 
 9 15 
 / \ \ 
 4 11 21 
包含数据的节点15未在上述二进制搜索树中删除。* / 
 
 #include< stdio.h> 
 #include< conio.h> 
 #include< stdlib.h> 
 
 typedef struct Node 
 {
 int info; 
 struct Node * left; 
 struct Node * right; 
}节点; 
 
 void deleteItem（node *，node *，int）; 
 void deleteNode（node * root，node * parent）
 {
 node * temp; 
 if（root-> left == NULL）/ *只剩下孩子* / 
 {
 if（parent-> left == root）
 parent->左=根 - >权; 
 else 
 parent-> right == root-> right; 
 free（root）; 
} 
 else if（root-> right == NULL）/ *只有右子* / 
 {
 if（parent-> left == root）
 parent-> left = root-> left; 
 else 
 parent-> right = root-> left; 
 free（root）; 
} 
 else / *两个孩子都存在* / 
 {
 temp = root-> left; 
 while（temp-> right！= NULL）
 temp = temp-> right; 
 root-> info = temp-> info; 
 deleteItem（root-> left，root，temp-> info）; 
 free（root）; 
} 
} 
 
 void insert（node ** root，int item）
 {
 node * parent，* cur; 
 parent = NULL; 
 cur = * root; 
 while（cur！= NULL）
 {
 parent = cur; 
 if（item< = cur-> info）
 cur = cur-> left; 
 else 
 cur = cur-> right; 
} 
 if（* root == NULL）
 {
 * root =（node *）malloc（sizeof（node））; 
（* root） - > info = item; 
（* root） - > left = NULL; 
（* root） - > right = NULL; 
} 
 else 
 {
 node * newNode =（node *）malloc（sizeof（node））; 
 newNode-> info = item; 
 newNode-> left = NULL; 
 newNode-> right = NULL; 
 if（item< parent-> info）
 parent-> left = newNode; 
 else 
 parent-> right = newNode; 
} 
} 
 
 void deleteItem（node * root，node * parent，int item）
 {
 if（root == NULL）
返回; 
 node * cur = root; 
 if（item< cur-> info）
 deleteItem（cur-> left，cur，item）; 
 else if（item> cur-> info）
 deleteItem（cur-> right，cur，item）; 
 else 
 deleteNode（cur，parent）; 
} 
 
 int main（）
 {
 int a [] = {12,9,4,11,15,21}; 
 int i; 
 node * root，* ptr; 
 root = NULL; 
 for（i = 0; i< 6; i ++）
 insert（& root，a [i]）; 
 ptr = root; 
 while（ptr！= NULL）
 {
 printf（％d \ n，ptr-> info）; 
 ptr = ptr-> right; 
} 
 deleteItem（root，NULL，15）; 
 ptr = root; 
 printf（\ n \ nn \ n \ n）; 
 while（ptr！= NULL）
 {
 printf（％d \ n，ptr-> info）; 
 ptr = ptr-> right; 
} 
 getch（）; 
} 

解决方案

看看你的代码：

  void  deleteNode（node * root，node * parent）
 {
 node * temp; 
  if （root-> left == NULL） / *  只剩下孩子* /  
 {
 如果（parent-> left == root）
 parent-> left = root-> right; 
  else  
 parent-> right == root-> right; 
 free（root）; 
} 
  else   if （root-> right == NULL）< span class =code-comment> / *  只有正确的孩子* /  
 {
  if （parent-> left == root）
 parent-> left = root-> left; 
  else  
 parent-> right = root-> left; 
 free（root）; 
} 
 其他  / *  两个孩子都存在* /  
 {
 temp = root-> left; 
  while （temp-> right！= NULL）
 temp = temp-> right; 
 root-> info = temp-> info; 
 deleteItem（root-> left，root，temp-> info）; 
 free（root）; 
} 
} 

你 真的 想要==吗？ ：笑：

 parent-> right == root-> right; 
 

我们都做到了！ ：O

让我们一步一步。我会告诉你我能立刻看到的问题。先修复它们，然后看看你是否可以完全解决问题。



两个 deleteNode 和 deleteItem 有一些错误的参数集。您的函数 deleteItem 有一个冗余参数 item 。您根本不使用它，只将它传递给同一函数的递归调用，实际上忽略了该值。去掉它。现在，参数 root 听起来像是多余的，但也许它只是以误导的方式命名。如果您有节点父节点，则实际上不需要root。如果你使用树，你必须记住根。但是你仍然需要两个参数：一个要删除的节点及其父节点，因为删除后你需要设置 left 或吧 member为null。



现在，删除很复杂，因为你没有父节点存储的指针在每个节点中。这是冗余，但它会显着提高性能。现在，您尝试递归执行节点删除（这是一个非常明智的决定）。您可以应用一些删除功能。树是二进制的，因此您获得节点的左右子树，并且对于每个非空子树，递归地调用相同的函数。在每个终端节点上停止递归 - 那些同时具有 left == 0 和 right == null ;然后，只有这样你才能删除节点，否则会丢失子节点。但是，您需要再次从父级开始扫描子树，删除在上一组删除后成为终端的节点，直到只有要删除的节点为止。所以考虑将父成员添加到结构中并利用它，特别是在删除期间。



< DD> -SA

/*           12
                  /\
                 9  15
                / \   \
               4  11   21
The node with data 15 is not being deleted in the above binary serach tree.*/

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

typedef struct Node 
{
    int info;
    struct Node* left;
    struct Node* right;
}node;

void deleteItem(node*,node*,int);
void deleteNode(node *root,node* parent)
{
    node *temp;
    if(root->left==NULL)/*Only left child*/
    {
        if(parent->left==root)
        parent->left=root->right;
        else
        parent->right==root->right;
        free(root);
    }
    else if(root->right==NULL)/*Only right child*/
    {
        if(parent->left==root)
        parent->left=root->left;
        else
        parent->right=root->left;
        free(root);
    }
    else/*Both children exist*/
    {
        temp=root->left;
        while(temp->right!=NULL)
        temp=temp->right;
        root->info=temp->info;
        deleteItem(root->left,root,temp->info);
        free(root);
    }
}

void insert(node **root,int item)
{
    node *parent,*cur;
    parent=NULL;
    cur=*root;
    while(cur!=NULL)
    {
        parent=cur;
        if(item<=cur->info)
        cur=cur->left;
        else
        cur=cur->right;
    }
    if(*root==NULL)
    {
        *root=(node*)malloc(sizeof(node));
        (*root)->info=item;
        (*root)->left=NULL;
        (*root)->right=NULL;
    }
    else
    {
        node *newNode=(node*)malloc(sizeof(node));
        newNode->info=item;
        newNode->left=NULL;
        newNode->right=NULL;
        if(item<parent->info)
        parent->left=newNode;
        else
        parent->right=newNode;
    }
}

void deleteItem(node *root,node *parent,int item)
{
    if(root==NULL)
    return;
    node *cur=root;
    if(item<cur->info)
    deleteItem(cur->left,cur,item);
    else if(item>cur->info)
    deleteItem(cur->right,cur,item);
    else
    deleteNode(cur,parent);
}
    
int main()
{
    int a[]={12,9,4,11,15,21};
    int i;
    node *root,*ptr;
    root=NULL;
    for(i=0;i<6;i++)
    insert(&root,a[i]);
    ptr=root;
    while(ptr!=NULL)
    {
        printf("%d\n",ptr->info);
        ptr=ptr->right;
    }
    deleteItem(root,NULL,15);
    ptr=root;
    printf("\n\n\n\n");
    while(ptr!=NULL)
    {
        printf("%d\n",ptr->info);
        ptr=ptr->right;
    }
    getch();
}

解决方案

Look at your code:

void deleteNode(node *root,node* parent)
{
    node *temp;
    if(root->left==NULL)/*Only left child*/
    {
        if(parent->left==root)
        parent->left=root->right;
        else
        parent->right==root->right;
        free(root);
    }
    else if(root->right==NULL)/*Only right child*/
    {
        if(parent->left==root)
        parent->left=root->left;
        else
        parent->right=root->left;
        free(root);
    }
    else/*Both children exist*/
    {
        temp=root->left;
        while(temp->right!=NULL)
        temp=temp->right;
        root->info=temp->info;
        deleteItem(root->left,root,temp->info);
        free(root);
    }
}

Do you really want "==" in there? :laugh:

parent->right==root->right;

We've all done it! :O

Let's do one step at a time. I'll tell you just the problems I can see immediately. Fix them first, and then see if you can solve the problem completely.

Both deleteNode and deleteItem have some wrong set of parameters. Your function deleteItem has a redundant parameter item. You don't really use it at all, you only pass it to recursive calls to the same function, and the value is actually ignored. Remove it. Now, the parameter root sounds like redundant, but perhaps it is only named in a misleading way. If you have a node parent, you don't really need a root. If you work with the tree, you have to remember the root anyway. But you still need two parameters: a node to be deleted and its parent node, because after deletion you will need to set left or right member to null after the corresponding sun-tree is deleted.

Now, deletion is complicated because you don't have a pointer the the parent node stored in each node. This is the redundancy, but it will improve performance dramatically. Right now, you try to perform the node deletion recursively (which is quite a decision). You can apply some deletion function. The tree is binary, so you get left and right sub-tree of the node, and for each of the non-null sub-tree call the same function recursively. Recursion is stopped on each of the terminal nodes — those which have both left == 0 and right == null; then and only then you can delete the node, otherwise you would have children nodes lost. But then, you will need to scan the sub-tree starting from the parent again, to delete the nodes which became terminal after previous set of deletion, until you have only the node to be deleted. So think about adding the parent member to the structure and leveraging it, in particular, during deletion.

—SA

这篇关于删除不在二叉搜索树中工作。的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！