Предпросмотр обхода двоичного дерева

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 

Записка отсутствует. 6. Наверху изображено 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); 

смещение источника прямоугольник (т.е. , blitting изображение.) get_offset просто нарезает лист спрайтов чисел.

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

Answer 1

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

Answer 2

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

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);}