Binary Recherche Arbre en C
-
22-09-2019 - |
Question
Je suis un gars de Python. Apprendre le langage C et j'ai essayé de mettre en œuvre Binary Search Arbre en C. Je notais le code, et je l'ai essayé de quelques heures, mais, pas en mesure d'obtenir la sortie comme prévu. S'il vous plaît aider!
S'il vous plaît me corriger.
#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);
}
La solution
Le problème réside dans l'insertion. Si node
est NULL
vous créez un nouveau nœud et le retourner. Mais si le nœud n'est pas NULL
. Vous apportez des modifications à corriger la sous-arborescence droite / gauche mais vous n'êtes rien retournerez.
Modifier
if(X < node->element){
node->left = insertElement(node->left, X);
}
else if(X > node->element){
node->right = insertElement(node->right, X);
}
à:
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.
}
Autres conseils
Votre insertElement
ne retourne pas toujours une valeur. Ceci est la raison pour laquelle vos appels récursifs vont mal. Dites à votre compilateur pour vous avertir des erreurs comme ça (par exemple, sur gcc, utilisez -Wall
).
displayTree
a une erreur semblable, de ne rien renvoyer quand il est spécifié pour renvoyer un TreeNode*
.
main
devrait aussi retourner une valeur (ou vous devez déclarer void
).