-
4 votesanswersviews
从二叉搜索树中删除多个节点
我有一个用C创建的二叉搜索树 . 问题是我找不到一种有效的方法来删除所有节点，例如id> 5 . 当我遍历树时，如果删除一个节点，则递归会出错，因为结构不一样 . 有什么办法，而不是使用帮助堆栈来保存数据之前从树中删除它们？ -
0 votesanswersviews
在二叉搜索树中删除
所以当我在二进制搜索树中删除时，我是否需要有7种不同的情况，即 左叶; 右叶; 只有左孩子的左孩子 . //i.e要删除的节点是它父节点的左子节点，它只剩下子节点 . 只有正确孩子的左孩子 . 只有左孩子的右孩子 . 只有正确孩子的正确孩子 . 要删除的节点包含两个子节点，即右侧和左侧 . 现在当这段代码使用 if-else 时，它变得非常讨厌..有没有其他方法可... -
0 votesanswersviews
为什么这个移植函数适用于二叉搜索树？
在CLRS中的二叉搜索树章节中，我遇到了移植函数，它将节点 u 替换为节点 v ，并在父元素中进行了适当的更改 . 这是我为移植功能编写的代码： void transplant(Node* root, Node* u, Node* v) { if(u->parent == NULL) root = v; else if(u == u->parent-&g... -
0 votesanswersviews
二进制搜索树节点删除
我正在实现从二叉搜索树中删除节点的功能 . 该功能的原型已设置，我无法更改它，这是一项学校作业 . 我的代码： typedef struct tBSTNode { char Key; struct tBSTNode * LPtr; ... -
0 votesanswersviews
二进制搜索树，删除节点
我正在编写一个程序，如果你愿意，它会读入“学生记录”，然后根据数据将其分成4个二进制搜索树 . 我试图删除一个节点，但不是实际删除它，我只想在结构中设置一个标志，它基本上让我知道它已被“删除” . 这是我的代码，它给了我几个错误： void deleteNode( TreeNodePtr *treePtr, SREC R, unsigned long key)/*ADD HOW*/ { ... -
0 votesanswersviews
删除二叉搜索树中的根节点时出现问题
我试图从我的BST删除根节点，然后打印树 inorder . 根删除似乎是一个问题，所有其他节点都被成功删除 . Root是20 . inOrderPrint 5 6 7 8 9 10 17 18 20 23 24 25 29 55 56 57 58 59 提供要删除的节点 20 删除后 5 6 7 8 9 10 17 18 20 5 6 7 8 9 10 17 18 23 24 25 29 ... -
0 votesanswersviews
二进制搜索树删除不起作用，为什么？
我试图在C中实现二进制搜索树 . 但我陷入了删除操作，当我运行代码时它不会删除指定的值 . 在调用delete之前:(调用 inorder() ） 16 19 23 调用delete后:(调用 inorder() ） 16 19 23 码： void deleteNode(struct node *n, int data) { struct node *temp; if(n... -
0 votesanswersviews
删除二进制搜索树的功能无法正常工作
这是用C编码的二叉搜索树的删除功能，但这不能正常工作 . 应该删除的节点被垃圾值替换 . void delete(struct node* root,int data) { { struct node* t1; if(root==0) { printf("element not found\n"); } else if(data>r... -
5 votesanswersviews
balancer 二叉搜索树（BST）
我正在尝试创建一个balance_bst（bstNode root）函数，但我正在努力实现 . 我正在将该函数实现为模板函数，因为我的bstNode类是一个模板类 . 这是（部分）我的代码： template<class Item, class Key> class bstNode{ public: //Constructor bstNode(const Item&a... -
1 votesanswersviews
从BST树创建一个红黑树 - 最快的方法？
我必须为我的大学课程创建和描述一个算法，该算法获得BST树T并创建新的BST树T'，以满足属性（并且尽可能快）：1）T'具有与T相同的精确键值2）T'是红黑树 到目前为止我've had only one idea: randomize 0 or 1. In case of 0, get the max key node from left subtree of T and insert it i... -
0 votesanswersviews
一种有效的伪代码，用于检查给定的BST是否是有效的AVL树
如果给定的BST树是有效的AVL树，我需要编写一个算法（伪代码） . 在这样做时，我需要给每个节点一个等级（在AVL树等级中意味着节点的高度），因此结果将是有效的AVL树 . 我想到了一个简单的算法，它在每个步骤中计算一个节点的高度和它的两个儿子的高度（如果儿子是空的，那么高度是-1），然后检查高度之间的差异是否为1,1或1,2或2,1 . 如果没有那么它不是AVL树 . 如果是，我们对node.... -
6 votesanswersviews
O（logn）总是一棵树吗？
我们总是看到（二元搜索）树上的操作具有O（logn）最差情况下的运行时间，因为树高是logn . 我想知道我们是否被告知算法的运行时间是logn的函数，例如mnlogn，我们可以得出结论它必须涉及（增强的）树吗？ 编辑：感谢您的评论，我现在意识到分治和二叉树在视觉/概念上是如此相似 . 我从来没有在两者之间 Build 联系 . 但我想到一个案例，其中O（logn）不是一个分治算法，它涉及一棵没有... -
0 votesanswersviews
链接列表插入与BST插入时间成本
在链表中，插入是O（1），因为我们假设我们已经知道要插入的位置 . 在二叉搜索树中，插入是O（logN），因为我们必须在插入之前找到插入的位置（但是，实际插入过程应该是恒定时间） . 为什么在LinkedList的情况下我们假设我们已经有了位置，而在BST中我们假设我们必须遍历节点以找到插入位置（导致时间复杂度为O（logN）？ -
165 votesanswersviews
为什么std :: map实现为红黑树？
为什么 std::map 实现为red-black tree？ 那里有几个 balancer 的binary search trees（BST） . 选择红黑树的设计权衡是什么？ -
7 votesanswersviews
std :: map和二进制搜索树
我已经读过std map是使用二叉搜索树数据结构实现的 . BST是一种顺序数据结构（类似于数组中的元素），它将元素存储在BST节点中并按顺序维护元素 . 对于例如如果element小于node，则将其存储在节点的左侧，如果它大于node，则将其存储在node的右侧 . 通过这种方法，我们实现了搜索，插入等各种操作的O（log n）复杂度 . 但是，std map是一个关联容器 . 我们有一个键和... -
0 votesanswersviews
互联网上的大多数代码片段是否存在二进制搜索树的深度错误？
我目前正在实现二进制搜索树 . 我的教材说明树的深度等于最深叶的深度 . 节点本身的深度定义为从根到该节点的边缘量 . 但是当我想在互联网上检查我的实现是否正确时，我发现很多实现都是这样的： int Tree::Depth() { if (!this) { return 0; } return max(this->left.Depth(), ... -
1 votesanswersviews
什么应该是二叉搜索树节点的结构
我正在尝试为二进制搜索树制作c程序，其中包含以下功能（实际上这是我大学作业的一部分）： A）创建二进制搜索树 . B）顺序，预订，后序遍历 . （非递归） C）在树中搜索Val . D）广度优先遍历 . E）深度优先遍历 F）计数叶节点，非叶节点 . G）数量没有 . 水平 我的疑问是： - 1. 通常树节点具有以下结构： class node{ private: node *lChi... -
0 votesanswersviews
广度优先或深度优先搜索在特定深度寻找儿童？
我知道这里有很多关于广度优先搜索和深度优先搜索的问题，但我认为我的情况有点不同 . 我有一个有根的树，其中每个节点可能有0,1或2个子节点（预期数量为1） . 给定一个大数 n ，我想找到一条长度为 n 的树的路径 . 很明显，深度优先应该是最好的方法，但我不太确定 . 树的宽度非常小，这通常是使用广度优先搜索的原因 . 另外，如果我使用深度优先搜索，那么我最终可能会进入一个高度非常接近 n 但小... -
1 votesanswersviews
二叉搜索树是二进制最大堆的特例吗？
据我所知，在max-heap中，每个节点的值大于或等于它的所有子节点 . 这同样适用于二叉搜索树，但在此数据结构中，同一级别（兄弟）上的节点正确构造也很重要 . 这让我觉得二叉搜索树基本上是一个带有额外属性的最大堆 . 所以每个BST也是最大堆 . 我对吗？ -
5 votesanswersviews
检查二叉树是否也是二叉搜索树的问题
我正试图解决这个问题，但我遇到了一些麻烦： 在二叉搜索树（BST）中：节点左子树中每个节点的数据值小于该节点的数据值 . 节点右子树中每个节点的数据值大于该节点的数据值 . 给定根节点：class Node {int数据;节点离开;节点权;}确定二叉树是否也是二叉搜索树 我有这个代码： boolean check(Node root) { //node doesn't have... -
1 votesanswersviews
结合二进制搜索树
我遇到问题的问题如下 . 假设您有两个不同的二叉搜索树A和B，并且您以某种方式知道A中的最大元素小于B中的最小元素 . 假设高度（A）<height（B） . 提供一种破坏性地创建二进制搜索树的算法，该搜索树将包含A∪B中的所有元素并且在时间O（高度（A））中运行 . 因此，由于A中的最大元素小于B中的最小元素，这意味着A中的每个元素都小于B中的每个元素 . 在新树中，左侧应为树A，右侧... -
1 votesanswersviews
BST来自预购，只需按相同顺序插入节点即可
要从给定的前序遍历构造BST，如果我尝试按照预先给定的顺序插入BST，我会获得BST . 那么，我们不是通过对元素进行排序或执行任何其他算法来创建有序的？ 有没有一个例子表明只是插入元素就无法构建树？ -
0 votesanswersviews
删除BST中的多个节点会更改生成的树？
如果我需要删除BST中的多个节点，结果树是否会改变删除顺序？正常的左右顺序将被保留，但我不确定树结构 . 这是一个“phisolophical”问题，我需要对它进行调整或反例 . -
3 votesanswersviews
查找树是否是二叉搜索树
这种方法是否错误，以确定树是否是BST？节点的左子树仅包含键小于节点键的节点 . 节点的右子树仅包含键大于节点键的节点 . 左右子树也必须是二叉搜索树 . 我的代码是： isBST(struct node* node) { if (node == NULL) return 1; if (node->left != NULL && node->le... -
3 votesanswersviews
最大的子树，它是二叉搜索树（BST）
给定一个二叉树，我想找出其中最大的子树BST . 这个问题与Finding the largest subtree in a BST重复，其中1337c0d3r通过遍历树向下提供O（n）解决方案 . 有两行代码令我困惑 . 任何人都可以帮我解释一下吗？ // Find the largest BST subtree in a binary tree. // If the subtree is ... -
1 votesanswersviews
从二叉搜索树中删除节点
我理解删除具有两个子树的节点时的想法：I "erase"节点's value and replace it with either its predecessor from the left subtree' s值或右子树值的后继值，然后删除该节点 . 但是，如果我选择右子树的后继者或左子树的前任，这是否重要？或者只要在执行删除后仍然有二进制搜索树，它是否有效？ -
1 votesanswersviews
二叉树的双线程树
我需要从常规二叉树构建双线程树，如果可能的话使用递归 . 这是我们使用的定义：二叉树的线程树是通过将每个空左子项设置为inorder遍历中的节点的前任，并将每个null右子项设置为inorder遍历中的节点的后继来获得的 . 我找不到解决方案，这里有几个类似于这个但没有解决方案的帖子 . 我只需要算法，它可以是任何语言 这是构造函数，第二个是我需要做的： public ThreadedNode(T... -
6 votesanswersviews
如何检查BST是否有效？
How can I check if a BST is a valid one, given its definition and using a generalized version of fold for BST? data(Ord a, Show a, Read a) => BST a = Void | Node { val :: a, left, right ::... -
6 votesanswersviews
在BST中查找交换的节点
我正在尝试编写一个程序，可以检测并打印BST中已交换的两个节点 . 在三层树中，我使用这种方法接近解决方案 . If (!AllSubTreeAreValid()) { //Nodes swapped on same side of main root node } else { int max = getMax(root->left); int min = getMin(root-... -
1 votesanswersviews
BST与重复（RABPAB）
我想为字符串“RABSAB”创建一个BST . 插入树的规则是： 1）节点的左子树<节点的密钥 .2）节点的右子树> =节点的密钥 . 我最终得到了两个答案： R R / \ / \ A S A S \ ...