我们知道有两种方法来删除节点,如果他有两个查尔兹在我的字典,如果我们采取最大值的最小值,一切都很好,当我们采取最大值的分钟,程序错过或删除一个子树的节点,我们删除。在我的代码,请。
我试着在函数中做指针的指针,没有任何变化。我试着在我们删除的节点上做指针,并从它开始做进程,仍然不工作。
#include<stdio.h>
#include<stdlib.h>
typedef struct noeud Node;
struct noeud
{
int valeur;
Node *gauche;
Node *droit;
};
Node *createNode(int val)
{
Node *newNode = malloc(sizeof(Node));
newNode->valeur = val;
newNode->gauche = NULL;
newNode->droit = NULL;
return newNode;
}
void infixe(Node *root)
{
if (root == NULL)
return;
infixe(root->gauche);
printf("%d - ",root->valeur);
infixe(root->droit);
}
Node* findMin(Node* root){
Node* current=root;
while(current->gauche!=NULL)
current=current->gauche;
return current;
}
Node* findMax(Node* root){
Node* current=root;
while(current->droit!=NULL)
current=current->droit;
return current;
}
Node* deleteInBST(Node* root,int val){
if(root==NULL) return root;
if(val<root->valeur){
root->gauche=deleteInBST(root->gauche,val);
}
else if(val>root->valeur){
root->droit=deleteInBST(root->droit,val);
}
else{
//! here of the root we wanna delete hasn't gauche child so we take the droit and we delete the root
if(root->gauche==NULL){
Node* temp=root->droit;
free(root);
return temp;
}
//! here of the root we wanna delete hasn't droit child so we take the gauche and we delete the root
else if(root->droit==NULL){
Node* temp=root->gauche;
free(root);
return temp;
}
else{
//! here if the root has two child so we have 02 ways to do it
//! the first we take the min of the maxs
/*Node* temp=findMin(root->droit);
root->valeur=temp->valeur;
root->droit=deleteInBST(root->droit,temp->valeur);
//! the second we take the max of the mins
*/
Node* temp=findMax(root->gauche);
root->valeur=temp->valeur;
root->gauche=deleteInBST(root->gauche,temp->valeur);
return root;
}
}
}
int main(){
Node* root = createNode(25);
root->gauche = createNode(10);
root->droit = createNode(60);
root->gauche->gauche = createNode(5);
root->gauche->droit = createNode(20);
root->gauche->droit->gauche = createNode(15);
root->droit->gauche = createNode(35);
root->droit->gauche->gauche = createNode(30);
root->droit->gauche->droit = createNode(45);
root->droit->gauche->droit->gauche = createNode(40);
root->droit->gauche->droit->gauche->gauche = createNode(37);
root->droit->gauche->droit->gauche->droit = createNode(43);
root->droit->droit = createNode(65);
root->droit->droit->droit = createNode(70);
printf("\n");
infixe(root);
/*//! here if we do root=deleteInBST(root,60) we lose the tree if we keep it like i wrote it we lose the sub_tree of 60 in the
// !most left */
deleteInBST(root,60);
printf("\n");
infixe(root);
return 0;
}
字符串
2条答案
按热度按时间mrfwxfqh1#
问题是递归函数并不总是执行
return
语句。特别是在尚未找到值为val
的节点的情况下,递归调用完成后并不返回根。解决方案是将最后一个
return root;
语句移出两个嵌套的else
块,以便在val
与root->valeur
不同的情况下也执行它。vmdwslir2#
在两种重要的情况下,你丢失了返回值。你应该得到一个编译器警告。
字符串