在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

当字符串不在左子树中时递归搜索returns NULL，您将其分配给node。然后 search_RtLR(node->right, str) 搜索 'nowhere'。你不应该覆盖你的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;

在C中的二叉树中递归搜索

Search recursively in binary tree in C

c

binary-tree