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
Vous devez vous connecter pour publier un commentaire.
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:
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 demalloc
, 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 commeinsertNode(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 demalloc
en C).OriginalL'auteur Matt Eckert
En haut, vous déclarez
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.OriginalL'auteur Victor Sand
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 localen
être réglé à la valeur qui est stockée dansrootNode
(dans ce cas, la valeur NULL). Les modifications apportées àn
dans leinsertNode()
fonction ne change pasrootNode
.Pour corriger le code que vous pourriez changer la
insertNode
etdeleteNode
fonctions d'accepter un pointeur vers le nœud racine de pointeur. Par exemple, leinsertCode()
fonction devient:Vous devez également avoir à modifier le code pour appeler
insertNode()
avec une référence à rootNodeinsertNode(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
Et utiliser la Fonction d'Insertion comme
Antérieure aux modifications de rester dans la fonction Insérer uniquement. Utilisez le double pointeur à l'intérieur.
OriginalL'auteur dead programmer