- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
我正在开发一个 C 程序,该程序可以按以下格式扫描学生记录并将其存储到二叉搜索树中。对于我定义的 BST:
struct student
int id
char firstname[20]
char lastname[20]
float score
char zipcode[10]
struct node
struct student data
struct node* leftChild
struct node* rightChild
程序的功能之一应该能够从树中删除记录。该程序询问用户将被删除的学生的姓氏。
下面是遍历BST找到要删除的目标姓氏的方法:
void traverse(node* root, student data)
if(root != NULL)
traverse(root->leftChild,data)
if(strcmp(root->data.lastname,data.lastname) == 0)
root = delete(root,data)
traverse(root->rightChild,data)
传递给遍历函数的示例学生结构是:
struct student John
int id = 1000
char firstname = John
char lastname = Adams
float score = 90.00
char zipcode = 92121
我与 findmin 一起使用的删除函数是因为我知道我需要找到根(目标节点)的右子树中的最小值,以便用它替换目标节点:
struct node* findmin(struct node* root)
while(root->leftChild != NULL)
root = root->leftChild
return root
struct node* delete(node* root, student data)
if(root == NULL) // check if empty tree
return root
// traverse towards left if ID is less
else if(data.iD < root->data.iD)
root->leftChild = delete(root->leftChild,data)
// towards right if greater than ID
else if(data.iD > root->data.iD)
root->rightChild = delete(root->rightChild,data)
/* else would mean target last name found */
else
/* if found node has no child */
if(root->leftChild == NULL && root->rightChild == NULL)
free(root)
root = NULL
// 1 child
else if(root->leftChild == NULL) // if left child is NULL
struct node* temp = root
root = root->rightChild
free(temp)
temp = NULL
else if(root->rightChild == NULL) // if right child is NULL
struct node* temp = root
root = root->leftChild
free(temp)
temp = NULL
// 2 children
else
struct node* temp = findmin(root->rightChild)
root->data = temp->data
root->rightChild = delete(root->rightChild,temp->data)
return root;
我期望这里发生的是 student John
将与 BST 的全局根一起传递到 traverse 中,并且在打印 BST 时,student John
将被删除并且不再存在。但是,当我传递包含目标姓氏的学生时,该名称仍将存在于树中。此外,当我测试我的代码并传递要删除的记录时,程序有时不会删除目标节点,而是删除具有最大学生 ID 的节点(树中最右边的节点)和/或会用分段来迎接我错误 11. 代码中是否存在我没有看到的缺陷?如果您需要我提供任何进一步的信息来帮助您,请告诉我。
最佳答案
遍历函数存在第一个问题。当你删除一个节点时,你需要更新指向它的指针。你不跟踪它。
下面是使用指向节点指针策略的遍历和删除函数。正如您所看到的,代码变得更简单。
在此代码中,pRoot
是指向根指针的指针。然后您可以更新它的值。您可以将其设置为NULL或由于删除而设置为另一个节点。
void traverse(node** pRoot, student data){
if(*pRoot != NULL) {
traverse(&((*pRoot)->leftChild),data);
if(strcmp((*pRoot)->data.lastname,data.lastname) == 0)
delete(pRoot,data);
traverse(&((*pRoot)->rightChild),data);
}
void delete(node* pRoot, student data)
if(*pRoot == NULL)
return;
node *temp = *pRoot;
if((*pRoot)->leftChild == NULL)
*pRoot = (*pRoot)->rightChild;
else if((*pRoot)->rightChild == NULL){
*pRoot = (*pRoot)->leftChild;
else {
// both children are not NULL :
// we replace *pRoot with the node with
// min ID detached from the rightChild.
// find node with min ID in right child
node **pNode = &((*pRoot)->rightChild);
while((*pNode)->leftChild != NULL)
pNode = &((*pNode)->leftChild);
// *pNode is the node with minID
// its left child is NULL,
// but its right child may not be NULL
// we detach the node with min ID
node *nNode = *pNode;
*pNode = nNode->rightChild;
//replace *pRoot with *nNode
nNode->rightChild = (*pRoot)->rightChild;
nNode->leftChild = (*pRoot)->leftChild;
*pRoot = nNode;
}
free(temp);
}
将上面的遍历和删除函数合并为一个函数,得到
void delete(node** pRoot, student *data){
if(*pRoot == NULL)
return;
delete(&((*pRoot)->leftChild), data);
detele(&((*pRoot)->rightChild), data);
if(strcmp((*pRoot)->data.lastname,data->lastname) != 0)
return;
// we delete *pRoot
node *temp = *pRoot;
if((*pRoot)->leftChild == NULL)
*pRoot = (*pRoot)->rightChild;
else if((*pRoot)->rightChild == NULL){
*pRoot = (*pRoot)->leftChild;
else {
// both children are not NULL :
// we replace *pRoot with the node with
// min ID detached from the rightChild.
// find node with min ID in right child
node **pNode = &((*pRoot)->rightChild);
while((*pNode)->leftChild != NULL)
pNode = &((*pNode)->leftChild);
// *pNode is the node with minID
// its left child is NULL,
// but its right child may not be NULL
// we detach the node with min ID
node *nNode = *pNode;
*pNode = nNode->rightChild;
//replace *pRoot with *nNode
nNode->rightChild = (*pRoot)->rightChild;
nNode->leftChild = (*pRoot)->leftChild;
*pRoot = nNode;
}
free(temp);
}
关于c - 从二叉搜索树中删除具有 2 个子节点的节点,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59168372/
过去两天我遇到了一个奇怪的问题,但我还无法解决它。我正在尝试从 2 个文本文件中获取单词并将这些单词添加到树中。我选择的获取单词的方法引用这里: Splitting a text file into
例如,像这样的树: 5 / \ 3 6 / \ 7 2 print(tree.branchLenSum()) 将是1+1+2+2=6 树类: class BinaryTre
我正在学习 JavaScript。我是文档对象模型 (DOM) 主题的新手。 我对节点在 DOM 树中的布局方式感到困惑? 我使用了这个 HTML 文件。 List Buy groceries
这个问题不太可能对任何 future 的访客有帮助;它只与一个较小的地理区域、一个特定的时间点或一个非常狭窄的情况相关,通常不适用于全世界的互联网受众。如需帮助使此问题更广泛适用,visit the
var nodeEnter = node.enter().append("g") .attr("class", "node") .attr("transform", function (d) {
我正在使用数据表来表示我的应用程序中的数据。我有一个功能,可以在单击克隆图标时克隆任何行并动态添加它下面的行。 数据表具有搜索功能,可以搜索表中存在的所有行,但是它只考虑初始页面加载时加载到表中的行。
我已经用 Python 编写了一个 Tree 类,但是我在为它创建迭代器时遇到了问题我希望能够做到 phonebook = MyTree() # Build up tree for node in p
我需要为 FreeBSD 检查这个 libunwind 端口, http://people.freebsd.org/~kib/git/libunwind.git/ 我以前和当我尝试使用命令 check
我已经实现了自己的 AVL 树,并将其用作字典。我想知道,计算以某个字符串开头的所有单词的最快方法是什么。 例如: string prefix = "fa"; output: 4 我已经在 O(n)
我目前正在尝试编写一个使用 2-3-4 树的程序,但我遇到了插入函数的问题。这是相关代码.. int main () { tree234 myTree; myTree.insert("
我的同事问了我这个问题,但我无法想出任何最佳解决方案。 给定一棵具有n 个节点、n-1 条边和 q 个查询的无向加权树。 每个查询都有输入 u v k ,输出位于路径 u to v 的奇数且小于 k
如果我有一个 app.html 模板如下: ${message} test 使用 MyComponent.ts : export class MyComponent { my
我继承了一个 git 存储库,其中树中的提交条目为空 sha1,阻止 FishEye 为存储库编制索引。 $ git fsck Checking object directoriies: 100%(2
这是一个例子。我也许可以在点击函数中弄清楚它,但我不确定从点击函数外部从根开始检查所有子项的最佳方法。谢谢 .node circle { fill: #fff; stroke: stee
我正在使用 Python 批量编辑许多当前看起来像这样的 musicXML 文件: ... -5 -9
假设有一个 8 阶 B 树。这意味着它可以有 8 个指针和 7 个元素。假设字母 A 到 G 存储在这棵 B 树中。所以这棵 B 树只是一个包含 7 个元素的节点。 然后你尝试将 J 插入到树中。没有
很难说出这里问的是什么。这个问题是含糊的、模糊的、不完整的、过于宽泛的或修辞性的,无法以目前的形式得到合理的回答。如需帮助澄清此问题以便重新打开它,visit the help center 。 已关
我正在尝试做一个简单的二维“物理”模拟,主要涉及圆形物体的碰撞,为了避免编程我自己的空间索引(四叉树/r-tree/等),我希望使用 Boost 的 R -树。 问题是我在 Boost 文档中找不到任
我正在从 python 字典中读取数据并尝试在下面的树中添加更多书籍元素。下面只是一个示例,我需要复制一个元素及其子元素但替换内容,在这种情况下我需要复制 book 元素但替换标题和作者。
假设我有一个变量,它包含一个 nltk 树类的树。是否有类似 parent() 或返回节点父节点的函数? 最佳答案 您需要一种不同的数据结构:一棵树,其节点包含指向其父节点的指针。 NLTK 现在提供
我是一名优秀的程序员,十分优秀!