Binären Suchbaum C-Implementierung
Ich schrieb vor kurzem ein ziemlich einfaches Stück code, der Versuch der Umsetzung einer Binären Suchbaum in C mit einfügen, suchen, löschen und anzeigen von Operationen. Leider ist der code nicht zu funktionieren scheint.
#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;
}
In der Tat, beachten Sie die auskommentierte Zeile printf("%d", rootNode->data);
kurz vor der do-while
block in main()
endet. Wenn ich die Auskommentierung dieser Zeile kompilieren Sie das Programm und führen Sie es, das Programm wirft einen segmentation fault. Könnte mir jemand sagen, warum dieser Fehler Auftritt, und warum der code als ganzes nicht ausgeführt wird? Vielen Dank im Voraus.
InformationsquelleAutor Pastafarian | 2013-05-09
Du musst angemeldet sein, um einen Kommentar abzugeben.
Haben Sie ein Missverständnis über den Weg C Griffe Argumente. In C werden alle Argumente als Wert übergeben werden, einschließlich Zeiger. Wenn Sie zuweisen, ein Zeiger innerhalb einer Funktion, die Sie neu zuweisen, wird eine Kopie des Zeigers.
Zum Beispiel:
Die Adresse (
&p
) der Zeiger ist unterschiedlich in der Funktion. Sie beide auf der gleichen Position (haben den gleichen Wert), aber jeder hat eine andere Adresse. Bei der Zuweisung wird der pointer auf die return-Wertmalloc
, es ist nur die Zuordnung der Funktion " lokale Kopie des Zeigers.Eine Möglichkeit dieses Problem zu beheben ist die Einführung einer anderen Ebene der Dereferenzierung, und übergeben Sie die Adresse des Zeigers:
void insertNode(int i, node **n)
, die Sie nennen können, wieinsertNode(0, &n)
. Wenn Sie möchten, ändern Sie ihn auf etwas anderes, dereferenzieren Sie es einmal und dann zuordnen:*p = malloc(sizeof(node))
.Andere Lösung ist, um die Funktion den Zeiger wieder und ordnen es in den aufrufenden code:
return malloc(sizeof(node))
. (Hinweis: Sie möchte eigentlich zurück nach der Initialisierung code... auch nicht umgewandelt den Rückgabewert vonmalloc
in C).InformationsquelleAutor Matt Eckert
Oben, erklären Sie
Wenn Sie nicht laufen
insertNode
(erfolgreich - Siehe Matt ' s Antwort), wird der Knoten noch NULL sein, wenn Sie versuchen, zu drucken, und das ist, warum Sie immer die segfault.InformationsquelleAutor Victor Sand
Der Grund, warum der code segfaults, wenn Sie kommentieren Sie die printf-Anweisung ist, weil Stammknotens ist ein NULL-Zeiger. Die Dereferenzierung dieses NULL-pointer in der Aufruf der Funktion bewirkt, dass der segfault.
Dem Grund, dass Stammknotens ist ein NULL-Zeiger ist, dass es nie geändert werden, indem der code. Aufruf
insertNode()
Ergebnisse in die lokale variablen
wird der Wert, gespeichert inrootNode
(in diesem Fall NULL). Die änderungenn
iminsertNode()
Funktion nicht ändernrootNode
.Fix den code, den Sie ändern könnte, das
insertNode
unddeleteNode
Funktionen akzeptieren einen Zeiger auf den root-Knoten Zeiger. Zum Beispiel dieinsertCode()
Funktion werden würde:Würden Sie auch haben um den code zu ändern, rufen Sie
insertNode()
mit einem Verweis auf StammknotensinsertNode(num, &rootNode);
Ich auch empfehlen, dass Sie überprüfen die return-Werte der verschiedenen scanf-Aufrufe. Wenn
scanf("%d",x)
gibt 0 zurück, dann wird der Wert nicht konvertiert werden, ein int und der Inhalt von x nicht definiert sind. Im Idealfall würde der code in diesem Fall behandeln würde.InformationsquelleAutor Joe
Denke ich das probblem ist mit der Unterschrift für die Insert-Funktion, Versuchen Sie die folgenden code und Es funktioniert
- Und Insert-Funktion als
Früher die änderungen bleiben in der Funktion Einfügen, nur. Verwenden Sie doppelte Zeiger-innen.
InformationsquelleAutor dead programmer