Помощь - Поиск - Пользователи - Календарь
Полная версия: Двоичное дерево
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
setare
Здравствуйте! У меня большая проблема. Не могли бы вы подсказать как можно нарисовать дерево в модуле граф. Нужно его нарисовать так, чтобы вершина этого дерева перемещалась в зависимости от того, сколько там веток. Если одна левая ветвь, то в правый угол и наоборот. Нужно, чтобы все ветви дерева были на одом уровне. К сожалению не знаю за что взяться.
Заранее благодарю!
setare
Я знаю, что надо использовать процедуры line and circle, но как зделать так, чтобы они соединились и двигались? Главный вопрос в этом!
klem4
Посмотри вот это, может поможет : http://pascal.dax.ru/?lessons&id=2&page=1

кстати, почему ДВОИЧНОЕ ? blink.gif huh.gif
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 недели над этим парюсь и все безысходно. Помогите отстающей в паскале студентке! unsure.gif

Давайте не будем дублировать темы...
setare
Хорошо, дублировать темы я не буду! Извините! :D
volvo
Цитата(setare @ 2.05.05 9:55)
К сожалению, я не знаю даже с чего начать. Не могли бы вы мне помочь?


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

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

Вы просили совет - я дал Вам совет - не пытайтесь начинать с графики. Делайте для начала в тексте.
setare
Большое спасибо за совет! Он мне очень очень помог! sad.gif
setare
Можно хотя бы вы проверите мой алгоритм, если уж вы так не хотите мне помочь; при том всего лишь один раз я вас попросила написать процедуру?
1)Нужно поссчитать ширину дерева
2)разделить экран:высоту на глубину+1, а ширину на ширину+1 чтобы найти местоположение дерева
3)После этого найти пересечение столбцов и строк на экране, в которых будут находиться узлы дерева. Каждый узел должен находиться в своем отдельном столбце и строке.
4)Нарисовать окружности
5)поссчитать центры окружностей и провести к ним линнии
6)передвигать дерево в соответствии количества веток(если одна левая, то вправо и тд)
Проблема в том, что я не знаю как написать 3 5 6 пункты. Вот так sad.gif unsure.gif
volvo
setare,
:no: Я пошел другим путем:
допустим, что дерево задано так:
PTNode = ^TNode;
TNode = Record;
Data: Char;
right, left: PTNode;
End;

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

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
Цитата(Atos @ 3.05.05 6:02)
a обязательно ли рисовать имеено кружки? С прямоугольниками всё было бы намного проще - линии, соединяющие их, выходили бы из середины нижнего основания и входили бы соответственно в середину верхнего.


Ну так и с кружками особых проблем в этом смысле нет smile.gif
Вот что у меня получилось:
setare
Здравствуйте! Спасибо большое за обьяснение! Вот только возник вопрос. Я вместо букв ввела цифры. Все рисуется великолепно, кроме вот этого случая:
4 2 6 1 3 5 7. В этом случая она не рисует цифру 5, кот должна распологаться в левом поддереве после 6. Прграмма просто связывает 2 и 6 с 3, что мы от нее и не просили. Что тогда делать в этом случае?
volvo
Цитата(setare @ 4.05.05 17:09)
Все рисуется великолепно, кроме вот этого случая:
4 2 6 1 3 5 7. В этом случая она не рисует цифру 5, кот должна распологаться в левом поддереве после 6. Прграмма просто связывает 2 и 6 с 3, что мы от нее и не просили. Что тогда делать в этом случае?

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

Реализация перенесена в 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: Это просто вопрос. smile.gif А потом с помощью dx & dy перемещать дерево или вправо или влево?
volvo
Цитата(setare @ 4.05.05 18:45)
Но есть маленький вопросик: а что означают
C+btw, Center(C+btw, R-btw), R-btw
и
pos_y := start_y + pred(level) * dely

Это функции, переменные и константы, они описаны выше по тексту. smile.gif
Цитата(setare @ 4.05.05 18:45)
и если будет только одна ветвь, то будет ли дерево при этом перемещаться или вправо или влево в зависимости от того кокое поддерево есть?

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

Кстати, а вы не используете глубину и ширину дерева? Для того, чтобы узнать месторасположение первого главного узла? Тут не надо делить длину экрана на глубину и ширину на ширину дерева? И вообще можно ли таким образом все это сделать? :p2: Это просто вопрос. smile.gif А потом с помощью dx & dy перемещать дерево или вправо или влево?
volvo
Цитата(setare @ 4.05.05 19:03)
Нет я имею ввиду именно btw и dely

Btw это половина радиуса окружности (вообще-то это от слова Between - то есть расстояние между чем-то) smile.gif Я так подумал, что если уйти влево и вправо на половину радиуса, это предотвратит наложение узлов...
А dely - раньше она называлась DeltaY, то есть - на сколько смещается следующий уровень относительно предыдущего по вертикали...

Цитата(setare @ 4.05.05 19:03)
Кстати, а вы не используете глубину и ширину дерева? Для того, чтобы узнать месторасположение первого главного узла?

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

Во вторых, в моем методе отрисовка начинается сразу же, без всяких предварительных вычислений, ведь это может занять какое-то время.

И в третьих это же не истина в последней инстанции, и даже не окончательная версия программы, это только второй набросок (первый, к сожалению был еще менее удачным). Можно попробовать и по-другому... :yes:
setare
Например, как?
volvo
Не знаю. Надо думать. Но задачу всегда можно решить несколькими способами, поэтому другой способ должен быть.
setare
Спасибо большое и еще раз извините за беспокойство! Но я думаю, что мне опять придется побеспокоить вас по этому вопросу! rolleyes.gif
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.