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

我决定从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是源矩形（即对图像进行blit处理）。get_offset只是将数字的Sprite切片。

所以我的问题是如何将preorderTraverse修复​​为ascii图形？它不必做复杂的事情，例如检查整个树的宽度等，只需正确嵌套即可。

最佳答案

您的代码中有一个简单的错误。对于合适的孩子，应该添加到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->...

注意：将graphicWidth添加到xstride或从中减去时，可能需要在x中添加。

关于c++ - 二叉树的遍历可视化，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/16560971/