C语言如何不使用全局变量递归返回二叉树节点指针

问题本质 #

原实现用全局变量跨递归栈帧存储匹配结果，存在几个明显缺陷：

• 函数不可重入，多线程场景下会出现数据竞争
• 重复调用前必须手动重置全局变量，否则会返回脏结果
• 找到目标节点后不会终止递归，会遍历完整棵树，存在无意义的性能损耗

最优改造方案：利用函数返回值传递结果 #

把函数返回值从void改为Tree*类型，让每一层递归把查找结果直接向上返回，一旦找到匹配节点就立刻终止递归向上传递，完全不需要全局变量。

struct tree {
   char info;
   struct tree* left;
   struct tree* right;
};

typedef struct tree Tree;

// 查找成功返回对应节点地址，未找到返回NULL
Tree* nodeAddress (Tree* a, char v) {
   if (a == NULL) {
      return NULL;
   }
   // 先遍历左子树查找
   Tree* left_find = nodeAddress(a->left, v);
   if (left_find != NULL) {
      return left_find;
   }
   // 匹配当前节点
   if (a->info == v) {
      return a;
   }
   // 左子树、当前节点都未命中，返回右子树查找结果
   return nodeAddress(a->right, v);
}

调用方式 #

直接接收函数返回值即可，不需要额外定义全局变量：

Tree* target_node = nodeAddress(root, 'x');
if (target_node != NULL) {
   // 找到节点后的业务逻辑
}

这个实现保持了原代码的中序遍历（左->根->右）逻辑，找到第一个匹配节点后就会立刻返回，比原实现执行效率更高，且没有全局状态依赖，线程安全、可重入，同一时间多个线程调用该函数不会互相干扰。

兼容方案：二级指针做输出参数 #

如果因为历史接口兼容要求，不能修改原函数的void返回值类型，可以新增一个二级指针类型的形参作为输出载体，同样可以移除全局变量：

// 第三个参数为输出参数，传入存储结果的指针地址
void nodeAddress (Tree* a, char v, Tree** result) {
   // 空节点或者已经找到结果，直接返回终止递归
   if (a == NULL || *result != NULL) {
      return;
   }
   nodeAddress(a->left, v, result);
   if (a->info == v) {
      *result = a;
      return;
   }
   nodeAddress(a->right, v, result);
}

调用方式 #

Tree* target_node = NULL;
nodeAddress(root, 'x', &target_node);
// 调用完成后target_node即为查找结果

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