binary-tree 相关问题

我的任务是用 C 语言编写一个简单的数据库。该程序将接收标准输入中的指令并打印它们的结果。说明的格式如下： : 我的任务是用 C 语言编写一个简单的数据库。该程序将接收标准输入中的指令并打印其结果。说明的格式如下：<operation>: <year> <month> <day> <name>。有 3 个操作：“S”（搜索）、“F”（查找）和“D”（删除）。存储指令会将条目存储在数据库中，如果条目已在数据库中，则打印“已存储”或“已存储”。如果该条目在数据库中，查找指令将打印“找到”，否则将打印“未找到”。删除指令将从数据库中删除该条目，如果找到该条目，则打印“已删除”，否则将打印“未找到”。由于时间限制，我不能简单地使用链表作为我的解决方案。首先，我尝试使用哈希映射（pastebin 链接）。我尝试使用二叉搜索树，但对条目进行哈希处理（pastebin链接）。这些尝试都没有成功（他们通过了简单的测试，但在大型测试中失败了）。最后我只是尝试了“最简单”的方法 - 存储整个条目的二叉树。这次尝试也通过了简单的测试，但在大型测试中失败了......现在我完全陷入困境。这是我当前的代码： #ifdef __STDC_LIB_EXT1__ #define __STDC_WANT_LIB_EXT1__ 1 #define scanf scanf_s // Bit hacky ngl. #endif #include <stddef.h> // NULL #include <stdio.h> // scanf()/scanf_s(), puts() #include <stdlib.h> // malloc(), free() #include <string.h> // strcmp() typedef struct { unsigned short year; unsigned char month, day; char *name; } User; typedef struct BinaryTreeNode { struct BinaryTreeNode *left, *right; User user; } BinaryTree; static inline BinaryTree *BinaryTree_alloc(User user) { BinaryTree *tree = (BinaryTree *) malloc(sizeof(BinaryTree)); tree->left = NULL; tree->right = NULL; tree->user = user; return tree; } static inline void BinaryTree_dealloc(BinaryTree *tree) { if (tree) { BinaryTree_dealloc(tree->left); BinaryTree_dealloc(tree->right); free(tree); } } int BinaryTree_compare(BinaryTree *tree, User user) { if (tree->user.year > user.year) return 1; else if (tree->user.year < user.year) return -1; else if (tree->user.month > user.month) return 1; else if (tree->user.month < user.month) return -1; else if (tree->user.day > user.day) return 1; else if (tree->user.day < user.day) return -1; else return strcmp(tree->user.name, user.name); } BinaryTree *BinaryTree_store(BinaryTree *tree, User user) { if (tree) { switch (BinaryTree_compare(tree, user)) { case 1: tree->left = BinaryTree_store(tree->left, user); break; case -1: tree->right = BinaryTree_store(tree->right, user); break; default: puts("Already stored"); } return tree; } puts("Stored"); return BinaryTree_alloc(user); } BinaryTree *BinaryTree_find(BinaryTree *tree, User user) { if (tree) switch (BinaryTree_compare(tree, user)) { case 1: return BinaryTree_find(tree->left, user); case -1: return BinaryTree_find(tree->right, user); default: puts("Found"); } else puts("Not found"); return tree; } static inline User BinaryTree_find_min_user(BinaryTree *tree) { while (tree->left) tree = tree->left; return tree->user; } BinaryTree *BinaryTree_delete(BinaryTree *tree, User user) { if (tree) switch (BinaryTree_compare(tree, user)) { case 1: tree->left = BinaryTree_delete(tree->left, user); break; case -1: tree->right = BinaryTree_delete(tree->right, user); break; default: if (!tree->left && !tree->right) { free(tree->user.name); free(tree); tree = NULL; puts("Deleted"); } else if (!tree->left || !tree->right) { BinaryTree *root = tree; if (!tree->left) tree = tree->left; if (!tree->right) tree = tree->right; free(root->user.name); free(root); puts("Deleted"); } else { User min_user = BinaryTree_find_min_user(tree->right); tree->user = min_user; tree->right = BinaryTree_delete(tree->right, min_user); } } else puts("Not found"); return tree; } int main() { char operation; User user; BinaryTree *tree = BinaryTree_alloc((User) { 0, 0, 0, NULL }); while (5 == scanf(" %c : %hu %hhu %hhu %m[^\n]", &operation, &user.year, &user.month, &user.day, &user.name)) { switch (operation) { case 'S': BinaryTree_store (tree, user); break; case 'F': BinaryTree_find (tree, user); break; case 'D': BinaryTree_delete(tree, user); break; } } BinaryTree_dealloc(tree); } 有人请帮助我：3 我不确定问题是什么，但您提到“大型”测试失败，因此在递归函数上从传递 User 切换到 User * 将使用更少的堆栈空间。（不固定）C 不保证尾部调用优化，因此您应该更喜欢迭代而不是递归算法，后者本质上具有未绑定的堆栈大小要求。如果您先处理特殊情况，那么通常很长的正常情况的缩进就会较少。这也是您通常期望的递归函数（首先是基本情况）。 BinaryTree_compare() 很奇怪，因为您正在比较两个用户，因此将其更改为 User_compare() 并传入两个 User *。调用者假定函数返回 -1、0 或 1，但 strcmp() 的情况并非如此，因此请确保现在确实如此。在通话中，我还切换了参数，因为对我来说，-1 表示树的 left 侧和 +1 右侧更有意义。（未修复）考虑重构 BinaryTree_find() 和/或 BinaryTree_store() 以消除非常相似的代码。 main() 分配一个空节点，但我认为仅仅盯着 NULL 更有意义。我删除了inline，因为编译器可能比你更了解它是否使用它。我可能会删除 BinaryTree_find_min_user() 并只在 BinaryTree_delete() 中添加那句台词。 #ifdef __STDC_LIB_EXT1__ #define __STDC_WANT_LIB_EXT1__ 1 #define scanf scanf_s // Bit hacky ngl. #endif #include <stddef.h> // NULL #include <stdio.h> // scanf()/scanf_s(), puts() #include <stdlib.h> // malloc(), free() #include <string.h> // strcmp() typedef struct { unsigned short year; unsigned char month, day; char *name; } User; typedef struct BinaryTreeNode { struct BinaryTreeNode *left, *right; User user; } BinaryTree; static BinaryTree *BinaryTree_alloc(const User *user) { BinaryTree *tree = malloc(sizeof *tree); tree->left = NULL; tree->right = NULL; tree->user = *user; return tree; } static void BinaryTree_dealloc(BinaryTree *tree) { if (!tree) return; BinaryTree_dealloc(tree->left); BinaryTree_dealloc(tree->right); free(tree); } int User_compare(const User *a, const User *b) { if (a->year > b->year) return 1; else if (a->year < b->year) return -1; else if (a->month > b->month) return 1; else if (a->month < b->month) return -1; else if (a->day > b->day) return 1; else if (a->day < b->day) return -1; int rv = strcmp(a->name, b->name); return rv < 0 ? -1 : rv > 0 ? 1 : 0; } BinaryTree *BinaryTree_store(BinaryTree *tree, const User *user) { if (!tree) { puts("Stored"); return BinaryTree_alloc(user); } switch (User_compare(user, &tree->user)) { case -1: tree->left = BinaryTree_store(tree->left, user); break; case 1: tree->right = BinaryTree_store(tree->right, user); break; default: puts("Already stored"); } return tree; } BinaryTree *BinaryTree_find(BinaryTree *tree, const User *user) { if (!tree) { puts("Not found"); return NULL; } switch (User_compare(user, &tree->user)) { case -1: return BinaryTree_find(tree->left, user); case 1: return BinaryTree_find(tree->right, user); default: puts("Found"); } return tree; } static User *BinaryTree_find_min_user(BinaryTree *tree) { for (; tree->left; tree = tree->left); return &tree->user; } BinaryTree *BinaryTree_delete(BinaryTree *tree, User *user) { if (!tree) { puts("Not found"); return tree; } switch (User_compare(user, &tree->user)) { case -1: tree->right = BinaryTree_delete(tree->right, user); break; case 1: tree->left = BinaryTree_delete(tree->left, user); break; default: if (!tree->left && !tree->right) { free(tree->user.name); free(tree); tree = NULL; puts("Deleted"); } else if (!tree->left || !tree->right) { BinaryTree *root = tree; if (!tree->left) tree = tree->left; if (!tree->right) tree = tree->right; free(root->user.name); free(root); puts("Deleted"); } else { User *min_user = BinaryTree_find_min_user(tree->right); tree->user = *min_user; tree->right = BinaryTree_delete(tree->right, min_user); } } return tree; } int main() { char operation; User *user = &(User) {0}; BinaryTree *tree = NULL; while (5 == scanf(" %c : %hu %hhu %hhu %m[^\n]", &operation, &user->year, &user->month, &user->day, &user->name)) { switch (operation) { case 'S': tree = BinaryTree_store (tree, user); break; case 'F': BinaryTree_find (tree, user); break; case 'D': BinaryTree_delete(tree, user); break; } } BinaryTree_dealloc(tree); } 和示例运行： $ cat input.txt S : 2023 11 28 m S : 2023 11 28 m S : 2023 11 28 a S : 2023 11 28 z F : 2023 11 28 m D : 2023 11 28 m F : 2023 11 28 m $ ./a.out < input.txt Stored Already stored Stored Stored Found Deleted Not found

c database binary-tree binary-search-tree binary-search

回答 1 投票 0

二叉树删除实现

我正在尝试在 Dart 中实现一个简单的二叉树。我的插入和搜索似乎工作得很好，但我的删除/删除却不行。无效删除（int targetData）{ 二叉搜索树节点？目标=查找（

flutter dart data-structures binary-tree

回答 1 投票 0

了解 C 语言中二叉树实现的功能

我在使用删除函数从二叉树中删除节点时遇到问题。这是我的第一个树程序，我发现书籍和互联网页面的删除功能非常令人困惑。我写了

c data-structures tree binary-tree

回答 1 投票 0

如何正确遍历一棵树？

以下代码在树中插入一些节点，并显示同一 B 树的中序和先序遍历。中序遍历似乎是正确的，因为节点是按 asc 排列的...