L'arbre de recherche binaire ne reconnaît pas correctement les valeurs

Question

J'essaie d'implémenter un arbre Serach binaire en utilisant C. Ici, dans ce code, j'ai ajouté quelques valeurs à l'arbre, puis j'ai essayé de vérifier si ces valeurs étaient dans l'arbre. Mais ma tentative de code retourne toujours vrai.

J'ai vérifié plusieurs fois. J'apprends encore la programmation en C.

Voici mon code.

#include <stdio.h> 
#include <stdlib.h> 
#include <stdbool.h> 
typedef struct BSTnode { 
    int data; 
    struct BSTnode *left; 
    struct BSTnode *right; 
    } BSTnode; 

BSTnode *getNewNode(int data){ 
    BSTnode *newNode = (BSTnode*)malloc(sizeof(BSTnode)); 
    newNode->data=data; 
    newNode->left=newNode->right=NULL; 
    } 
BSTnode* InsertNew(BSTnode *root,int data){ 
    if(root == NULL){ 
     root = getNewNode(data); 
       } 
     else if(data <= root->data){ 
      root->left = InsertNew(root->left,data); 
      } else{ 
       root->right = InsertNew(root->right,data); 
       } 
     return root; 
     } 

bool search(BSTnode *root, int data){ 
    if(root== NULL) return false; 
    else if(root->data == data) return true; 
    else if (data <= root->data) return search(root->left,data); 
    else return search(root->right,data); 

    } 
int main() 
{ 
//node to store root 

BSTnode *root = NULL; 

root = InsertNew(root,34); 
root = InsertNew(root,4); 
root = InsertNew(root,3); 
root = InsertNew(root,1); 

int num; 
printf("enter a number : \n"); 
num =scanf("%d"); 

if(search(root,num)==true){ 
    printf("found"); 
    }else{ 
    printf("not found"); 
    } 
    return 0; 
} 

Que manque-t-il ici?

Merci d'avance.

Answer 1

Il vous manque que

num =scanf("%d"); 

ne fait pas ce que vous pensez qu'elle (scanf retourne le nombre d'éléments converti avec succès ou -1 sur EOF). Vous ne l'avez pas manivelle suffisamment votre niveau d'avertissement du compilateur élevé pour vous dire que vous avez besoin

if (scanf ("%d", &num) != 1) { 
    /* complain */ 
} 

Dans votre programme cassé, scanf() arrive à retourner 1 (car il convertit 1 point et écrit à la mémoire aléatoire) et puisqu'il y a un 1 dans l'arbre, vous obtenez toujours vrai.

Answer 2

En plus de l'erreur signalée par @Jens, vous ne renvoyez pas une valeur de getNewNode. Ajouter une instruction:

return newNode; 

à la fin de cette fonction. Voici un fixed example on ideone

Answer 3

Pour commencer selon la norme C la fonction main sans paramètres doit être déclarée comme

int main(void) 

La fonction getNewNode

BSTnode *getNewNode(int data){ 
    BSTnode *newNode = (BSTnode*)malloc(sizeof(BSTnode)); 
    newNode->data=data; 
    newNode->left=newNode->right=NULL; 
    } 

a un comportement non défini, car il ne retourne rien a bien le type de retour BSTnode *.

La fonction peut être définie comme

BSTnode * getNewNode(int data) 
{ 
    BSTnode *newNode = (BSTnode *)malloc(sizeof(BSTnode)); 

    if (newNode != NULL) 
    { 
     newNode->data = data; 
     newNode->left = newNode->right = NULL; 
    } 

    return newNode; 
} 

La fonction suivante InsertNew est wrong.Take en compte que pour l'arbre de recherche binaire, il est habituellement utilisé à l'opérateur < au lieu de l'opérateur <=.

Ces déclarations

root->left = InsertNew(root->left,data); 

et

root->right = InsertNew(root->right,data); 

ne font pas de sens et les valeurs de écrasent root->left et root->right des noeuds qui ne sont pas réellement changé. Le nœud créé peut également être égal à NULL et dans ce cas, le nœud racine d'origine sera également remplacé par NULL.

Il est préférable de passer le nœud racine d'origine par référence via un pointeur.Vous devez également utiliser operator < au lieu de operator <=.

La définition de la fonction peut regarder la façon suivante

BSTnode * InsertNew(BSTnode **root,int data) 
{ 
    if (*root == NULL) 
    { 
     *root = getNewNode(data); 
     return *root; 
    } 
    else if (data < (*root)->data) 
    { 
     return InsertNew(&(*root->left), data); 
    } 
    else 
    { 
     return InsertNew(&(*root->right), data); 
    } 
} 

et la fonction peut être appelée comme

InsertNew(&root, 34); 

sans attribuer le pointeur de retour au nœud racine. La valeur de retour peut être vérifiée dans une instruction if si nécessaire.

Si vous ne voulez pas avoir des doublons dans l'arborescence, puis la fonction peut être écrit de la manière suivante

BSTnode * InsertNew(BSTnode **root,int data) 
{ 
    if (*root == NULL) 
    { 
     *root = getNewNode(data); 
     return *root; 
    } 
    else if (data < (*root)->data) 
    { 
     return InsertNew(&(*root->left), data); 
    } 
    else if ((*root)->data < data) 
    { 
     return InsertNew(&(*root->right), data); 
    } 
    else 
    { 
     return NULL; 
    } 
} 

Corrélativement la fonction search doit être définie comme

bool search(BSTnode *root, int data) 
{ 
    if (root == NULL) 
    { 
     return false; 
    } 
    else if (data < root->data) 
    { 
     return search(root->left, data); 
    } 
    else if (root->data < data) 
    { 
     return search(root->right, data); 
    } 
    else 
    { 
     return true; 
    } 
} 

L'utilisation de de la fonction scanf dans cette instruction

num =scanf("%d"); 

est faux.

L'appel correct ressemblera

printf("enter a number : "); 
scanf("%d", &num); 

Vous pouvez également vérifier si l'appel a réussi en utilisant la condition dans une instruction if

if (scanf("%d", &num) == 1) 
{ 
    //... 
} 

Et vous devez libérer toute la mémoire allouée à la arbre avant de quitter le programme.

En général, il est préférable d'utiliser la condition suivante

if(search(root,num)){ 

au lieu de la comparaison stricte avec une véritable

if(search(root,num)==true){ 

parce que si la fonction sera réécrite de telle sorte que dans le cas de succès il retournera toute valeur non nulle alors la comparaison stricte avec true ne fonctionnera pas.