c - 二叉搜索树难点

Question

作为练习的一部分，在我尝试学习编程的过程中，我被要求创建一个使用 1.结构 2.双向链表 3. 二叉搜索树

创建客户数据库.. 我可以将节点添加到列表并进行搜索。 然而，当试图删除客户时，程序无法正常工作并崩溃。 我已经查明问题出在我的 BST_delete 函数，从第 86 行开始，因为如果我不运行这个函数，程序会运行得更好。 更详细地说，我认为我没有更新正确的BST_email_root，它应该是二叉树的最新节点..

这让我发疯!我知道这不是最优雅的代码，但我仍在努力学习!谢谢

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

#define MAX_STRING 250

void myflush();

// Defining a customer structure.
struct customer {
    char *name;
    char *address;
    char *email;
};

// A double linked list. The data field points to a customer struct.
struct double_linked_list {
    struct customer *data;
    struct double_linked_list *previous;
    struct double_linked_list *next;
};

// Defining a pointer for the first one of the customers in the double linked list.

struct double_linked_list *customers_head=0;

// A  node for a Binary Search Tree (BST).

struct BST_node {
    struct double_linked_list *data;
    struct BST_node *left;
    struct BST_node *right;
};

// Defining a variable for the root of the BST that is indexed by the email.
struct BST_node *BST_email_root = 0;

// Looking for a node with a specific email in the BST.

struct BST_node *BST_find_customer(struct BST_node *root, char *email) {
if (root==NULL)
    return NULL;
if (strcmp(email,root->data->data->email)==0)
    return root;
else
    {
    if (strcmp(email,root->data->data->email)==-1)
    return BST_find_customer(root->left,email);
    else
        return BST_find_customer(root->right,email);
    }
}

// A procedure to finding a customer according to his email.

void find_customer() {
    char email[MAX_STRING];
    struct double_linked_list *l;
    struct BST_node *b;
    printf("Give the email of the customer (up to %d characters) : ", MAX_STRING-1);
    gets(email);

    b = BST_find_customer(BST_email_root, email);
    if (b==0)
        printf("There is no customer with this email.\n");
    else
    {
        l = b->data;
        printf("Customer found! \n");
        printf("Name    : %s\n", l->data->name);
        printf("Address : %s\n", l->data->address);
        printf("Email   : %s\n", l->data->email);
    }
}

struct BST_node *findMaxNode(struct BST_node *root)
            {
                if(root->right == NULL) return root;
                findMaxNode(root->right);
            }

// Deleting a node in the BST, according to a given email.

// The function returns the (new?) root of the BST, which might have been changed or not.
struct BST_node *BST_delete(struct BST_node *root, char *email)
{

if (root==NULL)
    return root;
struct BST_node *father=NULL;
char which_son;
while (strcmp(email,root->data->data->email)!=0){ //first, finding root and remembering who's root father
if(root==NULL) {
     return root;
} else if (strcmp(email,root->data->data->email) <0){
     father = root;
     root = root->left;
     if(root==NULL)
        return;
     else which_son = 'l';
} else {
     father = root;
     root = root->right;
    if(root==NULL)
        return;
    else which_son = 'r';
}
}
// now you have both the root node, and its father
if ( (root->right == NULL) && (root->left == NULL) ){ //case 1, if it's a leaf
 free(root);

} else if (root->left == NULL) { //case 2
    if (which_son == 'l') {
        father->left = root->right;
    } else {
        father->right = root->right;
    }

} else { //case 3 : here i get the "rightest" son of root's left son
    struct BST_node *replacing_node = root->left;
    while (replacing_node->right != NULL) {
        replacing_node = replacing_node->right;
    } //now replacing_node is a leaf, and can replace root
    if (which_son == 'l') {
        father->left = replacing_node;
        replacing_node->left = root->left;
        replacing_node->right = root->right;
    } else {
        father->right = replacing_node;
        replacing_node->left = root->left;
        replacing_node->right = root->right;
    }
    }
    return root;
}


// This function adds a new node in the Binary Search Tree (BST) rooted by *root,

struct BST_node *new_BST_node(struct BST_node *root, struct double_linked_list *l)
    {
    if (root==NULL)
        {
        root= (struct BST_node *)malloc(sizeof(struct BST_node ));
        if (root==NULL)
            {
            printf("Out of Memory!");
            exit(1);
            }

        root->data=l;
        root->left=NULL;
        root->right=NULL;
        return root;
        }

    if ((strcmp(l->data->email,root->data->data->email))<0)
                root->left =new_BST_node(root->left,l);
    else
        root->right =new_BST_node(root->right,l);


    };


// A procedure to modify the data concerning an existing customer
void modify_customer() {
    char old_email[MAX_STRING];
    char new_email[MAX_STRING];
    char new_name[MAX_STRING];
    char new_address[MAX_STRING];
    char ans;

    struct BST_node *ind;
    struct double_linked_list *l;

    printf("Give the email of the customer you want to modify: ");
    gets(old_email);
    ind = BST_find_customer(BST_email_root, old_email);
    if (ind == 0)
    {
        printf("There is no customer with this email.\n");
        return;
    }

    l = ind->data;  // The node in the double linked list for the customer
    printf("Old name: %s\n", l->data->name);
    printf("Give the new name (up to %d characters, <Enter> if it does not change): ", MAX_STRING - 1);
    gets(new_name);
    if (new_name[0] == 0)
        strcpy(new_name, l->data->name);

    printf("Old address: %s\n", l->data->address);
    printf("Give the new address (up to %d characters, <Enter> if it does not change): ", MAX_STRING - 1);
    gets(new_address);
    if (new_address[0] == 0)
        strcpy(new_address, l->data->address);

    printf("Old email: %s\n", l->data->email);
    printf("Give the new email (up to %d characters, <Enter> if it does not change): ", MAX_STRING-1);
    gets(new_email);
    if (new_email[0] == 0)
        strcpy(new_email, l->data->email);

    if (strcmp(l->data->email, new_email))
    {
        if (BST_find_customer(BST_email_root, new_email))
        {
            printf("New email already exists. Modification aborted.\n");
            return;
        }
    }

    printf("\n\n");
    printf("REPLACE:\n");
    printf("Name    : %s\n", l->data->name);
    printf("Address : %s\n", l->data->address);
    printf("Email   : %s\n", l->data->email);
    printf("WITH:\n");
    printf("Name    : %s\n", new_name);
    printf("Address : %s\n", new_address);
    printf("Email   : %s\n\n", new_email);

    printf("Are you sure? (Y)es/(N)o\n");
    scanf(" %c", &ans);
    myflush();
    if (ans == 'Y' || ans == 'y')
    {
        free(l->data->name);
        l->data->name = strdup(new_name);
        free(l->data->address);
        l->data->address = strdup(new_address);

        if (strcmp(l->data->email, new_email) != 0)
            // Only in case the email has been changed, we have to maintain the BST
        {
            BST_email_root=BST_delete(BST_email_root, l->data->email);
            free(l->data->email);
            l->data->email = strdup(new_email);
            BST_email_root=new_BST_node(BST_email_root, l);
        }
    }
}

//  add a new customer
struct double_linked_list *new_customer()
{
    char name[MAX_STRING], address[MAX_STRING], email[MAX_STRING];
    struct BST_node *b;
    struct double_linked_list *l;
    struct customer *c;

    printf("\nADDING A CUSTOMER\n\n\n");
    printf("Give the name (up to %d characters): ", MAX_STRING-1);
    gets(name);

    printf("Give the address (up to %d characters): ", MAX_STRING - 1);
    gets(address);

    printf("Give the email (up to %d characters): ", MAX_STRING - 1);
    gets(email);

        // check for duplicate email
    b = BST_find_customer(BST_email_root, email);
    if (b)
    {
        printf("Duplicate email. Customer aborted.\n");
        return 0;
    }

    c = (struct customer *) malloc(sizeof(struct customer));
    if (c == 0)
    {
        printf("Not enough memory.\n");
        return 0;
    }

    c->name = strdup(name); // check for memory allocation problem
    if (c->name == 0) return 0;
    c->address = strdup(address);   // check for memory allocation problem
    if (c->address == 0) return 0;
    c->email = strdup(email);   // check for memory allocation problem
    if (c->email == 0) return 0;

    l = (struct double_linked_list*) malloc(sizeof(struct double_linked_list));
    if (l == 0)
    {
        printf("Not enough memory.\n");
        free(c->name);
        free(c->address);
        free(c->email);
        free(c);
        return 0;
    }

    l->data = c;
    l->previous = 0;
    l->next = customers_head;

    if (customers_head)
        customers_head->previous = l;

    customers_head = l;

    BST_email_root = new_BST_node(BST_email_root, l);

    return l;
}

// This function deletes a customer, based on its email
void delete_customer() {
    char email[MAX_STRING];
    struct BST_node *n_del;
    printf("Give the email of the customer you want to delete(up to %d characters) : ", MAX_STRING-1);
    gets(email);

    n_del = BST_find_customer(BST_email_root, email);
    if (n_del==0)
        printf("There is no customer with this email.\n");

    else
    {
    struct double_linked_list *current = n_del->data;
    //struct double_linked_list *temp;
    //struct double_linked_list *prev = customers_head;

    if (current->next==NULL &&current->previous==NULL)
        {
        free(current);
        customers_head=0;
        }

    else if (current->next==NULL) //TA EXOUN ANAPODA??i oxi..Den exw katalaveiNEXT=0 EINAI GIA TO PROTO STOIXEIO pou vazw. An exw mono ena stoixeio ti ginete? prepei na to dw..
        {
        printf("1");
        current->previous->next=NULL;
        free(current);
        }

    else if (current->previous==NULL)
        { printf("2");
            current->next->previous=NULL;   //Apla kane to previous tou proigoumenou apo ton teleytaio pou thes na kaneis na mi deixnei pouthena..
        customers_head=current->next;
        free(current);
        }
    else
       {
        printf("3");
        current->next->previous = current->previous;  //vle ton proigoumeno komvo na deixnei ston epomeno kai ton epomeno ston proigoumeno
        current->previous->next = current->next;      //Ftiakse to customer's head na deixnei sto proigoumeno pou einai pleon to pio prosfato sti lista
       }
    }

    BST_email_root=BST_delete(BST_email_root, email);
}


void displaymenu() {
    printf("\n\n");
    printf("1. New customer\n");
    printf("2. Find customer using email\n");
    printf("3. Modify customer\n");
    printf("4. Delete customer\n");
    printf("0. Exit\n\n");
    printf("Give a choice (0-6) : ");
}

// This function empties the buffer of the standard input (stdin), that is, of the keyboard
void myflush()
{
    char ch;
    while ((ch = getchar()) != '\n' && ch != EOF);
}


// The main function
int main() {
    int choice;
    do {
        displaymenu();
        scanf("%d", &choice);
        myflush();
        switch (choice) {
        case 1:
            new_customer();
            break;
        case 2:
            find_customer();
            break;
        case 3:
            modify_customer();
            break;
        case 4:
            delete_customer();
            break;

        default:
            printf("Wrong selection.\n\n");
        }
    } while (choice != 0);

    return 0;
}

Answer 1

在不深入研究您的代码的情况下，我立即看到了一件事。你的陈述

...  if (strcmp(email,root->data->data->email) == -1) {

假设如果一个比另一个小，则返回值正好是-1 . strcmp 的返回值然而，在这种情况下，只是保证是 < 0 ，不完全是-1 (参见 strcmp reference)。

因此，很可能在搜索“父亲”时，您没有找到要查找的节点...