Binary Search Tree in C
-
22-09-2019 - |
Domanda
Sono un ragazzo Python. L'apprendimento delle lingue C e ho cercato di implementare Binary Search Tree in C. Io ho scritto il codice, e ho cercato di poche ore, ma, non in grado di ottenere l'output come previsto. Si prega di aiutare!
Si prega di correggere me.
#include<stdlib.h>
#include<stdio.h>
typedef int ElementType;
typedef struct TreeNode {
ElementType element;
struct TreeNode *left, *right;
} TreeNode;
TreeNode *createTree(){
//Create the root of tree
TreeNode *tempNode;
tempNode = malloc(sizeof(TreeNode));
tempNode->element = 0;
tempNode->left = NULL;
tempNode->right = NULL;
return tempNode;
}
TreeNode *createNode(ElementType X){
//Create a new leaf node and return the pointer
TreeNode *tempNode;
tempNode = malloc(sizeof(TreeNode));
tempNode->element = X;
tempNode->left = NULL;
tempNode->right = NULL;
return tempNode;
}
TreeNode *insertElement(TreeNode *node, ElementType X){
//insert element to Tree
if(node==NULL){
return createNode(X);
}
else{
if(X < node->element){
node->left = insertElement(node->left, X);
}
else if(X > node->element){
node->right = insertElement(node->right, X);
}
else if(X == node->element){
printf("Oops! the element is already present in the tree.");
}
}
}
TreeNode *displayTree(TreeNode *node){
//display the full tree
if(node==NULL){
return;
}
displayTree(node->left);
printf("| %d ", node->element);
displayTree(node->right);
}
main(){
//pointer to root of tree #2
TreeNode *TreePtr;
TreeNode *TreeRoot;
TreeNode *TreeChild;
//Create the root of tree
TreePtr = createTree();
TreeRoot = TreePtr;
TreeRoot->element = 32;
printf("%d\n",TreeRoot->element);
insertElement(TreeRoot, 8);
TreeChild = TreeRoot->left;
printf("%d\n",TreeChild->element);
insertElement(TreeRoot, 2);
insertElement(TreeRoot, 7);
insertElement(TreeRoot, 42);
insertElement(TreeRoot, 28);
insertElement(TreeRoot, 1);
insertElement(TreeRoot, 4);
insertElement(TreeRoot, 5);
// the output is not as expected :(
displayTree(TreeRoot);
}
Soluzione
Il problema è nell'inserimento. Se node
è NULL
si crea un nuovo nodo e restituirlo. Ma cosa succede se il nodo non è NULL
. Si stanno facendo corrette modifiche alla destra / sinistra sotto-albero, ma non si restituisce nulla.
Cambia
if(X < node->element){
node->left = insertElement(node->left, X);
}
else if(X > node->element){
node->right = insertElement(node->right, X);
}
a:
if(X < node->element){
node->left = insertElement(node->left, X);
return node; // add this.
}
else if(X > node->element){
node->right = insertElement(node->right, X);
return node; // add this.
}
Altri suggerimenti
Il tuo insertElement
non restituisce sempre un valore. Questo è il motivo per cui le chiamate ricorsive vanno male. Informi il compilatore di mettere in guardia circa gli errori del genere (per esempio, il GCC, usare -Wall
).
displayTree
ha un errore simile, restituendo niente quando si è specificato per restituire un TreeNode*
.
main
dovrebbe anche restituire un valore (o si dovrebbe dichiararla void
).