binary-search-tree 相关问题

二叉搜索树是由具有左子节点和右子节点的根节点组成的数据结构。左节点及其所有后代的值小于根节点,而右节点及其所有后代的值大于根节点。根节点的子节点遵循相同的模式。这给了我们一个由有序元素组成的树。

36个节点,叶子深度差最多为1,可以组成多少棵二叉搜索树?

我正在考虑这个挑战: 可以用 36 个节点制作多少棵二叉搜索树,使得叶子的深度之差最多为 1? 我可以说这也意味着...

回答 1 投票 0

36个节点可以组成多少棵叶子深度差最多为1的二叉搜索树?

我正在考虑这个挑战: 36个节点可以组成多少棵二叉搜索树,叶子的深度差最多为1? 我可以说这也意味着有多少

回答 1 投票 0

我的 BST 删除方法有什么问题?

编辑:由于某种原因,我无法附上我正在使用的 BST 的照片,但您可以使用此链接查看它:https://ibb.co/zhsCSrg 我正在使用二叉搜索树,并且正在编写伪代码......

回答 1 投票 0

使用生成器在 BST 上执行中序树遍历

因此给出以下内容: def 中序(t): 如果t: 中序(t.left) 产量 t.key 中序(t.right) x = [ n 表示 inorder(r) 中的 n ] x 只包含根节点,为什么? 这是

回答 2 投票 0

当二叉搜索树有 2 个子节点时如何删除节点

我正在创建我的第一棵树。看起来我陷入了如何在树有 2 个子节点时从树中删除节点的问题。目前我正在尝试: 找到中序后继者(...的最左边的孩子

回答 1 投票 0

Common Lisp 中二叉搜索树实现中的类型错误

我目前正在 Common Lisp 中实现二叉搜索树,并且遇到了类型错误。当我尝试在树中查找最小或最大键时,会出现错误。这是

回答 1 投票 0

二叉搜索树库在我自己的IDE上测试leetcode

我目前正在做一道关于 leet 代码的 BST 问题,但我更喜欢在自己的 IDE 上做。我正在使用 IntelliJ IDEA。一个例子是 leet code 的问题是求最大路径和。 我的代码是

回答 1 投票 0

为什么我的c代码检查二叉搜索树是否完整(使用数组进行检查)根据valgrind检查会导致内存泄漏问题

#包括 #包括 typedef 结构节点 { 整数值; 结构节点*左; 结构节点*右; }节点; 节点* createNode(int n) { 节点* new = (节点*)malloc(

回答 2 投票 0

为什么红黑树删除功能的最坏情况旋转数是恒定的,但颜色翻转却不是?

我在 Stack Overflow 上找到了这个答案。答案意味着,在最坏的情况下,红黑树“删除”功能的旋转次数是恒定的,并且颜色翻转的数量会增长

回答 1 投票 0

使用二叉搜索树的 C 语言简单数据库

我的任务是用 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

回答 1 投票 0

为什么使用此代码执行 DFS 会导致重复叶子?

我正在编写一个算法来辨别两棵树是否具有相同的叶子。 它们具有相同顺序的相同叶子编号,因此返回 true。 这是我写的代码: 函数 leafSimi...

回答 1 投票 0

AVL 树的“删除”操作在实践中最坏的情况是什么样的?

我找到了这个堆栈溢出答案:https://stackoverflow.com/a/28846533/10061169,这表明AVL树“删除”操作可以有O(log(N))轮换。我目前正在努力寻找...

回答 1 投票 0

查找后序 BST 排列的数量

我正在处理一个问题,内容如下: 找到从 1 到 n 个 BST 的排列(后序遍历)。 例如,对于 n = 3:我们有 6! - 1 = 5 种排列,因为 (3 1 2) 不是 BST 后序。 我...

回答 1 投票 0

如何在 Java 中创建二叉搜索树?

我正在 OOP 课上做作业,但我发现自己哪里出错了。即使我没有对任何节点做任何事情,我仍然不断收到 NullPointerExceptions...

回答 1 投票 0

寻找两个节点的共同祖先的问题

我有以下代码用于查找二叉搜索树中两个节点的第 n 个共同祖先。如果代码可以找到第 n 个共同祖先,则将返回共同祖先,如果存在...

回答 1 投票 0

保存和加载xml文件的步骤是什么?

保存和加载xml文件的步骤是什么?保存和加载xml文件的步骤是什么? if (element.getElementsByTagName(Customer.KEY_NAME).getLength() > 0) { 名称 = 元素。

回答 1 投票 0

重新平衡任意 BST?

参考: 我被问到这个问题@MS SDE 面试,第三轮。这不是家庭作业的问题。我也思考了一下,并在下面提到了我的方法。 问题: 修改 BST,使其成为...

回答 5 投票 0

如何修复红黑树,避免不必要的旋转?

我正在用Java实现红黑树,并在插入过程中遇到旋转问题。具体来说,当我将数字 10 和 13 插入树中时,它甚至执行旋转

回答 1 投票 0

我尝试使用迭代插入 BST 树,但输出不完整。可能哪里有问题?

我正在使用迭代机制在BST中进行插入操作。我使用递归进行了有序遍历,以快速显示我的树并知道我做的是对还是错。然而,...

回答 1 投票 0

为什么我的二叉树删除会删除树的整个左侧部分?

我有一个作业,其中我需要在 C 中实现二叉搜索树。在我尝试为树实现删除函数时,我未能实现

回答 1 投票 0

© www.soinside.com 2019 - 2024. All rights reserved.