Как я могу устранить хвостовую рекурсию в следующей функции (от двух рекурсивных вызовов до одной)?

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);
}