-
1 votesanswersviews
BST来自预购，只需按相同顺序插入节点即可
要从给定的前序遍历构造BST，如果我尝试按照预先给定的顺序插入BST，我会获得BST . 那么，我们不是通过对元素进行排序或执行任何其他算法来创建有序的？ 有没有一个例子表明只是插入元素就无法构建树？ -
0 votesanswersviews
删除BST中的多个节点会更改生成的树？
如果我需要删除BST中的多个节点，结果树是否会改变删除顺序？正常的左右顺序将被保留，但我不确定树结构 . 这是一个“phisolophical”问题，我需要对它进行调整或反例 . -
165 votesanswersviews
为什么std :: map实现为红黑树？
为什么 std::map 实现为red-black tree？ 那里有几个 balancer 的binary search trees（BST） . 选择红黑树的设计权衡是什么？ -
0 votesanswersviews
C fgets（）只处理最后一行
我正在尝试编写一个接收.txt文件的程序，读取所有行，然后将每个单词存储到BST中 . 然后我执行inorder遍历以按字母顺序打印单词 . 如果文本文件只包含1行，则程序可以正常工作，但如果文本文件包含多行，则会出现意外结果 . 示例：文本文件： first line second line 仅输出： line second 完全丢失文本文件的第一行 . 我的主要方法是： #define M... -
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 \ ... -
2 votesanswersviews
最小高度的BST
我正在尝试解决以下问题：“给定一个带有唯一整数元素的排序（递增顺序）数组，编写一个算法来创建一个具有最小高度的BST . ” 给定的答案将根节点作为数组的中间位置 . 虽然这样做对我来说很直观，但我试图严格证明，最好将根节点作为数组的中间位置 . 书中给出的理由是：“要创建一个最小高度的树，我们需要尽可能地将左子树中的节点数与右子树中的节点数相匹配 . 这意味着我们需要根节点是数组的中间，因为这意... -
0 votesanswersviews
具有重复键的BST数量
如果n个顶点的键不同于Catalan number给出的BST的数量 . 但是，如果某些元素重复，我们如何计算BST的数量？ 我天真的想法，如果我们在n中有k个相等的元素，那么我们应该在k上划分加泰罗尼亚数字！（k个元素的排列） . 但是如果我们在最简单的例子（BST构建在[1,1,1]上）检查它，我们就会意识到这是错误的想法 . 那么，当我们计算BST的数量时，我们应该如何考虑重复的密钥？ Wh... -
1 votesanswersviews
在不使用父指针的情况下找到后继者[重复]
这个问题在这里已有答案： In Order Successor in Binary Search Tree 16个答案 BST中元素的后继元素是由顺序遍历确定的排序顺序中元素的后继元素 . 在CLRS的算法教科书（麻省理工学院出版社的算法导论）中介绍了当每个节点都有指向其父节点的指针时找到后继者 . 在这里找到后继者的想法是 - 如果节点 x 的右子树是非空的，则 x 的后继是右子树中的最小元... -
1 votesanswersviews
如何根据BST中的后继获取节点的父节点？
在BST中，如果每个节点都没有指向其父节点的指针，则指向其后继节点（也有左右子节点指针） . 我们如何设计一个算法来根据后继指针获取其父级？ -
3 votesanswersviews
BST中节点的PreOrder后继者
我正在尝试这个问题，但无法弄清楚算法 . 我的偏好是迭代地做 . 直到现在，我已经找到了一些东西，但在某些方面还不确定 . 目前，我的算法看起来像： 首先遍历树以查找节点 遍历树时，跟踪上一个节点 . 如果找到节点，检查是否存在左子节点，那么它是后继节点 . 如果留下的孩子不在场，那么检查是否有正确的孩子，即继承孩子 . 如果节点（留给父节点）并且之前已经保存了prev节点，则... -
2 votesanswersviews
BST删除实际上并不删除
我有这个删除功能，它将BST中的节点作为参数删除它 . 它在做任何事之前检查三个案例： 如果节点没有子节点 - 那么只需删除节点 如果节点有一个子节点 - 那么只需用子节点替换该节点 如果节点有两个子节点 - 找到右侧树中的最小节点，将其替换为我们要删除的节点（实际上是删除它），然后删除我们找到的最小节点 前两个案例有效，但不是最后一个有两个孩子的案例 . 这种情况的代码如下 Ac... -
1 votesanswersviews
BST链接和案例不起作用
我有一个像这样的嵌套结构 typedef struct Node_link { struct Node_base *parent, *left, *right; }Node_link; typedef struct Node_base { struct Node_link link[2]; }Node_base; typedef struct Node{ struct... -
0 votesanswersviews
在BST中删除节点而没有指向它的父节点
我正在将这本电话簿写在安排在BST的结构上 . 它由两个结构组成： -数据结构： typedef struct note { char name[LENGHT]; char surname[LENGHT]; int tel; }data; 结构： typedef struct junction { data entry; struct junction... -
2 votesanswersviews
从C中的BST删除节点
我试图理解这个在线创建的功能，用于删除BST中的节点 . 有一些我无法理解的事情 这是代码： struct Node* Delete(struct Node *root, int data) { if (root == NULL) { return NULL; } if (data > root->data) { // data is in the left s... -
0 votesanswersviews
从二叉搜索树中删除具有2个子节点的节点
我试图在二叉搜索树中删除一个有2个孩子的节点 . 但是我在这里面临的问题很少 . 在删除带子节点的节点（带有data = 30的节点）时（left-> data = 20，right-> data = 40），我用它的inorder后继（它是data = 40的节点）替换节点，然后删除继承人 . 删除后，节点的数据被成功替换（新值为40），但是inorder后继未被正确删除/释放 . ... -
1 votesanswersviews
如何删除二进制搜索树的所有节点
我正在尝试编写一个代码来删除BST的所有节点（每个节点只有三个属性，左，右和数据，没有父指针） . 下面的代码是我提出的，它只删除树的右半部分，保持左半部分完好无损 . 如何修改它以便左半部分也被删除（这样我最终只剩下没有左或右子树的根节点）？ def delete(root): global last if root: delete(root.left) de... -
0 votesanswersviews
在反向二叉搜索树中的顺序继承
如果BST被翻转，我对inorder继承人/前任有轻微的困惑 . 当BST被翻转/反转时，我的意思是当右子树中的所有元素都较小并且左子树中的所有元素都较大时 . 通常，正确的子树具有更大的 Value . 如果它是相反的，那么inorder继承人/前任的定义是否仍然保持不变？ 对于普通树，顺序继承者将是右子树的最左边的子项不是吗？ 对于翻转的BST，如下例所示： 8 /\ 15 4... -
1 votesanswersviews
用于从二叉搜索树中删除具有给定值的节点的函数
我有一个名为TreeNode的结构，带有一个int键，左右和父 . 我试图用我的DeleteNode函数从树中删除一个节点，但它无法正常工作 . 我应该用我的DeleteNode函数中的删除节点替换左子树的最大值 . 我的移植和max函数是DeleteNode的辅助函数 . 我的问题是我不知道在我的DeleteNode函数中我应该将我所处的节点值与我通过函数传递的值进行比较 . 我在我的代码中用星... -
0 votesanswersviews
无法理解树遍历递归函数
我在理解预订，顺序和后序树遍历中涉及的递归函数时遇到了一些麻烦 . 我有一些递归的知识（但不可否认它不是我的强项） . 所有这些人似乎都称自己两次先与根的左子女打电话，然后与正确的孩子打电话 . 但这究竟是怎么可能的呢？对左子项的preOrder函数的调用不会将控制流返回到顶部，并且下一次调用永远不会执行吗？ void preOrder (Node* root) { if (root =... -
-1 votesanswersviews
二进制搜索树节点删除错误
我已经创建了我的二叉搜索树，并将指向我要删除的节点的指针放到我的 *p 中 . 删除方法应该是删除 *p 指向的节点，并且应该将 addtree 的子树添加到我的根目录 . *pBaum 是指向我的根的指针 . 但是我每次声明时都会在 addtree 上收到一条名为"conflict types"的错误消息 Baum = addtree(Baum, p->right)... -
1 votesanswersviews
二叉搜索树递归混淆
我认为这是一个愚蠢的问题但很遗憾地说它会清除我的困惑 . 如果您只是查看此代码 void printInOrder(){ printPrivateInOrder(root); } void printPrivateInOrder(Node* n){ if (root != NULL){ if (n->left != NULL){... -
37 votesanswersviews
balancer BST
Reference: 我被问到这个问题@MS SDE采访，第3轮 . 这不是一个家庭作业问题 . 我也考虑了一下，并在下面提到了我的方法 . Question: 修改BST，使其尽可能 balancer . 不用说，你应该尽可能高效地做到这一点 . Hint: 采访者说这是一个合乎逻辑的问题，如果你有不同的想法，你会得到答案 . 没有困难的编码 . 话虽如此，我认为他不指望我指向AVL /... -
2 votesanswersviews
遍历BST的元素
我有一个二叉搜索树，其节点存储在python字典中 . 这是一个例子： BST = {'node1': ['Fail', 'node3'], 'node3': ['Fail', 'Pass'], 'node2': ['Fail', 'node1'], 'node4': ['Fail', 'node2']} 在字典中，每个键都是来自BST的父级，列表（键的值）是该父级的子级，具有来自字典的对应键 ... -
1 votesanswersviews
按顺序进行BST遍历：查找
我试图找到二元搜索树的第k个最小元素，我在使用递归时遇到了问题 . 我理解如何打印顺序/后序等树，但我没有返回元素的等级 . 有人能指出我犯错的地方吗？一般来说，我很难理解树中的递归 . 编辑：这是一个练习，所以我不是在寻找使用内置函数 . 我有另一个解决方案，我在插入节点时跟踪左右儿童的数量，并且该代码工作正常 . 我想知道是否可以使用inorder遍历来执行此操作，因为它似乎是一个更简单的解决...