1

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

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

但到目前为止我设法得到的结果看起来像：

http://i41.tinypic.com/x0ts7m.png

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 图形？它不必做复杂的事情，例如检查整个树的宽度等，只需正确嵌套即可。

4

2 回答 2

0

您的代码中有一个简单的错误。对于正确的孩子，你应该添加而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，除以xstride2：

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

注意：您可能需要在graphicWidth向xstride/从x.

于 2013-05-15T09:23:46.330 回答
0

你的逻辑在这里是完全错误的。

if(mLeft)  {  x -= 50; y += 30; mLeft->preorderTraverse(x, y);}
if(mRight) {  x += 50; y += 30; mRight->preorderTraverse(x, y);}

看看它，想想x如果两者都 mLeft 存在 mRight会发生什么。你减去 50然后加回来。 mRight最终得到与父级相同的 x 坐标。

同样，y您要添加 30两次。

你想要这样的东西。

if(mLeft)  {  mLeft->preorderTraverse(x - 50, y + 30);}
if(mRight) {  mRight->preorderTraverse(x + 50, y + 30);}
于 2013-05-15T16:15:59.353 回答