如何在以下函数中消除尾部递归（从两个递归调用到一个）？

Question

我具有以下功能：

void treetraverse (tnode *node)
{
   if (node == NULL)
   {
      return;
   }
   fprintf(stdout,"%d",node->val);
   if (node-> d == 'L')
   {
      treetraverse(node->r);
      treetraverse(node->l);
    }
    else
    {
      treetraverse(node->l);
      treetraverse(node->r);
     }
}

d是方向，可以是'L'或'R'。并且node-> r和node-> l分别是节点的左右子节点。我正在尝试从中删除尾递归，使其在功能上等效-它现在进行两个递归函数调用，但我希望它进行一次。我该如何重写该函数以实现该目标？谢谢。

Answer 1

最直接的方法将是类似于

void treetraverse (tnode *node)
{
  do
  {

   if (node == NULL)
   {
      return;
   }
   fprintf(stdout,"%d",node->val);

   tnode *node1;
   tnode *node2;

   if (node-> d == 'L')
   {
      node1 = node->r;
      node2 = node->l;
    }
    else
    {
      node1 = node->l;
      node2 = node->r;
     }

    treetraverse(node1);
    node = node2;

    }
    while (true);
}