二叉树递归函数
我需要打印出一个如下所示的二叉树：
--------x------- ----x-------x--- --x---x---x---x- -xxxxxxxx xxxxxxxxxxxxxxxx 使用递归打印行的左侧和行的右侧，但第一行除外。 因此该函数将调用具有左起点和右终点参数的显示函数。 然后它会自动调用两次，左侧为一侧，右侧为一侧。
#include #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-
正如您所看到的，您的问题存在于调用递归函数的结构树中。 为了防止这种类型的行为，您需要实现一种设计，在打印整个树之前扫描整个树。
您的呼叫结构现在的工作方式如下：
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.
为了平衡这一点，你应该做的是在打印之前捕获每个级别。 要做到这一点，你需要某种forms的集合，如链接列表，为每一面添加，然后扫描整个树后，你可以重建绘图。
在您的displayfunction中，您已经创建了一个检查，以确定这是该行的左侧还是右侧：
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
这有意义吗？ 我希望我没有跳过任何事情，因为我在概念上做了这一切：
您将需要进行广度优先遍历 。