0

我知道这可能是一个简单的问题，但是自从我完成任何 C 编程以来已经有一段时间了。我正在尝试在 x 节点上执行中序遍历，其中 x 是我传递给函数的某个数字。我的中序函数递归地调用自己，在我的一生中，我无法弄清楚如何在其访问的 x 节点之后停止遍历。这是我的中序遍历函数：

void inorder(node h)
 {

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

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

        inorder(h->r);
     }
      return;

 }

非常感谢任何指导。

4

2 回答 2

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);
    }
}
于 2013-04-10T03:33:54.647 回答
0

试试这个 - 应该只适用于访问的 x 个节点（访问的节点数是被打印的候选节点）；

int inorder(node h, int x)
 {

     if (h != NULL && x > 0)
     {
        x = inorder(h->l, x);

        if (x > 0) {
           printf(" %d\n",h->item);
           x--;
        }
        if (h->r && x > 0)
           x = inorder(h->r, x);
     }
      return x;

 }

[编辑：@nhahtdh在对访问的节点的定义进行了一些讨论并减少了 x 的值后，更正了此代码。工作测试代码可以在这里看到。

于 2013-04-10T02:01:54.030 回答