1

我已经编写了一个代码来使用队列（数组）按级别顺序打印树。

    void printLevelOrder(node *root) {
         node* queue[10];
         node*t=root;
         int y=0;
         queue[y]=t;
         for(int i=0;i<10;i++)
         {
                 printf("%d,",queue[i]->val); 

                 t=queue[i];
                 if((t->left)!=NULL){
                 queue[++y]=t->left;
                 }
                 if((t->right)!=NULL){
                 queue[++y]=t->right;
                 }
         } 
}

我想将该方法转换为递归方法。我试过了，但我没有得到正确的解决方案。是否可以将此类问题转换为使用递归调用？

4

4 回答 4

1

可以进行递归，但在这种情况下，结果可能看起来就像上面代码中的循环体正在执行，然后为队列中的下一个元素调用自身。不可能将其转换为在树遍历算法中更常见的一种递归，其中递归方法为它作为参数接收的子节点调用自身。因此没有预期的性能提升——你仍然需要队列或类似的结构——而且我真的不明白执行转换的意义。

于 2012-10-09T08:14:21.610 回答
0

据我了解，以“级别顺序”打印树实际上是对给定树的BFS遍历，递归不适合。递归是一种非常适合DFS的方法。

递归在内部使用堆栈（LIFO 结构），而 BFS 使用队列（FIFO 结构）。如果根的解决方案取决于（结果，或只是遍历顺序）子树的解决方案，则树算法适用于递归。递归到树的“底部”，从底部向上解决问题。由此，前序、中序和后序遍历可以作为递归完成：

  • pre-order : 打印根，打印左子树，打印右子树
  • in-order：打印左子树，打印根，打印右子树
  • post-order : 打印左子树，打印右子树，打印根

然而，级别顺序不能分解为“为根做一些事情，为每个子树做一些事情”。唯一可能的“递归”实现将遵循@Qnan 的建议，并且正如他所说，没有多大意义。

然而，可以相当优雅地将任何递归算法转换为迭代算法。由于内部递归实际上与堆栈一起工作，因此在这种情况下唯一的技巧是使用您自己的堆栈而不是系统堆栈。这种递归和迭代实现之间的一些细微差别是：

  • 通过迭代，您可以节省函数调用的时间
  • 使用递归，您通常会得到更直观的代码
  • 使用递归，每个函数调用都会为返回地址分配额外的内存
  • 使用iterative，您分配内存，并确定分配内存的位置
于 2012-10-09T14:53:07.463 回答
0

我不确定这是否是您正在寻找的，但它是部分递归。

void print_level_part(node* p, level) {
    if(p) {
        if(level==1) {
            printf("%d", p->val);
        } else {
            print_level_part(p->left, level-1);
            print_level_part(p->right, level-1);
        }
    }
}

//the loop in main which does the main printing.
for(int i=0; i<n; ++i) {
    print_level_part(root, i);
}

如果您想要完全递归的解决方案，那么我可能会建议您更改递归函数for中的循环。main

于 2012-10-09T13:37:22.137 回答
0

这是 Qnan 所说的一个例子：

void printNext(node **queue,int i,int y)
{
  if (i==y) return;

  node *t = queue[i++];
  printf("%d,",t->val);

  if (t->left)  queue[y++] = t->left;
  if (t->right) queue[y++] = t->right;

  printNext(queue,i,y);
}

void printLevelOrder(node *root)
{
  node *queue[10]; /* be careful with hard-coded queue size! */
  int y=0, i=0;

  queue[y++]=root;
  printNext(queue,i,y);
  printf("\n");
}
于 2012-10-09T14:25:38.237 回答