1

我需要打印出一个看起来像这样的二叉树：

--------x-------
----x-------x---
--x---x---x---x-
-x-x-x-x-x-x-x-x 
xxxxxxxxxxxxxxxx

使用递归打印除第一行外的行的左侧和行的右侧。所以该函数会调用一个带有左起点和右终点参数的显示函数。然后它会调用自己两次，一次调用左侧，一次调用右侧。

    #include <stdio.h>

#define LENGTH 16

void makeBranches(int, int);
void display(int, int);

int main(){

  makeBranches(0, LENGTH-1);
}

void makeBranches(int left, int right){

  if(left >= right){
    return;
  } else{
    display(left, right);
      makeBranches(left, (right+left)/2);
      makeBranches((right+left)/2+1, right);  
  }
}

void display(int left, int right){
  int mid = (left+right)/2;
  int i;

  for(i = left; i <= right; i++){
    if(i == mid)
      printf("X");
    else
      printf("-");
  }

  if(right == LENGTH-1)
    printf("\n");

}

这就是我的代码目前的样子，尽管它已经改变了很多次。

我不知道如何让 makeBranches 的第一次调用执行然后第二次调用。现在它只做左边的调用，看起来像这样：

-------X--------
---X-----X--X-
4

2 回答 2

0

您将需要进行广度优先遍历。

于 2012-11-08T20:03:11.407 回答
0

如您所见，您的问题在于调用递归函数的结构树。为了防止这种类型的行为，您需要实现一个设计，在打印任何内容之前扫描整个树。

您现在的调用结构如下所示：

makeBranches(left,right) -> 
  makeBranches(left, (right+left)/2) ->
    makeBranches(left, ((right+left)/2+left)/2) ->
      makeBranches(left, (((right+left)/2+left)/2+left)/2) -> etc.
  makeBranches((right+left)/2+1,right) ->
    makeBranches((right+(right+left)/2+1)/2+1,right) ->
      makeBranches((right+(right+(right+(right+left)/2+1)/2+1)/2+1)/2+1,right) -> etc.

为了解决这个问题，您应该做的是在打印之前捕获每个级别。为此，您需要某种形式的集合，例如为每一侧添加链接列表，然后一旦扫描整个树，您就可以重建绘图。

在您的display函数中，您已经创建了一个检查以了解这是行的左侧还是右侧：

if(right == LENGTH-1)
    printf("\n");

所以让我们修改显示调用。

void display(int left, int right){
  int mid = (left+right)/2;
  int i;
  string thisLine = "";

  for(i = left; i <= right; i++){
    if(i == mid)
      thisLine += "X";
    else
      thisLine += "-";
  }

  if(right == LENGTH-1) {
    rightList.add(thisLine);
  } else {
    leftList.add(thisLine);
  }
}

现在，main()在构建整个树之后，打印出每个列表的每个节点left->right->"\n"（重复直到为空）。

您可以注意的一些警告，但可以设计的是，您第一次调用display创建整行，所以如果您使用我的代码，它会将它放在right列表中，这意味着您必须像这样绘制它right->(left->right->"\n")repeat

这有意义吗？我希望我没有跳过任何东西，因为我在概念上做了这一切：\

于 2012-11-08T19:19:33.190 回答