Ric*_*ral 2 c search binary-tree insert
我有点不得不把我以前的C问题暂停,因为现在这个问题更重要了......
我已经在二叉搜索树上编写了插入和删除函数,但删除函数不完整.我需要帮助的一些事情......
1)我的插入功能是好还是可以以某种方式改进？
2)我的删除功能没有删除具有左右子节点的节点.我在过去的几个小时里搜索过很多但是找不到合适的方法.
2.a)我应该如何删除具有2个子节点的节点？
2.b)与第一个问题一样,删除功能是好还是可以改进？这个我知道它可以因为我在那些ifs中重复了很多代码,但是我不知道如何改进它,我也需要帮助.
typedef struct sClientProfile *ClientProfile;
typedef struct sClientTree *ClientTree;
typedef struct sClientProfile {
char *clientName;
int clientAge;
int clientNIF;
} nClientProfile;
typedef struct sClientTree {
ClientProfile clientProfile;
char *clientName;
ClientTree leftTree;
ClientTree rightTree;
} nClientTree;
void addClientToTree(ClientTree *cTree, ClientProfile cProfile) {
if(!*cTree) {
ClientTree new = (ClientTree)malloc(sizeof(nClientTree));
if(!new) {
perror("malloc");
}
new->clientName = strdup(cProfile->clientName);
new->clientProfile = cProfile;
new->leftTree = NULL;
new->rightTree = NULL;
*cTree = new;
} else {
if(strcmp((*cTree)->clientName, cProfile->clientName) > 0) {
addClientToTree(&(*cTree)->leftTree, cProfile);
} else {
addClientToTree(&(*cTree)->rightTree, cProfile);
}
}
}
void deleteClientFromTree(ClientTree *cTree, char *cName) {
if(!cTree) return;
int nCompare = strcmp((*cTree)->clientName, cName);
if(nCompare > 0) {
deleteClientFromTree(&(*cTree)->leftTree, cName);
} else if(nCompare < 0) {
deleteClientFromTree(&(*cTree)->rightTree, cName);
} else {
if(!(*cTree)->leftTree && !(*cTree)->rightTree) {
ClientTree cliPtr = *cTree;
free(cliPtr->clientProfile);
free(cliPtr);
cliPtr->clientProfile = NULL;
cliPtr = NULL;
*cTree = NULL;
} else if(!(*cTree)->leftTree) {
ClientTree cliPtr = *cTree;
free(cliPtr->clientProfile);
free(cliPtr);
cliPtr->clientProfile = NULL;
*cTree = (*cTree)->rightTree;
} else if(!(*cTree)->rightTree) {
ClientTree cliPtr = *cTree;
free(cliPtr->clientProfile);
free(cliPtr);
cliPtr->clientProfile = NULL;
*cTree = (*cTree)->leftTree;
} else {
// MISSING DELETE CASE
}
}
}
您可能会注意到,但我只想发表2条评论:
更新下面:
我已经完成了删除功能的迭代版本,但我不喜欢它的一些事情,也许它们可以改进(或不改进),但我看不出如何.我还试图编写它缺少的情况,删除一个有2个孩子的节点,但它不能正常工作......
我已经评论了整个代码,我认为代码可以改进,问题出在哪里.我还将这些问题命名为A,B(不再有B),C和D,以便我们可以轻松地引用它们.
bool deleteClientFromTree(ClientTree *cTree, char *cName) {
if(!cTree) return FALSE;
ClientTree currPtr = *cTree;
ClientTree prevPtr = NULL;
int nCompare;
while(currPtr) {
nCompare = strcmp(currPtr->clientName, cName);
if(nCompare > 0) {
prevPtr = currPtr;
currPtr = currPtr->leftTree;
} else if(nCompare < 0) {
prevPtr = currPtr;
currPtr = currPtr->rightTree;
} else {
/*
* A)
*
* The following cases have 3 lines in common, the free()
* calls and return statement. Is there anyway to improve
* this code and make it more compact?
*
* Of course, the printf's are to be removed...
*/
if(!prevPtr && !currPtr->leftTree && !currPtr->rightTree) {
printf("CASE #1\n");
*cTree = NULL;
free(currPtr->clientProfile);
free(currPtr);
return TRUE;
} else if(!currPtr->leftTree || !currPtr->rightTree) {
printf("CASE #2\n");
if(prevPtr->leftTree == currPtr) {
prevPtr->leftTree = currPtr->rightTree;
} else {
prevPtr->rightTree = currPtr->leftTree;
}
free(currPtr->clientProfile);
free(currPtr);
return TRUE;
} else {
printf("CASE #3\n");
ClientTree tempPtr = currPtr->rightTree;
while(tempPtr->leftTree) {
tempPtr = tempPtr->leftTree;
}
/*
* C)
*
* This has a big problem...
*
* If you take a look at the ClientProfile structure,
* in the first post, you'll see two ints
* (clientNIF/clientAge) and one char* (clientName).
*
* The problem is that the following code line is only
* copying the integer data, not the string. For some
* reason, the string remains the old one.
*
* I tried to use strdup() directly on clientName like:
* currPtr->clientProfile->clientName = strdup(tempPtr->clientProfile->clientName);
* but it still doesn't work.
*
* Why everything is being copied but the strings?
*/
currPtr->clientProfile = tempPtr->clientProfile;
/*
* D)
*
* Is there anyway to not call the function itself
* and make the while loop once again and delete the
* corresponding leaf?
*/
return deleteClientFromTree(&currPtr->rightTree, tempPtr->clientProfile->clientName);
}
}
}
return FALSE;
}
小智 5
删除节点时,必须对其子节点执行某些操作.
如果没有孩子 - 没问题.您只需删除该节点.
如果有一个孩子,也没问题; 删除节点并将其左子节点移动到其位置.
适合正确的孩子; 只需将子项移动到已删除节点的位置即可.
当您要删除具有左右子节点的节点时,会出现问题.您可以将左侧或右侧子项移动到已删除节点的位置,但是您对另一个子项及其子树又做了什么？
解决方案是这样; 找到要删除的节点的逻辑后继.通过逻辑继承者,我的意思是这个; 假设你有一个由整数组成的树,你删除了值为35的节点,逻辑后继是下一个最大的数字.雅？如果你正在进行有序行走,它将是你删除元素后的元素.
现在,有一个简单的规则来找到逻辑继承者; 你是对的(你总是有权利,因为这是你有两个孩子的情况),然后你尽可能地向左走.
你最终得到的那个元素是合乎逻辑的继承者.它比删除的元素大(你在开始时就去了,记得吗？)但它是最小的下一个最大的元素.
现在,那个元素总是只有一个或没有孩子 - 因为你尽可能地离开了,还记得吗？所以你不能再离开了 - 因为没有左 - 所以这个元素没有孩子或只有一个正确的孩子,这意味着它属于一个易于取消链接的类别(没有孩子或只有一个孩子) .因此,取消链接此元素很容易.
现在来吧很酷 - 考虑一下; 如果下一个最大元素与树中要删除的元素位于树中相同的位置,则树仍然有效且正确 - 因为每个元素左侧的所有内容都较小,右侧的所有内容都较大.
所以你做的就是这个; 您将下一个最大节点中的用户数据复制到正在删除的节点中,并删除下一个最大的节点(它没有子节点或只有正确的子节点,因此很容易取消链接和删除).
就是这样!
所以,基本上 - 找到你的逻辑继承者,取消他与树的链接,并将他的用户数据放入你实际上最初删除的元素中(当然,你不会删除它,因为它仍然是树的一部分).
| 归档时间： |
|
| 查看次数： |
16040 次 |
| 最近记录： |