BST 输出差异 - 寻求解决

问：

{加分：增加特定成员的分。减去点数：减少特定成员的点数。删除成员：从系统中删除成员。搜索成员：在 BST 中查找成员，并在树中报告其点和深度。按字母顺序先行计数：确定其名称按字母顺序排列在给定成员之前的成员数。

我已经在 C 语言中实现了一个二叉搜索树 （BST） 来管理客户数据，并且我遇到了程序输出与预期输出之间的一些差异。我想了解可能导致这些差异的原因以及如何解决它们。

以下是该问题的简要概述：

我有一系列输入命令，包括在BST中添加、减去、删除和搜索客户。执行这些命令后，我将程序的输出与预期输出进行比较，发现存在差异。

下面是输入和输出的示例：

输入：

18 添加迈克尔 30 添加丽莎 40 添加索菲亚 45 最多添加 28 添加 Natalia 60 添加 Lucas 32 添加亚历克斯 10 添加索菲亚 3 添加 Oliver 20 子最大 30 德尔迈克尔 替补 娜塔莉亚 28 搜索 Alex 搜索 Oliver 搜索 Michael 替补迈克尔 20 最大count_smaller 德尔马克斯 输出：

迈克尔 30 丽莎 40 索菲亚 45 最多 28 娜塔莉亚 60 卢卡斯 32 亚历克斯 10 索菲亚 48 奥利弗 20 最大 0 Michael已删除 娜塔莉亚 32 亚历克斯 10 0 奥利弗 20 4 未找到 Michael 未找到 Michael 6 Max 已删除 索菲亚 48 丽莎 40 卢卡斯 32 娜塔莉亚 32 奥利弗 20 亚历克斯 10

我的输出： 迈克尔 30 丽莎 40 索菲亚 45 最多 28 娜塔莉亚 60 卢卡斯 32 亚历克斯 10 索菲亚 48 奥利弗 20 最大 0 Michael已删除 娜塔莉亚 32 Alex 未找到 奥利弗 20 4 未找到 Michael 迈克尔 0 6 Max 已删除 索菲亚 48 丽莎 40 卢卡斯 32 娜塔莉亚 32 奥利弗 20 亚历克斯 10

#define MAXLEN 19

typedef struct customer {
    char name[MAXLEN + 1];
    int points;
} customer;

typedef struct treenode {
    customer* cPtr;
    struct treenode* left;
    struct treenode* right;
} treenode;

// Function Declarations
treenode* createNewNode(customer* c);
treenode* insertNode(treenode* root, customer* c, int addPoints, int* isNew);
treenode* findNode(treenode* root, char* name);
int findNodeWithDepth(treenode* root, char* name, int* depth);
void updatePoints(treenode* root, char* name, int points);
treenode* deleteNode(treenode* root, char* name);
treenode* minValueNode(treenode* node);
int countBefore(treenode* root, char* name);
void inOrderCollect(treenode* root, customer** arr, int* index);
customer* readCustomer(char* name, int points);
int compareCustomers(const void* a, const void* b);
void sortCustomers(customer** customers, int n);

// Function Definitions
treenode* createNewNode(customer* c) {
    treenode* newNode = (treenode*)malloc(sizeof(treenode));
    newNode->cPtr = c;
    newNode->left = newNode->right = NULL;
    return newNode;
}

treenode* insertNode(treenode* root, customer* c, int addPoints, int* isNew) {
    if (root == NULL) {
        *isNew = 1;
        return createNewNode(c);
    }
    int cmp = strcmp(c->name, root->cPtr->name);
    if (cmp < 0) {
        root->left = insertNode(root->left, c, addPoints, isNew);
    } else if (cmp > 0) {
        root->right = insertNode(root->right, c, addPoints, isNew);
    } else {
        *isNew = 0;
        root->cPtr->points += addPoints;
    }
    return root;
}

treenode* findNode(treenode* root, char* name) {
    if (root == NULL) return NULL;
    if (strcmp(name, root->cPtr->name) == 0)
        return root;
    else if (strcmp(name, root->cPtr->name) < 0)
        return findNode(root->left, name);
    else
        return findNode(root->right, name);
}

int findNodeWithDepth(treenode* root, char* name, int* depth) {
    if (root == NULL) {
        return -1;  // Not found
    }
    int cmp = strcmp(name, root->cPtr->name);
    if (cmp == 0) {
        return root->cPtr->points;
    } else if (cmp < 0) {
        (*depth)++;
        return findNodeWithDepth(root->left, name, depth);
    } else {
        (*depth)++;
        return findNodeWithDepth(root->right, name, depth);
    }
}

treenode* minValueNode(treenode* node) {
    treenode* current = node;
    while (current && current->left != NULL)
        current = current->left;
    return current;
}

treenode* deleteNode(treenode* root, char* name) {
    if (root == NULL) return root;

    if (strcmp(name, root->cPtr->name) < 0)
        root->left = deleteNode(root->left, name);
    else if (strcmp(name, root->cPtr->name) > 0)
        root->right = deleteNode(root->right, name);
    else {
        if (root->left == NULL) {
            treenode* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            treenode* temp = root->left;
            free(root);
            return temp;
        }
        treenode* temp = minValueNode(root->left); // Changed to left subtree
        root->cPtr = temp->cPtr;
        root->left = deleteNode(root->left, temp->cPtr->name);
    }
    return root;
}

int countBefore(treenode* root, char* name) {
    if (root == NULL) return 0;
    if (strcmp(name, root->cPtr->name) > 0)
        return 1 + countBefore(root->left, name) + countBefore(root->right, name);
    else
        return countBefore(root->left, name);
}

void inOrderCollect(treenode* root, customer** arr, int* index) {
    if (root != NULL) {
        inOrderCollect(root->left, arr, index);
        arr[*index] = root->cPtr;
        (*index)++;
        inOrderCollect(root->right, arr, index);
    }
}

customer* readCustomer(char* name, int points) {
    customer* c = (customer*)malloc(sizeof(customer));
    strcpy(c->name, name);
    c->points = points;
    return c;
}

int compareCustomers(const void* a, const void* b) {
    customer* custA = *(customer**)a;
    customer* custB = *(customer**)b;
    if (custA->points == custB->points)
        return strcmp(custA->name, custB->name);
    return custB->points - custA->points;
}

void sortCustomers(customer** customers, int n) {
    qsort(customers, n, sizeof(customer*), compareCustomers);
}

// Main Function
int main() {
    int n, i, points, depth, isNew;
    char command[15], name[MAXLEN + 1];
    treenode* root = NULL;

    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        scanf("%s", command);
        if (strcmp(command, "add") == 0) {
            scanf("%s %d", name, &points);
            customer* c = readCustomer(name, points);
            isNew = 0;
            root = insertNode(root, c, points, &isNew);
            if (!isNew) free(c); // Free the customer if not inserted
            printf("%s %d\n", name, findNode(root, name)->cPtr->points);
        }
        else if (strcmp(command, "sub") == 0) {
            scanf("%s %d", name, &points);
            treenode* node = findNode(root, name);
            if (node != NULL) {
                node->cPtr->points = node->cPtr->points > points ? node->cPtr->points - points : 0;
            }
            printf("%s %d\n", name, node ? node->cPtr->points : 0);
        }
        else if (strcmp(command, "del") == 0) {
            scanf("%s", name);
            if (findNode(root, name)) {
                root = deleteNode(root, name);
                printf("%s deleted\n", name);
            } else {
                printf("%s not found\n", name);
            }
        }
        else if (strcmp(command, "search") == 0) {
            scanf("%s", name);
            depth = 0;
            points = findNodeWithDepth(root, name, &depth);
            if (points >= 0) {
                printf("%s %d %d\n", name, points, depth);
            } else {
                printf("%s not found\n", name);
            }
        }
        else if (strcmp(command, "count_smaller") == 0) {
            scanf("%s", name);
            int count = countBefore(root, name);
            printf("%d\n", count);
        }
    }

    customer** customers = (customer**)malloc(sizeof(customer*) * n);
    int index = 0;
    inOrderCollect(root, customers, &index);
    sortCustomers(customers, index);

    for (i = 0; i < index; i++) {
        printf("%s %d\n", customers[i]->name, customers[i]->points);
        free(customers[i]);
    }
    free(customers);
    // Free the tree here if necessary
    return 0;
}