c++ - 二叉树的前序遍历可视化

Question

我决定从 http://rosettacode.org/wiki/Tree_traversal#C.2B.2B 中获取代码并使用 SDL 将其可视化。页面上的 ASCII 图形如下所示:

         1
        / \
       /   \
      /     \
     2       3
    / \     /
   4   5   6
  /       / \
 7       8   9

但到目前为止我设法得到的结果是这样的:

ASCII:

        1
      2 
    4   3
  7   6
    8
      9

注意缺少的 5。6 绘制在它上面(通过位置的调试输出验证。)

还有我的问题代码:

作为对指出打字错误的回应，我将从我的源文件中原样复制/粘贴:

  void preorderTraverse(int x = osd.position.x, int y = osd.position.y) const {
    osd.position.x = x;
    osd.position.y = y;
    std::cout << "Debug: " << x << " " << y << " " << getValue() << std::endl;
    osd.put(getValue());
    if(mLeft)  {  x -= 50; y += 30; mLeft->preorderTraverse(x, y);}
    if(mRight) {  x += 50; y += 30; mRight->preorderTraverse(x, y);}
  }

思路是遵循遍历的递归性，但是遍历右边的时候好像有问题。

请注意，我将默认参数设置为 osd.position，因为它们的定义如下:

position.x = SCREEN_WIDTH / 2 - 50/2;
position.y = 0;

而 osd.put 是:

SDL_Rect offset = get_offset(num);

SDL_BlitSurface( number_chart_, &offset, screen, &position );

offset 是源矩形(即 blitting 图像)。get_offset 简单地切片一个 sprite 数字表。

所以我的问题是如何修复 preorderTraverse 使其看起来像 ascii 图形？它不需要做检查整棵树的宽度等复杂的事情，只要适本地嵌套即可。

Answer 1

您的代码中存在一个简单的错误。对于正确的 child ，您应该添加到x，而不是从中减去。也就是说，您应该这样做:

if(mRight) 
{
    x += graphicWidth; // <-- Note the "+" here.
    y += graphicHeight; 
    mRight->preorderTraverse(x, y);
}

但这不会解决您所有的问题。我认为你在每次递归时添加或减去 x 的数量应该取决于你在树中的深度。

作为您可以执行的操作的示例，请尝试以下操作。向 preorderTraverse 添加另一个名为 xstride 的参数，如下所示:

void preorderTraverse(int xstride, int x, int y) const

并在第一次调用时像这样初始化它:

preorderTraverse (SCREEN_WIDTH / 4, /*some value for X*/, /*some value for Y*/)

然后，在函数体中，您将 xstride 添加到/从 x 减去:

x += xstride; // or x -= xstride. Also see the end note.

并且在每次递归调用 preorderTraverse 时，您将 xstride 除以 2:

mLeft->preorderTraverse (xstride / 2, x, y); // or mRight->...

注意:在 x 中添加/减去它时，您可能需要将 graphicWidth 添加到 xstride。