二進制搜索樹插入在C中無法正常工作（可能是一個無知的錯誤）

我想在C中使BST樹結構，但我有一些困難，讓我的插入功能工作。在閱讀了一些例子之後，我發現最好的方法是傳遞一個指向樹根的指針，然後在該節點上遞歸地插入，直到找到一個空的節點（NULL）。不過，我想在整個樹結構（只是讓一切都整齊地封裝）來傳遞，我想我想出了以下解決方案：二進制搜索樹插入在C中無法正常工作（可能是一個無知的錯誤）

void insert(struct Node* temp, char *s){ 

if (temp == NULL) { 
    struct Node *newNode = make_node(); 
    newNode-> data = strdup(s); 
    temp = newNode; 
    return; 


} 
if (strcmp(s,temp->data) > 0) { 
    temp = temp->left; 
    insert(temp, s); 
    } 
if (strcmp(s,temp->data) < 0) { 
    temp = temp->right; 
    insert(temp, s); 
    } 

} 
//--------------------------------------------------------------          
void insert_tree(struct BSP * tree, char *s) { 

    struct Node *temp = tree->root; 
    insert(temp, s); 

} 
//-------------------------------------------------------------

當我插入的樹，我叫insert_tree（），但後來我使用insert（）作爲遞歸插入應該指向樹根的節點的一種方式。 P.S的BSP的結構和節點是：

typedef struct Node { 
    struct Node * left; 
    struct Node * right; 
    char * data; 

} node; 

typedef struct BSP { 
    struct Node * root; 
    int size; 
}

誰能幫助我理解我在做什麼錯？

來源

2015-03-13 Charles Davis

究竟發生了什麼問題？ – JeremyP 2015-03-13 14:45:22

什麼是無知的錯誤？我的錯誤往往很文盲。 – dhein 2017-07-28 09:40:08

第一個答案是對的，但你總是可以使用指針指針，就像這樣。

typedef struct Node 
{ 
    Node() 
    { 
     left = NULL; 
     right = NULL; 
     data = NULL; 
    } 

    struct Node* left; 
    struct Node* right; 
    char* data; 
} node; 

typedef struct BSP 
{ 
    BSP() 
    { 
     root = NULL; 
     size = 0; 
    } 

    struct Node* root; 
    int size; 
} bsp; 

void insert(struct Node** temp, char* s) 
{ 
    Node* node = *temp; 

    if (node == NULL) 
    { 
     struct Node* newNode = new Node(); 
     newNode->data = strdup(s); 
     (*temp) = newNode; 
     return; 
    } 

    if (strcmp(s, node->data) > 0) 
    { 
     insert(&node->left, s); 
    } 

    if (strcmp(s, node->data) < 0) 
    { 
     insert(&node->right, s); 
    } 
} 

void insert_tree(struct BSP* tree, char* s) 
{ 
    insert(&tree->root, s); 
    tree->size++; 
}

來源

2015-03-13 15:23:44 kewl

非常感謝你的迴應。它不僅幫助我獲得代碼的工作，而且現在我感覺終於明白了爲什麼使用指針指針可能會有用。 – 2015-03-13 16:01:58

你的問題是你扔掉了新的節點。在C函數中，參數是按值傳遞的，這意味着在調用者中插入函數中的temp不會改變。

插入應該返回新創建的節點，並且您需要在調用者中對它做些什麼。

來源

2015-03-13 14:49:35 JeremyP

二進制搜索樹插入在C中無法正常工作（可能是一個無知的錯誤）

回答

相關問題