搜索递归地用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;