在 c++ 中使用递归返回一个值

Question

我接受了采访，无法回答这个问题。您有一个二叉树，并且使用 in_order 将所有节点放入数组中，然后返回数组大小的值。有人告诉我不能使用辅助函数并为数组计数器添加 int i=0 。

我必须使用的递归函数标题是。

      In_order(Struct_Node * node, int *array){

      }

因为我是按顺序写的。

      if(node){
      In_order(node->left, array);

//这一行是我应该添加元素并返回值的地方， 但我不明白该怎么做。这是我的一周重点，我需要理解 这段代码如何工作的推理比代码是什么更重要。

      in_order(node->right,array); 
      }

我实际上并没有写在两个 In_order 语句之间写的内容，但我写的内容是错误的。

Answer 1

猜测所有丢失的细节，我认为你会做类似的事情：

int In_order(Struct_Node * node, int *array){

   int count = 0;
   if (node->left) {
     count += In_order(node->left, array);
   }
   array[count++] = node->data; // whatever it is you're storing
   if (node->right) {
     count += In_order(node->right, array+count);
   }
   return count;
}

关键点是你将更新的指针传递给 RHS 递归调用，并且你的返回值为 1 + LHS return + RHS return

如果你可以'不要使用 int 作为计数器（这真的很愚蠢，因为它是迄今为止最清晰的表达方式），你可以这样做：

int In_order(Struct_Node * node, const int *array){
   int *tptr = array;

   if (node->left) {
     tptr += In_order(node->left, array);
   }
   *tptr++ = node->data; // whatever it is you're storing
   if (node->right) {
     tptr += In_order(node->right, tptr);
   }

   return tptr-array;
}

如果你想“有点”疯狂并避免除函数参数之外的任何局部变量，你可以更改返回类型为指向数组当前工作端的指针（实际上也是数组的大小）并执行以下操作：

int *In_order(const Struct_Node * const node, int * const result) {
  return !node ? result :
          In_order(node->right, &(*In_order(node->left, result) = node->value)+1);
}

尽管说​​实话，这是糟糕的代码（我什至不能 100% 确定它定义良好！）并且我真的希望他们没有在寻找这样的解决方案！

Answer 2

中序是树遍历的一种方法；您按顺序（因此得名）从左到右移动节点。

因此，对于插入部分，您可以将所有节点插入当前节点的左侧，插入当前节点，然后将所有节点插入右侧。

在 in_order(node->right,array) 调用之后，您返回您的值（您的问题描述不清楚您应该返回什么）。

Answer 3

对于中序遍历：

1. 对左子树（如果有）进行中序遍历。
2. 访问当前节点。
3. 对右子树（如果有）进行中序遍历。

在您的情况下，“访问”意味着将当前节点添加到列表中，并增加计数器。

至于将元素放入数组中，就我个人而言，我会使用向量（如果绝对必要，然后在最后转换/复制到数组中）。您可以在“启动”函数中创建它，然后调用递归函数，或者在调用方中创建它。无论哪种方式，您都可以在每次调用中传递对它的引用。最后，您将获得节点值数组和计数。否则，您最终必须遍历树一次来计算元素，然后再遍历一次来收集它们。 （或者你可以传递一个引用或指向一个指针的指针，这样你就可以根据需要重新分配，但这会变得很难看。无论哪种方式，我都不相信调用者知道给你一个多大的数组——这是你的工作知道/计算你的树的大小：P）