二叉搜索树无法正确识别值

Question

我想用C实现一个Binary Serach Tree。在这段代码中，我向树中添加了一些值，然后试图检查这些值是否在树中。但是我的尝试代码总是返回true。

我已经检查了很多次。我仍然在学习C编程。

这是我的代码。

#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; 
} 

我在这里错过了什么？

在此先感谢。

Answer 1

你缺少一个

num =scanf("%d"); 

不会做你认为它（scanf函数返回的项数转换成功或-1 EOF）。你没有曲柄你的编译器的警告级别高到足以告诉你，你需要

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

在你的破程序，scanf（）的恰好返回1（因为它转化项目1项，并写信给随机存储器）和因为树中有1个，你总是会变成真的。

Answer 2

除了@Jens指出的错误，您还没有从getNewNode返回值。添加声明：

return newNode; 

在该函数结束时。这里是一个fixed example on ideone

Answer 3

对于按照初学者的C标准的功能main不带参数应声明如下

int main(void) 

功能getNewNode

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

是未定义行为，因为它虽然已经没有返回返回类型BSTnode *。

该功能可以定义下列方式

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

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

    return newNode; 
} 

功能InsertNew是wrong.Take考虑，对于二叉搜索树有通常使用的运营商，而不是<运营商<=的。

这些陈述

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

和

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

没有意义，并覆盖的那不得实际改变节点的root->left和root->right值。另外创建的节点可以等于NULL，在这种情况下，原始根节点也将被NULL覆盖。

最好通过指针传递原始的根节点。你

也应该使用operator <而不是operator <=。

函数定义可以看看下面的方式

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); 
    } 
} 

和功能可以被称为像

InsertNew(&root, 34); 

不分配返回指针根节点。如果需要，可以在if语句中检查返回值。

如果你不希望有树重复的值，则函数可以写成下面的方式

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; 
    } 
} 

相应功能search应该像使用的

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; 
    } 
} 

定义本声明中的功能scanf

num =scanf("%d"); 

是错误的。

正确的调用看起来像

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

您还可以查看呼叫是否成功通过如果声明

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

使用条件，你应该免费为所有分配的内存树退出程序之前。

一般来说，最好是使用以下条件

if(search(root,num)){ 

，而不是与真正的

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

的严格比较的，因为如果该函数将在的情况下被改写这样的方式成功则返回任何非零值，然后与true进行严格比较将不起作用。