Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > [C++]Отрисовка Бинарных Деревьев

Автор: Addidas 28.3.2009, 00:32

Пишу я значит визуализацию бинарных деревьев. Суть задачи - есть класс для работы с бин. деревом. Надо по имеющемуся дереву отрисовать его в компаненте, скажем PaintBox, примитивами. То есть кружки и линии.
Библиотеки сторонние использовать крайне не хочу.
Среда разработки - Borland C++. Но даже если не кодом так помогите хотя бы подробным описанием алгоритма - как просчитать всё эту отрисовку. Дня три уже сижу - ничего путного пока не пришло в голову.

Автор: zim22 28.3.2009, 08:48

алгоритм отрисовки на VB
http://www.vb-helper.com/howto_net_fractal_binary_tree.html

Автор: Addidas 28.3.2009, 08:55

Цитата(zim22 @ 28.3.2009, 08:48)

алгоритм отрисовки на VB
http://www.vb-helper.com/howto_net_fractal_binary_tree.html

Спасибо конечно за линк, но нельзя ли по русски и всё таки на С\С++... VB я не знаю и код что там приведён - адские письмена...

Автор: zim22 28.3.2009, 09:29

Цитата(Addidas @ 28.3.2009, 08:55

)

I have been translating it personally for you. Enjoy!

Код

Рекурсивная рисовалка ветки бинарного дерева
void DrawBranch(CDC *dc, int depth, int X, int Y, double length, double theta, double length_scale, double dtheta)
{
   int x1, y1;
   // Определим, где текущий ветка должна заканчиваться.
   x1 = (X + length * cos(theta));
   y1 = (Y + length * sin(theta));
   dc->DrawLine(X, Y, x1, y1);
   // Если глубина больше 1, отрисовать подветки
   if (depth > 1)
   {
       DrawBranch(dc, depth - 1, x1, y1, length * length_scale, theta + dtheta, length_scale, dtheta);
       DrawBranch(gr, depth - 1, x1, y1, length * length_scale, theta - dtheta, length_scale, dtheta);
   }
}

Автор: Addidas 28.3.2009, 10:02

Thanks 4 your translating for me personal but may be u explain me parametrs that function.
cdc - я понял это контекст устройства на котором рисуем...
depth - глубина текущего узла
X Y - относительно каких координат начинаем рисовать - так?
остальные параметры загадка 4 me

Автор: zim22 28.3.2009, 10:50

Цитата(Addidas @ 28.3.2009, 10:02

)

X Y - относительно каких координат начинаем рисовать - так?

наверно. это не моя функция, не могу точно знать.

Цитата(Addidas @ 28.3.2009, 10:02

)

стальные параметры загадка 4 me

double length - длина какая-то.
double theta, double dtheta - поставь туда значения разные, посмотри что происходит.
double length_scale - это масштаб сужения / растягивания изображения

Автор: Addidas 28.3.2009, 20:26

Посмотрел функцию - отрисовку делает тока в общем виде... то есть рисует явно - узел и 2 потомка.... моя же задача стоит отрисовывать по существующему дереву... то есть могут быть все 2^(n-1) узлов на каждом уровне.. .а могут быть узлы у которых только по одному потомку... ну для пример
      2
     / \
    1  3
   / \   \
  0  2  4

тут вот у узла 1 - два потомка, а у узла 3 - один... следовательно нарисовать надо
      ()
     /  \
    ()  ()
   /  \   \
  ()  ()  ()
ну это для примера.
той функцией такого не сделать!

Автор: Anikmar 30.3.2009, 08:27

Может попробовать рисовать снизу вверх?

Автор: Addidas 31.3.2009, 15:33

Да нее... я уже сам дошёл до решения... проще всё на самом деле... тока дерево получается растянутым... но масштабирование рулит и всё такое... всем спасибо..

Автор: zim22 31.3.2009, 16:00

Цитата(Addidas @ 31.3.2009, 15:33

)

я уже сам дошёл до решения...

не хотите с нами поделиться?

Автор: Addidas 3.4.2009, 09:31

Идея проста... я завёл в деревьях для каждого узла три доп поля.... два поля это координаты - X и Y, а третье это поле указывающее какой это узел - левый, правый или корень... Далее рекурсивно расчитывал координаты по принципу - на каждый уровень дерева общую ширину холста надо делить на 2 ^ (текущий уровень)... ну и соответственно корень встанет ровно в серединку, а все остальные будут строиться относительно него уже... сам код :

Код


void Tree :: GNK(Tree *r, Tree *prev, int W, int Y, int L)
{
 int buf;

 buf = floor(W / pow(2, L));
 
 if(r != NULL)
    {

       if (prev == NULL)
        {
          r->x = buf;
                          r->y = Y;
        }
       else
        {    
         if (r->n == 'l')
          {
           r->x =prev->x - buf + 10;
           r->y = prev->y + 60;
          }
         else
          {
           if (r->n == 'r')
            {
              r->x = prev->x + buf - 10;
              r->y = prev->y + 60;
            }
          }
        }


       GNK(r->left,r,W,r->y, L + 1);
       GNK(r->right,r,W,r->y, L + 1);
    }
}

Автор: zim22 3.4.2009, 13:05

Addidas, спасибо smile