Предварительная визуализация обхода двоичного дерева

Question

Предварительная визуализация обхода двоичного дерева

Я решил взять код от http://rosettacode.org/wiki/Tree_traversal#C.2B.2B и визуализировать его с помощью SDL. Графика ASCII на странице выглядит следующим образом:

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

Но результат, который мне удалось получить, выглядит так:

ASCII:

Обратите внимание на пропущенные 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 );

смещение — это исходный прямоугольник (т. е. блицание изображения). get_offset просто разрезает спрайт-лист чисел.

Итак, мой вопрос, как я могу исправить preorderTraverse, чтобы он выглядел как графика ascii? Он не должен делать сложные вещи, такие как проверка ширины всего дерева и т. Д., Просто должен быть правильно вложен.

1

binary-tree c++sdl tree-traversal

Решение

Другие решения

Ваша логика здесь просто неверна.

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 заканчивается той же координатой х, что и родитель.

Аналогично с y вы добавляете 30 дважды.

Вы хотели что-то вроде этого.

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

0

Источник

Accepted Answer

В вашем коде есть простая ошибка. Для правильного ребенка, вы должны добавлять в 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,

0