Ciao a tutti, sto risolvendo il problema della rimozione di un nodo da un albero.
L'esercizio non è ancora completo,ma ho un problema sulla rimozione sul nodo foglia nella funzione deleteNode dove la funzione free non mi libera la memoria.
Faccio un esempio, se inserisco il valore 49 che coincide con una foglia non lo elimina dalla memoria.
Cosa può essere?
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef struct treeNode {
struct treeNode *leftPtr, *rightPtr;
int data;
} TreeNode;
typedef TreeNode *TreeNodePtr;
void insertNode(TreeNodePtr *, int);
void inOrder(TreeNodePtr);
void preOrder(TreeNodePtr);
void postOrder(TreeNodePtr);
int depth(TreeNodePtr);
void deleteNode(TreeNodePtr , int);
void *scrollRight(TreeNodePtr);
void *binaryTreeSearch(TreeNodePtr, int);
int main() {
int i, item[20] = {14,71,29,74,33,92,82,76,35,99,55,84,78,13,68,20,27,8,2,49} , item1;
TreeNodePtr rootPtr = NULL;
srand(time(NULL));
for (i = 0; i < 20;i++) {
item1 = item[i];
insertNode(&rootPtr, item1);
}
printf("\nStampa preOrder:\n");
preOrder(rootPtr);
printf("\n\nStampa inOrder:\n");
inOrder(rootPtr);
printf("\n\nStampa postOrder:\n");
postOrder(rootPtr);
printf("\n\nL'albero è composto da %d livelli\n", depth(rootPtr));
printf("\nChe valore vuoi eliminare? ");
scanf("%d", &item1);
deleteNode(rootPtr, item1);
printf("\nStampa preOrder:\n");
preOrder(rootPtr);
printf("\n\nStampa inOrder:\n");
inOrder(rootPtr);
printf("\n\nStampa postOrder:\n");
postOrder(rootPtr);
printf("\n\nL'albero è composto da %d livelli\n", depth(rootPtr));
return 0;
}
void insertNode(TreeNodePtr *treePtr, int value) {
if(*treePtr == NULL) {
*treePtr = malloc(sizeof(TreeNode));
if(*treePtr != NULL) {
(*treePtr)->data = value;
(*treePtr)->leftPtr = NULL;
(*treePtr)->rightPtr = NULL;
}
}
else {
if(value < (*treePtr)->data)
insertNode(&(*treePtr)->leftPtr, value);
else if (value > (*treePtr)->data)
insertNode(&(*treePtr)->rightPtr, value);
else {
printf("DUP ");
}
}
}
void inOrder(TreeNodePtr treePtr) {
if(treePtr != NULL) {
inOrder(treePtr->leftPtr);
printf("%3d", treePtr->data);
inOrder(treePtr->rightPtr);
}
}
void preOrder(TreeNodePtr treePtr) {
if(treePtr != NULL) {
printf("%3d", treePtr->data);
preOrder(treePtr->leftPtr);
preOrder(treePtr->rightPtr);
}
}
void postOrder(TreeNodePtr treePtr) {
if(treePtr != NULL) {
postOrder(treePtr->leftPtr);
postOrder(treePtr->rightPtr);
printf("%3d", treePtr->data);
}
}
int depth(TreeNodePtr treePtr) {
int s, d;
if(treePtr == NULL)
return -1; //nodo radice parte da 0
s = depth(treePtr->leftPtr);
d = depth(treePtr->rightPtr);
if(s > d)
return ++s;
else
return ++d;
}
void deleteNode(TreeNodePtr treePtr, int value) {
TreeNodePtr temp;
if((temp = binaryTreeSearch(treePtr, value))) {
printf("Valore trovato\n");
if(temp->leftPtr == NULL && temp->rightPtr == NULL) {
free(temp); //funzionamento anomalo
}
}
else printf("Valore non trovato\n");
}
void *binaryTreeSearch(TreeNodePtr treePtr, int value) {
if(treePtr != NULL) {
if(value < treePtr->data)
return binaryTreeSearch(treePtr->leftPtr, value);
else if (value > treePtr->data)
return binaryTreeSearch(treePtr->rightPtr, value);
else
return treePtr;
}
return NULL;
}
void *scrollRight(TreeNodePtr treePtr) {
while(treePtr->rightPtr != NULL)
treePtr = treePtr->rightPtr;
return treePtr;
}