在二进制搜索树中执行删除操作c

我编写了一个程序，它将两个文件名作为参数f1和f2，这两个文件都带有数字。该程序应可调用如下：树f1 f2在二进制搜索树中执行删除操作c

f1拥有数百万的唯一编号，每行一个。每个数字应被读取并插入二进制搜索树。

这些插入后，程序应该从第二个文件读取数字。对于每个号，下面有许多工作要做：

搜索树
如果它存在的号码，询问用户从树中删除它现在

，我的代码对于插入和搜索，正在给出正确的结果，但是，在删除部分中，存在一些错误。

请帮我修改我的代码：

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

struct node { 
    int info; 
    struct node *left, *right; 
}; 

struct node *insert (struct node *root, int item) 
{ 
    struct node *temp, *temp1, *pre; 

    temp = (struct node *) malloc (sizeof (struct node)); 
    temp->info = item; 
    temp->left = temp->right = NULL; 

    if (root == NULL) 
     root = temp; 
    else { 
     temp1 = root; 
     while (temp1 != NULL) { 
      pre = temp1; 
      if (item < temp1->info) 
       temp1 = temp1->left; 
      else 
       temp1 = temp1->right; 

     } 
     if (item < pre->info) 
      pre->left = temp; 
     else 
      pre->right = temp; 
    } 

    return root; 
} 

struct node *create (struct node *root) 
{ 
    int num; 
    root = NULL; 
    FILE *fp1 = fopen ("myFile1.txt", "r"); 
    if (fp1 == NULL) { 
     printf ("cannot open this file"); 
     exit (0); 
    } 

    while (fscanf (fp1, "%d", &num) == 1) 
     root = insert (root, num); 

    return root; 
    fclose (fp1); /* (note: unreachable code) */ 
} 

struct node *min (struct node *ptr) 
{ 
    struct node *current = ptr; 

    while (current->left != NULL) 
     current = current->left; 

    return current; 
} 

struct node *delete (struct node *root, int n) 
{ 
    if (root == NULL) 
     return root; 

    if (n < root->info) 
     root->left = delete (root->left, n); 
    else if (n > root->info) 
     root->right = delete (root->right, n); 
    else { 
     if (root->left == NULL) { 
      struct node *p; 
      p = root->right; 
      free (root); 
      return p; 
     } 
     else if (root->right == NULL) { 
      struct node *p; 
      p = root->left; 
      free (root); 
      return p; 
     } 

     struct node *p; 
     p = min (root->right); 
     root->info = p->info; 
     root->right = delete (root->right, p->info); 
    } 

    return root; 
} 

void search (struct node *root) 
{ 
    int Y, X; 
    struct node *t; 
    t = root; 
    char ch = 'n'; 
    FILE *fp2 = fopen ("myFile2.txt", "r"); 
    if (fp2 == NULL) { 
     printf ("cannot open this file"); 
     exit (0); 
    } 
    X = 0; 
    while (fscanf (fp2, "%d", &Y) == 1) { 
     while (t != NULL && X == 0) { 
      if (Y == t->info) { 
       X = 1; 
       break; 
      } else if (Y < t->info) 
       t = t->left; 
      else 
       t = t->right; 
     } 

     if (X == 1) 
      printf (" %d is found %d\n", Y, X); 
     printf ("if you want to delete a number "); 
     scanf ("%c", &ch); 
     if (ch == 'y') { 
      root = delete (root, Y); 
      return root; 

     } 
     else 
      printf ("%dNot found %d\n", Y, X); 

    } 
    fclose (fp2); 
} 

void inorder (struct node *root) 
{ 
    if (root != NULL) { 
     inorder (root->left); 
     printf ("%d ", root->info); 
     inorder (root->right); 
    } 
} 

void main() 
{ 
    struct node *root = NULL; 
    struct node *ptr = NULL; 
    root = create (root); 
    inorder (root); 
    search (root); 
    inorder (root); 
}

来源

2016-02-02 Trisha

有些错误？什么是错误？ –

你的函数'delete'看起来很好。 – Rabbid76

你用调试器完成了吗？ – pm100

以下是更正代码：

#include<stdio.h> 
#include<stdlib.h> 
struct node 
{ 
int info; 
struct node *left, *right; 
}; 
struct node* insert(struct node* root, int item) 
{ 
struct node *temp,*temp1,*pre; 
temp = (struct node *)malloc(sizeof(struct node)); 
temp->info = item; 
temp->left = temp->right = NULL; 

if (root == NULL) 
{ 
    root=temp; 
} 
else 
{ 
    temp1=root; 
    while(temp1!=NULL) 
    { 
      pre=temp1; 
      if(item<temp1->info) 
      { 
       temp1=temp1->left; 
      } 
      else 
      { 
       temp1=temp1->right; 
      } 
    } 
    if(item<pre->info) 
    { 
     pre->left=temp; 
    } 
    else 
    { 
     pre->right=temp; 
    } 
} 
return root; 
} 

struct node *create(struct node *root) 
{ 
    int num; 
    root=NULL; 
    FILE *fp1=fopen("myFile1.txt","r"); 
    if (fp1 == NULL) 
    { 
     printf("cannot open this file"); 
     exit(0); 
    } 
    while(fscanf(fp1,"%d",&num)==1) 
     root=insert(root,num); 
    fclose(fp1); 
    return root; 
} 
struct node * min(struct node* ptr) 
{ 
     struct node* current = ptr; 
     while (current->left != NULL) 
     current = current->left; 

     return current; 
} 
struct node* delete(struct node* root,int n) 
{ 
    if(root==NULL) 
    { 
     return root; 
    } 
    if(n<root->info) 
    { 
     root->left=delete(root->left,n); 
    } 
    else if(n>root->info) 
    { 
     root->right=delete(root->right,n); 
    } 
    else 
    { 
      if(root->left==NULL) 
      { 
       struct node *p; 
       p=root->right; 
       free(root); 
       return p; 
      } 
      else 
      if(root->right==NULL) 
      { 
       struct node *p; 
       p=root->left; 
       free(root); 
       return p; 
      } 

      struct node *p; 
      p=min(root->right); 
      root->info=p->info; 
      root->right=delete(root->right,p->info); 
    } 
    return root; 
} 

void search(struct node *root) 
{ 
     int Y,X; 
     struct node *t; 
     char ch='n'; 
     FILE *fp2=fopen("myFile2.txt","r"); 
     if (fp2 == NULL) 
     { 
      printf("cannot open this file"); 
      exit(0); 
     } 
     while(fscanf(fp2,"%d",&Y)==1) 
     { 
      t = root; 
      X = 0; 
      while(t!=NULL && X==0) 
      { 
       if(Y==t->info) 
       { 
        X=1; 
        break; 
       } 
       else 
       { 
       if(Y<t->info) 
       { 
        t=t->left; 
       } 
       else 
       { 
        t=t->right; 
       } 
       } 
      } 

      if(X==1) 
      { 
       printf("\n%d is found\n",Y); 
       printf("\nDo you want to delete %d (y/n): ",Y); 
       scanf(" %c",&ch); 
       if(ch=='y') 
       { 
       root=delete(root,Y); 
       } 
      } 
      else 
      { 
       printf("\n%d Not found %d\n",Y,X); 
      } 
     } 
     fclose(fp2); 
} 

void inorder(struct node *root) 
{ 
      if (root != NULL) 
      { 
       inorder(root->left); 
       printf("%d ", root->info); 
       inorder(root->right); 
      } 
} 

void main() 
{ 
     struct node *root = NULL; 
     struct node *ptr = NULL; 
     root=create(root); 
     inorder(root); 
     printf("\n"); 
     search(root); 
     printf("\n"); 
     inorder(root); 
     printf("\n"); 
}

从格式化的微小变化

除此之外，以下是主要的变化：

永远记得把{}括号每个控制语句（如，同时，其他等），即使它有一个操作，因为后来，代码可以被添加到相同的控制语句和被遗忘的大括号将意味着控制语句不会被应用到该代码。对于例如你忘了括号中：
```
if(X==1) 
printf(" %d is found %d\n",Y,X); 
printf("if you want to delete a number "); 
scanf("%c",&ch); 
if(ch=='y') 
{ 
    root=delete(root,Y); 
    return root; 
} 
else 
    printf("%dNot found %d\n",Y,X); 
```
因为缺少大括号的现在，否则被应用到if(ch=='y')，而不是if(X==1)。其次，每当你将一个条件变量初始化为一个值并对其进行检查，在一个嵌套循环中，并且对于多个输入或者情况，该操作将被重复时，初始化也需要在循环。与t = root;和X = 0;在search函数中的情况一样，它们只是设置一次，并且当从文件读取下一个数字时，它们不会再次初始化。
你叫return root;，在void search(struct node *root)功能，这是返回类型void的，这意味着它返回什么：
```
if(ch=='y') 
{ 
root=delete(root,Y); 
return root; 
} 
```
而且，一个return呼叫的装置，该功能将停止进一步执行，然后在那里，并且在return呼叫下面的其余代码将不会被执行，这不是您想要的，如：
```
struct node *create(struct node *root) 
{ 
int num; 
... 
while(fscanf(fp1,"%d",&num)==1) 
    root=insert(root,num); 
return root; 
fclose(fp1); 
} 
```
这里，fclose(fp1);永远不会被调用。
而且，最后但不是最少的代码，更好地缩进可以帮助理解每个控制语句所在的范围，而不必跟踪每一个左括号{向关闭一个}。

来源

2016-02-02 17:10:20

-1

有几个额外的领域，你想避免长期为自己造成问题。你想避免硬编码文件名在你的代码的主体中，更不用埋藏在函数中的硬编码文件名。如果您需要对文件进行操作，例如create或search，请将FILE*参数（或文件名）传递给函数。这将使您的代码更易于维护和重用。对于create你会做类似的东西：

struct node *create (struct node *root, FILE *fp) 
{ 
    int num; 
    root = NULL; 

    while (fscanf (fp, "%d", &num) == 1) 
     root = insert (root, num); 

    return root; 
}

您当前search，你可以这样做：

void search (struct node *root, FILE *fp) 
{ 
    int v; 

    while (fscanf (fp, "%d", &v) == 1) { 

     struct node *t = root; 
     char ch = 'n'; 

     while (t != NULL) { 
      if (t->info == v) { 
       printf ("\n%d is found\n", v); 
       printf ("\nDo you want to delete %d (y/n): ", v); 
       scanf (" %c", &ch); 
       if (ch == 'y') { 
        root = delete (root, v); 
       } 
       break; 
      } 
      else { 
       if (v < t->info) 
        t = t->left; 
       else 
        t = t->right; 
      } 
     } 
     if (!t) 
      printf ("\n%d Not found\n", v); 
    } 
}

但为什么你传递一个FILE *指针search开始与？不应该search只搜索你的树并返回一个指向包含匹配值（如果存在）的节点的指针，否则返回NULL？这肯定会使search成为一种通用函数，可用于树的许多不同情况，而不是一次性检查第二个文件中的匹配值。

那么如何获得您的代码所需的文件名信息呢？就像您将所需的参数传递给您在代码中调用的每个函数一样，您也可以以相同方式将所需信息传递给main。 main需要在命令行上给出参数并将它们传递给您的程序。的main的一般形式是：

int main (int argc, char **argv)

（也将看到的等价形式int main (int argc, char *argv[])简单地反映了argv的另一种形式，而不显示阵列转换到指针当数组被传递的是自动发生的结果作为函数参数）

使用参数获取信息到main而不是硬编码。这并不意味着您不能在您的代码中提供默认文件名，如果未提供参数，将使用该文件名。您可以使用三元运算符，该运算符基本上是形式(condition) ? true_value : false_value形式的简写if-else。有了它，您可以从命令行获取文件名，同时仍然提供缺省值，以便在没有提供参数的情况下使用文件名（注意：第一个参数将始终用作fp1）。例如：

int main (int argc, char **argv) 
{ 
    FILE *fp1 = fopen (argc > 1 ? argv[1] : "myfile1.txt", "r"); 
    FILE *fp2 = fopen (argc > 2 ? argv[2] : "myfile2.txt", "r"); 
    if (fp1 == NULL) { 
     fprintf (stderr, "cannot open fp1\n"); 
     return 1; 
    } 
    if (fp2 == NULL) { 
     fprintf (stderr, "cannot open fp2\n"); 
     return 1; 
    }

然后，您可以通过FILE*指针（fp1，fp2）到需要他们的任何功能，例如：

root = create (root, fp1);

已经移除了create和search硬编码的文件名，您可以打开你注意创建一个search比仅从第二个文件检查匹配值更有用。重写search，它只需要一个指针root和要搜索的值，然后它可以返回一个指示，说明该值是否在您的树中找到（通常指向包含该值的节点的指针），返回一个NULL指针。例如：

struct node *search (struct node *root, int v) 
{ 
    struct node *t = root; 

    while (t != NULL) { 
     if (t->info == v) 
      return t; 
     else { 
      if (v < t->info) 
       t = t->left; 
      else 
       t = t->right; 
     } 
    } 
    return t; 
}

要完成一个维护的方式你的代码，你只需要编写将从第二个文件读取的值的函数，search你的树，然后提示允许删除如果值被发现。同样，它只需要一个指向root的指针和一个FILE*指针来读取值。然后它可以从那里处理呼叫search和delete。（注意：delete可以被重写为直接对由search返回的指针进行操作以避免第二次遍历，但那是另一天）。例如，您的检查，并及时删除功能可能是：

void check_delete (struct node *root, FILE *fp) 
{ 
    int v; 

    while (fscanf (fp, "%d", &v) == 1) { 

     char ch = 'n'; 

     if (search (root, v)) { 

      printf ("\n%d is found\n", v); 
      printf ("\nDo you want to delete %d (y/n): ", v); 
      scanf (" %c", &ch); 

      if (ch == 'y') 
       root = delete (root, v); 
     } 
     else 
      printf ("\n%d Not found\n", v); 
    } 
}

把所有谜题的拼在一起，并提供函数原型上述main（这将最终与一起移动到合适的头文件该结构）和函数下面的定义（它最终将被移动到一个单独的源文件），你会结束与类似于下面的代码。请注意，这不是彻底的重写，其中包含所有建议的更改或改进，但重要的是要开始以正确的方式处理代码所需的信息，并避免早日陷入不良习惯。让我知道你是否还有其他问题：

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

struct node { 
    int info; 
    struct node *left, *right; 
}; 

/* function prototypes */ 
struct node *insert (struct node *root, int item); 
struct node *create (struct node *root, FILE *fp); 
struct node *min (struct node *ptr); 
struct node *delete (struct node *root, int n); 
struct node *search (struct node *root, int v); 
void check_delete (struct node *root, FILE *fp); 
void inorder (struct node *root); 

int main (int argc, char **argv) 
{ 
    FILE *fp1 = fopen (argc > 1 ? argv[1] : "myfile1.txt", "r"); 
    FILE *fp2 = fopen (argc > 2 ? argv[2] : "myfile2.txt", "r"); 
    if (fp1 == NULL) { 
     fprintf (stderr, "cannot open fp1\n"); 
     return 1; 
    } 
    if (fp2 == NULL) { 
     fprintf (stderr, "cannot open fp2\n"); 
     return 1; 
    } 
    struct node *root = NULL; 

    root = create (root, fp1); 
    fclose (fp1); 

    inorder (root); 
    putchar ('\n'); 

    check_delete (root, fp2); 
    fclose (fp2); 
    putchar ('\n'); 

    inorder (root); 
    putchar ('\n'); 

    return 0; 
} 

struct node *insert (struct node *root, int item) 
{ 
    struct node *temp, *temp1, *pre; 

    temp = malloc (sizeof *temp); 
    temp->info = item; 
    temp->left = temp->right = NULL; 

    if (root == NULL) { 
     root = temp; 
    } 
    else { 
     temp1 = root; 

     while (temp1 != NULL) { 
      pre = temp1; 
      if (item < temp1->info) 
       temp1 = temp1->left; 
      else 
       temp1 = temp1->right; 
     } 

     if (item < pre->info) 
      pre->left = temp; 
     else 
      pre->right = temp; 
    } 

    return root; 
} 

struct node *create (struct node *root, FILE *fp) 
{ 
    int num; 
    root = NULL; 

    while (fscanf (fp, "%d", &num) == 1) 
     root = insert (root, num); 

    return root; 
} 

struct node *min (struct node *ptr) 
{ 
    struct node *current = ptr; 
    while (current->left != NULL) 
     current = current->left; 

    return current; 
} 

struct node *delete (struct node *root, int n) 
{ 
    if (root == NULL) { 
     return root; 
    } 
    if (n < root->info) { 
     root->left = delete (root->left, n); 
    } else if (n > root->info) { 
     root->right = delete (root->right, n); 
    } else { 
     if (root->left == NULL) { 
      struct node *p; 
      p = root->right; 
      free (root); 
      return p; 
     } else if (root->right == NULL) { 
      struct node *p; 
      p = root->left; 
      free (root); 
      return p; 
     } 

     struct node *p; 
     p = min (root->right); 
     root->info = p->info; 
     root->right = delete (root->right, p->info); 
    } 
    return root; 
} 

struct node *search (struct node *root, int v) 
{ 
    struct node *t = root; 

    while (t != NULL) { 
     if (t->info == v) 
      return t; 
     else { 
      if (v < t->info) 
       t = t->left; 
      else 
       t = t->right; 
     } 
    } 
    return (t); 
} 

void check_delete (struct node *root, FILE *fp) 
{ 
    int v; 

    while (fscanf (fp, "%d", &v) == 1) { 

     // struct node *t = root; 
     char ch = 'n'; 

     if (search (root, v)) { 

      printf ("\n%d is found\n", v); 
      printf ("\nDo you want to delete %d (y/n): ", v); 
      scanf (" %c", &ch); 

      if (ch == 'y') 
       root = delete (root, v); 
     } 
     else 
      printf ("\n%d Not found\n", v); 
    } 
} 

void inorder (struct node *root) 
{ 
    if (root != NULL) { 
     inorder (root->left); 
     printf ("%d ", root->info); 
     inorder (root->right); 
    } 
}

来源

2016-02-02 23:25:04

作者要求在他/她的代码中更正**删除**的错误，这些错误在一些地方发生了变化，而不是修改整个代码。虽然，你已经给出了很好的建议，但它们不仅仅是处理作者的查询，这可能会导致后面的观众或作者的混淆。 –

你是谁？我必须整天纠正你的草率编辑。你担心你的答案混杂着不必要的变量，我会担心我的交易？ –

这不是仇恨游戏。我只是表达了我的想法。你在谈论什么“草率编辑”和“回答杂乱无章的变数”？我不明白你的意思。 –

在二进制搜索树中执行删除操作c

回答

相关问题