Un Arbre de Recherche binaire C mise en œuvre

J'ai récemment écrit un assez simple morceau de code de tenter de mettre en œuvre un Arbre de Recherche Binaire en C avec de l'insertion, de recherche, de suppression et de fonctionnement de l'écran. Malheureusement, le code ne semble pas fonctionner.

#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int data;
struct TreeNode *leftChildNode;
struct TreeNode *rightChildNode;
};
typedef struct TreeNode node;
node *rootNode = NULL;
void insertNode(int i, node *n) {
if(n == NULL) {
n = (node*)malloc(sizeof(node));
n->leftChildNode = NULL;
n->rightChildNode = NULL;
n->data = i;
}
else 
if(n->data == i)
printf("\nThis value already exists in the tree!");
else
if(i > n->data)
insertNode(i, n->rightChildNode);
else
insertNode(i, n->leftChildNode);
}
void searchNode(int i, node *n) {
if(n == NULL)
printf("\nValue does not exist in tree!");
else
if(n->data == i)
printf("\nValue found!");
else
if(i > n->data)
searchNode(i, n->rightChildNode);
else
searchNode(i, n->leftChildNode);
}
void deleteNode(int i, node *n) {
if(n == NULL)
printf("\nValue does not exist in tree!");
else
if(n->data == i) {
if(n->leftChildNode == NULL)
n = n->rightChildNode;
else
if(n->rightChildNode == NULL)
n = n->leftChildNode;
else {
node *temp = n->rightChildNode;
while(temp->leftChildNode != NULL)
temp = temp->leftChildNode;
n = temp;
}
}
else
if(i > n->data)
deleteNode(i, n->rightChildNode);
else
deleteNode(i, n->leftChildNode);
}
void displayPreOrder(node *n) {
if(n != NULL) {
printf("%d ", n->data);
displayPreOrder(n->leftChildNode);
displayPreOrder(n->rightChildNode);
}
}
void displayPostOrder(node *n) {
if(n != NULL) {
displayPostOrder(n->leftChildNode);
displayPostOrder(n->rightChildNode);
printf("%d ", n->data);
}
}
void displayInOrder(node *n) {
if(n != NULL) {
displayInOrder(n->leftChildNode);
printf("%d ", n->data);
displayInOrder(n->rightChildNode);
}
}
int main(void) {
int ch, num, num1;
do {
printf("\nSelect a choice from the menu below.");
printf("\n1. Insert a node.");
printf("\n2. Search for a node.");
printf("\n3. Delete a node.");
printf("\n4. Display the Binary Search Tree.");
printf("\nChoice: ");
scanf("%d", &ch);
switch(ch) {
case 1: printf("\nEnter an element: ");
scanf("%d", &num);
//printf("YESYES");
insertNode(num, rootNode);
break;
case 2: printf("\nEnter the element to be searched for: ");
scanf("%d", &num);
searchNode(num, rootNode);
break;
case 3: printf("\nEnter the element to be deleted: ");
scanf("%d", &num);
deleteNode(num, rootNode);
break;
case 4: printf("\nSelect an order for the elements to be display in.");
printf("\n1. Pre-order.");
printf("\n2. Post-order.");
printf("\n3. In-order.");
printf("\nChoice: ");
scanf("%d", &num1);
switch(num1) {
case 1: printf("\nPre-order Display: ");
displayPreOrder(rootNode);
break;
case 2: printf("\nPost-order Display: ");
displayPostOrder(rootNode);
break;
case 3: printf("\nIn-order Display: ");
displayInOrder(rootNode);
break;
default: exit(0);
}
break;
default: exit(0);
}
//printf("%d", rootNode->data);
printf("\nIf you want to return to the menu, press 1.");
printf("\nChoice: ");
scanf("%d", &num);
} while(num == 1);
return 0;
}

En fait, de l'avis de la ligne commentée printf("%d", rootNode->data); juste avant la do-while bloc dans main() se termine. Si je décommentez cette ligne, compiler le programme et l'exécuter, le programme génère une erreur de segmentation. Quelqu'un pourrait-il me dire pourquoi cette erreur se produit et pourquoi le code n'est pas en cours d'exécution? Merci à l'avance.

OriginalL'auteur Pastafarian | 2013-05-09

binary-search-tree c

5

Vous ont une idée fausse au sujet de la façon dont C traite les arguments. En C, tous les arguments sont passés par valeur, y compris les pointeurs. Lorsque vous réaffectez un pointeur à l'intérieur d'une fonction que vous réaffectez une copie de ce pointeur.

Par exemple:
```
void f ( int *p );
int *p;
f(p);
```
L'adresse (&p) du pointeur est différent dans la fonction. Ils pointent vers le même emplacement (ont la même valeur), mais chacun a une adresse différente. Lorsque vous affectez le pointeur de la valeur de retour de malloc, c'est uniquement affectation de la fonction de copie locale de ce pointeur.

Un moyen de résoudre ce problème est d'introduire un autre niveau d'indirection, et de transmettre l'adresse du pointeur: void insertNode(int i, node **n), que vous pouvez appeler comme insertNode(0, &n). Lorsque vous voulez le changer pour quelque chose d'autre, de déréférencer une fois et puis attribuer: *p = malloc(sizeof(node)).

Une autre solution est d'avoir le retour de la fonction le pointeur et l'assigner dans le code appelant: return malloc(sizeof(node)). (Remarque: Vous auriez fait le retourner après le code d'initialisation... aussi, ne lancez pas la valeur de retour de malloc en C).

OriginalL'auteur Matt Eckert
1

En haut, vous déclarez
```
node *rootNode = NULL; 
```
Si vous ne courez pas insertNode (avec succès - Voir Matt réponse), le nœud sera toujours NULL lors de l'impression, et c'est pourquoi vous obtenez l'erreur de segmentation.

Pourquoi le downvote? Je me rends compte que ce n'est pas la réponse complète, mais l'OP n'a de demander également pourquoi son code de segmentation lors de l'impression.

OriginalL'auteur Victor Sand
1

La raison pour laquelle le code de segmentation lorsque vous supprimez l'instruction printf est parce que rootNode est un pointeur NULL. Un déréférencement de ce pointeur NULL dans l'appel de fonction provoque l'erreur de segmentation.

La raison que rootNode est un pointeur NULL est qu'il n'est jamais modifiée par le code. L'appel de insertNode() résultats dans la variable locale n être réglé à la valeur qui est stockée dans rootNode (dans ce cas, la valeur NULL). Les modifications apportées à n dans le insertNode() fonction ne change pas rootNode.

Pour corriger le code que vous pourriez changer la insertNode et deleteNode fonctions d'accepter un pointeur vers le nœud racine de pointeur. Par exemple, le insertCode() fonction devient:
```
void insertNode(int i, node **n) {
if(*n == NULL) {
(*n) = (node*)malloc(sizeof(node));
(*n)->leftChildNode = NULL;
(*n)->rightChildNode = NULL;
(*n)->data = i;
}
else
{
if((*n)->data == i)
{
printf("\nThis value already exists in the tree!");
}
else
{
if(i > (*n)->data)
insertNode(i, &(*n)->rightChildNode);
else
insertNode(i, &(*n)->leftChildNode);
}
}
}
```
Vous devez également avoir à modifier le code pour appeler insertNode() avec une référence à rootNode insertNode(num, &rootNode);

Je vous recommandons de vérifier les valeurs de retour des différents scanf appels. Si scanf("%d",x) retourne 0 alors la valeur ne peut être converti en int et le contenu de x ne sont pas définis. Idéalement, le code serait en mesure de gérer ce cas gracieusement.

OriginalL'auteur Joe

Je pense que le probblem est avec la signature pour Insérer une fonction d'Essayer le code ci-dessous et qu'Il fonctionnera

void insertNode(int i, node **n) {
if(*n == NULL) {
*n = (node*)malloc(sizeof(node));
(*n)->leftChildNode = NULL;
(*n)->rightChildNode = NULL;
(*n)->data = i;
}
else 
if((*n)->data == i)
printf("\nThis value already exists in the tree!");
else
if(i > (*n)->data)
insertNode(i, &((*n)->rightChildNode));
else
insertNode(i, &((*n)->leftChildNode));
}

Et utiliser la Fonction d'Insertion comme

insertNode(num, &rootNode);

Antérieure aux modifications de rester dans la fonction Insérer uniquement. Utilisez le double pointeur à l'intérieur.

OriginalL'auteur dead programmer

Vous devez vous connecter pour publier un commentaire.