搜索遞歸地用C

Question

二叉樹的函數接收參數節點（已經成員名稱）和STR（名稱搜索）

{ 
    if (node == NULL) return NULL; 
    if (strcmp(node->name, str) == 0) return node; 
    node = search_RtLR(node->left, str); 
    if (node != NULL) return node; 
    node = search_RtLR(node->right, str); 
    if (node != NULL) return node; 

    return NULL; 
} 

當我搜索一個名稱，在左子樹，它的工作原理，但當我在右子樹中搜索時，程序終止（同樣當樹中沒有這樣的名字時），我找不到錯在哪裏。樹不按字母順序排序。

Answer 1

你重寫你的節點參數變量：

node = search_RtLR(node->left, str); // overwriting node here at assignment 
if (node != NULL) return node; 
node = search_RtLR(node->right, str); // node is NULL here, look at line above! 

你不應該！

定義的參數爲const（因爲這是不會改變任何數據的功能）也有助於（如編譯器會警告你，如果你試圖覆蓋const的變量）：

Node* search_RtLR(const Node* node, const char* str) { 
    if (node == NULL) return NULL; 
    if (strcmp(node->name, str) == 0) return node; 
    const Node* newNode = search_RtLR(node->left, str); 
    if (newNode != NULL) return newNode; 
    return search_RtLR(node->right, str); 
} 

Answer 2

當字符串不在leftsubtree中遞歸搜索返回NULL，您分配給node。然後search_RtLR(node->right, str)搜索'無處'。你不應該覆蓋你的node：

if (node == NULL) return NULL; 
if (strcmp(node->name, str) == 0) return node; 
node1 = search_RtLR(node->left, str); 
if (node1 != NULL) return node1; 
node1 = search_RtLR(node->right, str); 
if (node1 != NULL) return node1; 

return NULL;