Двоичное дерево, нарисовать дерево в графе Опции

[setare]

Здравствуйте! У меня большая проблема. Не могли бы вы подсказать как можно нарисовать дерево в модуле граф. Нужно его нарисовать так, чтобы вершина этого дерева перемещалась в зависимости от того, сколько там веток. Если одна левая ветвь, то в правый угол и наоборот. Нужно, чтобы все ветви дерева были на одом уровне. К сожалению не знаю за что взяться.
Заранее благодарю!

[setare]

Я знаю, что надо использовать процедуры line and circle, но как зделать так, чтобы они соединились и двигались? Главный вопрос в этом!

[klem4]

Посмотри вот это, может поможет : http://pascal.dax.ru/?lessons&id=2&page=1

кстати, почему ДВОИЧНОЕ ?

Сообщение отредактировано: klem4 - 22.04.2005 22:07

[setare]

Двоичное дерево, потому что из главного узла выходят только две ветви и так до конца. Спасибо за ссылку. Понимаете, проблема как раз в том, что я никак не могу понять как использовать все это и написать процедуру. Я знаю, что надо использовать цикл для рисовании окружностей и ветвей. Но как можно соединить их? Знаю, что нужно 640 разделить на глубину +1, а 480 на ширину +1, тобы найти их место расположение. А как двигать первый узел? Каким образом прибавлять dx & dy? Половина алгоритма мне чуть-чуть ясна, а как реализовать нет. Я не хочу, чтобы вы думали, что я только жду готовую решенную задачу и все. У меня трудности с паскалем, сама я не очень в нем разбираюсь, а мне никто не обьясняет. Поэтому последняя надежла на вас!

[klem4]

Ну вот может это натолкнет тебя на мысли :
вот картина http://forum.pascal.net.ru/index.php?act=A...ype=post&id=408
Художник Volvo :D

[setare]

Здравствуйте! У меня возникла проблема, которую я никак не могу решить без вашей помощи! Нам нужно реализовать работу с деревом и нарисовать в дальнейшем это дерево в модуле граф. Вопрос состоит в том как это сделать, а именно нарисовать дерево? К сожалению, я не знаю даже с чего начать. Не могли бы вы мне помочь? Процедуры и функции модуля я знаю, но как их можно использовать в этой программе? Также рисование дерева нужно связать с глубиной и шириной дерева. Но каким образом? Пожалуйста, напишите мне эту процедуру. Я уже 3 недели над этим парюсь и все безысходно. Помогите отстающей в паскале студентке!

Давайте не будем дублировать темы...

Сообщение отредактировано: volvo - 2.05.2005 14:00

[setare]

Хорошо, дублировать темы я не буду! Извините! :D

[volvo]

К сожалению, я не знаю даже с чего начать. Не могли бы вы мне помочь?

setare, а Вы когда-нибудь пробовали выводить дерево в текстовом режиме? Да, да... Не в графическом, а в текстовом, но так чтобы оно читалось сверху вниз, а не слева направо... Попробуйте. Если выводится - то просто поменять вывод текста на вывод графики. Главное - алгоритм.

[setare]

Если я б знала как выводить дерево в текстовом режиме, то я бы сто процентов вывела бы его в графе и не обращалась бы к вам. Проблема вся заключается как раз в том, что я не знаю как это сделать.

[volvo]

Если я б знала как выводить дерево в текстовом режиме, то я бы сто процентов вывела бы его в графе и не обращалась бы к вам.

Ну, начнем с того, что ДАЖЕ если я Вам и дам процедуру вывода дерева в текстовом режиме, ее ОЧЕНЬ непросто будет заставить стабильно работать в графике. Там будет достаточно проблем.

Вы просили совет - я дал Вам совет - не пытайтесь начинать с графики. Делайте для начала в тексте.

[setare]

Большое спасибо за совет! Он мне очень очень помог!

[setare]

Можно хотя бы вы проверите мой алгоритм, если уж вы так не хотите мне помочь; при том всего лишь один раз я вас попросила написать процедуру?
1)Нужно поссчитать ширину дерева
2)разделить экран:высоту на глубину+1, а ширину на ширину+1 чтобы найти местоположение дерева
3)После этого найти пересечение столбцов и строк на экране, в которых будут находиться узлы дерева. Каждый узел должен находиться в своем отдельном столбце и строке.
4)Нарисовать окружности
5)поссчитать центры окружностей и провести к ним линнии
6)передвигать дерево в соответствии количества веток(если одна левая, то вправо и тд)
Проблема в том, что я не знаю как написать 3 5 6 пункты. Вот так

[volvo]

setare,
:no: Я пошел другим путем:
допустим, что дерево задано так:

PTNode = ^TNode;
TNode = Record;
  Data: Char;
  right, left: PTNode;
End;

Тогда для того, чтобы его распечатать (я пока про текстовый режим, про графический скажу потом, если такой алгоритм подойдет ) делаем так (обычный нисходящий проход - корень, правое поддерево, левое поддерево):

procedure print_tree(root: PTNode);
  const
    start_x = 40;
    start_y = 1;

    delx = 4;
    dely = 2;

  procedure print_node(T: PTNode; level: integer; x_pos: integer);
  var pos_x, pos_y: integer;
  begin
    pos_x := x_pos;
    pos_y := start_y + pred(level) * dely;

    gotoxy(pos_x, pos_y);
    writeln(T^.data);

    if T^.right <> nil then begin
      gotoxy(pos_x + (delx div 2), pos_y + 1); writeln('\');
      print_node(T^.right, level + 1, x_pos + delx);
    end;
    if T^.left <> nil then begin
      gotoxy(pos_x - (delx div 2), pos_y + 1); writeln('/');
      print_node(T^.left, level + 1, x_pos - delx);
    end;
  end;

begin
  print_node(root, 1, start_x)
end;

Результат работы этой процедуры для содержимого "g l f k e h v r s a m t" имеет вид:

А вот для графики - можно попробовать определить

start_x := getmaxx div 2;
start_y := 10; { это значение уже надо подбирать }
delx := ... { эти тоже подбираются }
dely := ...  

и заменить WriteLn на OutTextXY и Circle, главное что известны координаты и смещения узлов одно относительно другого.

Но я говорил, что будут проблемы - они есть. Масштабирование. Если будет достаточно разветвленное дерево, оно просто не поместится на экран, а при уменьшении радиуса окружности (представляющей узел) в нее просто не поместится значение узла. Так что не все так просто... Но для не очень разветвленных деревьев должно получиться неплохо... Попробуйте, если что не получится - я помогу... :yes:

[Atos]

setare,a обязательно ли рисовать имеено кружки? С прямоугольниками всё было бы намного проще - линии, соединяющие их, выходили бы из середины нижнего основания и входили бы соответственно в середину верхнего.

{Сам как раз сегодня ночью думал над выводом АВЛ-дерева в Дельфи. Впрочем, я ставлю задачу проще: на экран выводится определённое ограниченное количество узлов, строго в определённом месте экрана, ну и можно передвигаться по дереву, выделяя один из узлов}

[volvo]

a обязательно ли рисовать имеено кружки? С прямоугольниками всё было бы намного проще - линии, соединяющие их, выходили бы из середины нижнего основания и входили бы соответственно в середину верхнего.

Ну так и с кружками особых проблем в этом смысле нет
Вот что у меня получилось:

[setare]

Здравствуйте! Спасибо большое за обьяснение! Вот только возник вопрос. Я вместо букв ввела цифры. Все рисуется великолепно, кроме вот этого случая:
4 2 6 1 3 5 7. В этом случая она не рисует цифру 5, кот должна распологаться в левом поддереве после 6. Прграмма просто связывает 2 и 6 с 3, что мы от нее и не просили. Что тогда делать в этом случае?

[volvo]

Все рисуется великолепно, кроме вот этого случая:
4 2 6 1 3 5 7. В этом случая она не рисует цифру 5, кот должна распологаться в левом поддереве после 6. Прграмма просто связывает 2 и 6 с 3, что мы от нее и не просили. Что тогда делать в этом случае?

:no: Не только в этом случае... В любом случае, когда есть симматричные ветви слева и справа - будет отображаться только левая. Правая же будет ей затерта. Для того, чтобы этого не происходило, придется переписывать метод Print... Вот я тут набросал, но не проверял досконально. Можете посмотреть

Реализация перенесена в FAQ: Динамические структуры - Деревья

procedure TTree.print;
begin
  PrintTreeGraph(root)
end;

Одно НО ! Если дерево будет сильно разбалансированное или большое по размеру, то начнутся новые проблемы: при возрастании глубины расположения узла место отводимое на него и его потомков (в ширину) достаточно быстро уменьшается, и узлы начнут накладываться один на другой... Я даже не знаю, можно ли это как-то решить, кроме использования сбалансированных деревьев.

[setare]

Спасибо! Извините, что я побеспокоила вас в ваш праздник!
Но есть маленький вопросик: а что означают
C+btw, Center(C+btw, R-btw), R-btw
и
pos_y := start_y + pred(level) * dely
и если будет только одна ветвь, то будет ли дерево при этом перемещаться или вправо или влево в зависимости от того кокое поддерево есть?

[setare]

Кстати, а вы не используете глубину и ширину дерева? Для того, чтобы узнать месторасположение первого главного узла? Тут не надо делить длину экрана на глубину и ширину на ширину дерева? И вообще можно ли таким образом все это сделать? :p2: Это просто вопрос. А потом с помощью dx & dy перемещать дерево или вправо или влево?

[volvo]

Но есть маленький вопросик: а что означают
C+btw, Center(C+btw, R-btw), R-btw
и
pos_y := start_y + pred(level) * dely

Это функции, переменные и константы, они описаны выше по тексту.

и если будет только одна ветвь, то будет ли дерево при этом перемещаться или вправо или влево в зависимости от того кокое поддерево есть?

Нет. Ничего никуда перемещаться не будет, все будет отрисовываться точно так же, как и при двух ветвях, но одна из них будет пустой... Я просто редко пользуюсь обычными деревьями, чаще AVL, а там дерево сбалансировано, и с ним легче...