二叉树搜索函数递归异常：找到目标节点后未正确返回

我在给二叉树添加节点时，通过搜索目标节点来挂载新节点。只往同一侧（左或右）添加时函数正常，但先左后右添加时，明明找到了目标节点，find_node函数却没有触发return root终止递归，反而一直执行到root为NULL。我用的是Ubuntu下的GCC编译器，不确定是不是编译器的问题。

核心代码 #

find_node查找函数 #

tree* find_node(tree *root, unsigned int index){
    if(root==NULL){
        return NULL;
    }else if(root->value==index){
        return root;

    }else if(root->value<=index){
        find_node(root->left, index);
    }else if(root->value>index){
        find_node(root->right, index);
    }
}

create_node_link节点挂载函数 #

void create_node_link(tree **root, int value, int index, int link_type){
    tree *new_node=malloc(sizeof(tree));
    if(new_node!=NULL){
        new_node->left=NULL;
        new_node->right=NULL;
        new_node->value=value;
    }

    tree *position=find_node(*root, index);
    if(position==NULL){
        printf("NOT FOUND");
        getch();
        return;
    }

    if(link_type==1)
        link_left(position, new_node);
    else if(link_type==2)
        link_right(position, new_node);
    viz_tree(*root);
}

树结构定义 #

头文件声明 #

typedef struct my_tree tree;

源文件结构体定义 #

struct my_tree{
    unsigned int value;
    tree *left;
    tree *right;
};

根节点初始化代码 #

// 主程序中初始化根节点
tree *root=create_node(1);

// header.c中的节点创建函数
tree *create_node(int value){ 
    tree* result=malloc(sizeof(tree));
    if(result!=NULL){
        result->left=NULL;
        result->right=NULL;
        result->value=value;
    }
    return result;
}

问题原因与修复 #

问题根源 #

find_node函数的递归分支没有返回值！当进入root->value<=index或root->value>index分支时，你调用了递归的find_node，但没有把递归结果返回给上层调用。这导致：即使递归深处找到了目标节点并返回，上层递归调用因为没有return这个结果，会执行到函数末尾，而C语言中无明确return的函数会返回未定义值（通常是垃圾值），最终上层调用拿到NULL，表现为找不到节点，递归持续到root为NULL。

修复后的find_node函数 #

tree* find_node(tree *root, unsigned int index){
    if(root==NULL){
        return NULL;
    }else if(root->value==index){
        return root;

    }else if(root->value<=index){
        return find_node(root->left, index); // 新增return，传递递归结果
    }else if(root->value>index){
        return find_node(root->right, index); // 新增return，传递递归结果
    }
    // 增加默认return，避免编译器警告
    return NULL;
}

额外优化建议 #

• 该问题与Ubuntu下的GCC编译器无关，纯代码逻辑错误。
• create_node_link中如果malloc失败（new_node为NULL），后续链接操作会触发空指针访问，建议添加错误处理：

  if(new_node == NULL){
      printf("内存分配失败");
      return;
  }
  

内容的提问来源于stack exchange，提问作者Marius Iordan