c - C-搜索中的二叉搜索树如果未找到值则无法返回消息

Question

我尝试用递归制作二叉搜索树。我只写出了插入和搜索功能。但是，我的搜索功能有问题。我被困在第 39 行，如果我没有找到树中存在的值，它不会向我返回未找到该值的消息。请帮忙!

#include <stdio.h>
#include <stdlib.h>


typedef struct node { 
    int key; 
    struct node* left;
    struct node* right;
}node;

struct node* root= NULL;

int contains(node* temp, int el){

        if (el==temp->key) {
            return 1;
        }
        else if(el< temp->key) return contains(temp->left, el);
        else return contains(temp->right, el);
}

void searchPrompt(void){
    int el=-1;
    do{
        printf("   Search key or press -1 to return to menu: ");
        scanf("%d", &el);
        if(el>0){
            if (root==NULL) printf("\tError: tree is empty\n"); 
            else {
                if(contains(root, el)) printf("\tKey %d is found\n",el);
                else printf("\tKey %d is not found\n",el);
            }
        }
        else if (el<-1||el==0) printf("\tError: key not positive\n");
    }while (el!=-1);
    printf("   <Exit search method>\n\n");
}
//for search

void preOrder(node* temp){

    if (temp!=NULL){
        printf("%d ",temp->key);
        preOrder(temp->left);
        preOrder(temp->right);
    }
}

//for insertion
void insertNode(node* current, int value){        
        if(value< current->key){
            if (current->left == NULL) {
                current->left=(node*) malloc(sizeof(node));
                current->left->key = value;
                printf("\tSuccess! Value inserted: %d\n", current->left->key);

            }
            else {
                insertNode(current->left, value);
            }
        }
        else {
            if (current->right == NULL) {
                current->right=(node*) malloc(sizeof(node));
                current->right->key = value;
                printf("\tSuccess! Value inserted: %d\n", current->right->key);
            }
            else {
                insertNode(current->right, value);
            }
        }
}//end insert

void insert(int value){

    if(root==NULL){  //empty tree
        root =(node*) malloc(sizeof(node));

        root->key= value;
        printf("\tPrint root here: %d\n", value);
        root->left= NULL;
        root->right=NULL;
        printf("\tSuccess! Value inserted: %d\n", root->key);
    }
    else {
        insertNode(root, value);
    }        
        printf("\tResult: ");
        preOrder(root);
        printf("\n");
}

void insertPrompt(void){
    int value=-1;
    do{
        printf("   Insert value or press -1 to return to menu:  ");
        scanf("%d", &value);
        if(value>0)
            insert(value);
        else if (value<=0)printf("\tError: key not positive\n");
    }while (value!=-1);
    printf("   <Exit insert method>\n\n");

}

int menuPrompt(void){
    int choice=-1;
    do{
        printf("Enter <1> Search <2> Insert <3> Delete <4> Print Tree <5> Quit: ");
        scanf("%d", &choice);
        if(choice>5 || choice<1) printf("Error: invalid input! \n\n");
    }  while(choice>5 || choice<1);
    return choice;

}

int main(int argc, char *argv[]){
   int choice=-1;
   int value=-1;


    while(choice!=5){

   choice=menuPrompt();

   switch(choice){
    case 1:
         searchPrompt();
         break;
    case 2:
         insertPrompt();
         break;
    case 3:

         break;
    case 4:

         break;    
    case 5:
         printf("<Exit program> \n");
         break;
   }//end switch

}

  system("PAUSE");  
  return 0;
}

Answer 1

int contains(node* temp, int el){
        if(temp==NULL) return 0;
        if (el==temp->key) {
            return 1;
        }
        else if(el< temp->key) return contains(temp->left, el);
        else return contains(temp->right, el);
}

这既解决了问题..使您免受 UB 的困扰，也避免了在未找到 elemnt 时的错误行为。

在BLUEPIXY中提到将左右插入的新节点设置为NULL。

why is it needed you might ask ..but the thing is when you don't find an element eventually you will reach some leaf node. And then you will go to left or right and if you set it to NULL you will call contain with NULL as parameter and then it will return 0 as you expect it to be.