C中的二叉搜索樹程序行爲奇怪

Question

我寫了下面的代碼來創建二叉搜索樹，但是當創建函數被調用並且它試圖在程序第一次調用insertNode（...）掛了。以下是密碼：

struct BstNode{ 
    int value; 
    struct BstNode* left; 
    struct BstNode* right; 
}; 

struct BstNode *root; 

struct BstNode* insertNode(struct BstNode* root, int data){ 
    if(data <= root->value) 
     root->left = insertNode(root->left, data); 
    else 
     root->right = insertNode(root->right, data); 

    printf("%d ",root->value); 
    return root; 
} 


void create(struct BstNode* root){ 
    int data; 
    if(root == NULL){ 
     //create the root node 
     printf("\nInside create"); 
     root = (struct BstNode*) malloc(sizeof(struct BstNode)); 
     printf("\nData :: "); 
     scanf("%d",&data); 
     root->value = data; 
     root->left = NULL; 
     root->right = NULL; 
    } 
    else{ 
     printf("\nCalling insertNode()"); 
     printf("\nData :: "); 
     scanf("%d",&data); 
     root = insertNode(root, data); // The program hangs up here : the very first time this line is executed 
     printf("\nCalled insert"); 
    } 
} 

int main(){ 
    root = NULL; 
    int i; 
    for(i=0;i<5;i++){ 
     create(root); 
     printf("%d ",root->value); // For checking the value 
    } 
    return 0; 
} 

有人可以指出我的錯誤。任何建議都很有幫助。

Answer 1

有人可以指出我的錯誤。

主要問題是createNode修改了本地副本root。全局變量root從不修改，並且仍然設置爲NULL。

任何建議是有幫助的。

1. 避免使用全局變量。移動root成爲main中的局部變量。
2. 更改create的簽名和目的，以便它只創建一個節點，而不是其他任何東西。
3. 請勿投下malloc的結果。見Specifically, what's dangerous about casting the result of malloc?
4. 使用insertNode而不是create在main。撥打create從insertNode在正確的地方。
5. 添加一個打印樹內容的函數。
6. 在測試代碼時，使用隨機數代替用戶輸入的數據。
7. 通過使用命令行參數，可以靈活地創建5個以上的節點。

這是我的計劃建議：

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

struct BstNode{ 
    int value; 
    struct BstNode* left; 
    struct BstNode* right; 
}; 

struct BstNode* create(int data){ 
    printf("Creating a node with value: %d\n", data); 
    struct BstNode* node = malloc(sizeof(*node)); 
    node->value = data; 
    node->left = NULL; 
    node->right = NULL; 
    return node; 
} 

struct BstNode* insertNode(struct BstNode* root, int data){ 
    if (root == NULL) 
    { 
     return create(data); 
    } 

    if(data <= root->value) 
     root->left = insertNode(root->left, data); 
    else 
     root->right = insertNode(root->right, data); 

    return root; 
} 

void print(struct BstNode* node, int indent, char const* nodeName) 
{ 
    if (node == NULL) 
    { 
     return; 
    } 

    for (int i = 0; i < indent; ++i) 
    { 
     printf(" "); 
    } 
    printf("%s: %d\n", nodeName, node->value); 
    print(node->left, indent+1, "left"); 
    print(node->right, indent+1, "right"); 
} 

int main(int argc, char** argv){ 
    struct BstNode *root = NULL; 
    int i; 
    int data; 
    int num = 5; 
    if (argc > 1) 
     num = atoi(argv[1]); 

    srand(time(NULL)); 
    for(i=0;i<num;i++){ 
     data = rand()%10000; 
     root = insertNode(root, data); 
    } 

    printf("\n"); 
    print(root, 0, "root"); 
    return 0; 
} 

Answer 2

用於這種樹插入算法是（insert(node, value)）：

• 如果node是NULL分配的節點，設置左/右爲NULL（它是葉），設置值到value，返回分配節點
• 否則，如果value < node->value：node->left = insert(node->left, value)
• 其他：node->right = insert(node->right, value)
• return node（使我們有均勻碼）

從插入說讓你說main是一樣的：root = insert(root, val)。

與其返回值，您也可以將指針傳遞給指針（&root），但您必須在函數中對其進行解引用。你似乎不太熟悉指針，如果你打算使用這樣的結構，你應該更多地閱讀這些內容。

還要注意的是，在你的main功能您printf是沒有用的：在那種樹木的根值將始終是第一個插入的值（或者你將不得不在樹中執行轉移到平衡的分支，但這是另一個問題）。 打印btree也意味着一個遞歸函數，並且您必須選擇如何打印它（深度優先，排序...）。例如：如果節點是NULL返回;在左邊稱自己;打印值;打電話給自己→將打印按小到大排序的內容。

Answer 3

功能insertNode有導致程序崩潰無限遞歸。

更具體

struct BstNode* insertNode(struct BstNode* root, int data){ 
    if(data <= root->value) 
     root->left = insertNode(root->left, data); 
    else 
     root->right = insertNode(root->right, data); 

printf("%d ",root->value); 
return root; 

你去功能，並檢查是否（數據< =根 - >值）。在這兩種情況下（true和false），都會再次調用insertNode函數，然後再次調用insertNode - 您將永遠不會收到返回語句。遞歸函數需要有基本的情況下返回一些值，而無需再次調用自己。

thisFunction() 
    if (base case) 
    return value; 
    else 
    return thisFunction() 

在二叉搜索樹的情況下，基本情況是，當你的密鑰（數據）要插入的A）插入鑰匙，比目前的節點，當前節點的右孩子越大葉（空）或B ）插入的關鍵字比當前節點更小（或等於您要解析關係的方式），並且當前節點的左側子項爲空。 (data > cur->data && cur->right == NIL)或(data < cur->data && cur->left == NIL)。如果您遇到這些情況之一，只需將新節點設置爲當前節點的子節點或子節點。