二叉搜索樹無法正確識別值

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進行嚴格比較將不起作用。