c - 依次遍历x个节点

Question

我知道这可能是一个简单的问题，但我已经有一段时间没有做过任何 C 编程了。我试图在 x 节点上执行中序遍历，其中 x 是我传递给函数的某个数字。我的 inorder 函数正在递归地调用自身，并且在我的生命周期中，我无法弄清楚如何在访问过 x 节点后停止遍历。这是我的中序遍历函数:

void inorder(node h)
 {

     if (h != NULL)
     {
        inorder(h->l);

        printf(" %d\n",h->item);

        inorder(h->r);
     }
      return;

 }

非常感谢任何指导。

Answer 1

假设“访问次数”是要从中序遍历中打印出的节点数。一种解决方案是让 inorder 函数返回剩余要打印的节点数，并在遍历树时对其进行检查。

int inorder(node h, int x)
{
    // I mimic your current code. The code is indeed shorter, but it will
    // do extra recursion, compared to the other approach of checking
    // for the subtree and value of x before the recursive call.
    if (h != NULL && x > 0)
    {
        x = inorder(h->l, x);

        if (x > 0) {
            printf(" %d\n",h->item);
            x--;
        }

        x = inorder(h->r, x);
    }

    return x;
}

实现中的另一个细微变化是将指针传递给包含 x 的变量，并使用它来更新计数器。如果这样编写，该函数不需要返回任何内容。

void inorder(node h, int *x)
{
    // I mimic your current code. The code is indeed shorter, but it will
    // do extra recursion, compared to the other approach of checking
    // for the subtree and value of x before the recursive call.
    if (h == NULL && *x > 0)
    {
        inorder(h->l, x);

        if (*x > 0) {
            printf(" %d\n",h->item);
            (*x)--;
        }

        inorder(h->r, x);
    }
}