ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Java [игнор отключен] [закрыт для гостей] / Отрисовка бинарного дерева.
10 сообщений из 10, страница 1 из 1
Отрисовка бинарного дерева.
    #34050887
AlexeyShponarsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AlexeyShponarsky
Гость
Всем доброго дня!
Есть бинарное дерево заполненное данными. Нужно его отобразить на плоскости что бы ветви не пересекались. Может кто это уже делал, может придумает) Нужен не пример кода а описание алгоритма.
Спасибо.
...
Рейтинг: 0 / 0
12.10.2006, 15:16:03
| Ответить | Цитировать | Написать  
Отрисовка бинарного дерева.
    #34051354
Leonidv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonidv
Участник
Высчитываем ширину дерева по количество его листьев нижнего уровня. И рисуем, соответственно, снизу вверх. Понятно, что в бинарном дереве количество элементо в на верхнем уровне (корень сверху) меньше, чем количество элементов на верхнем уровне.
...
Рейтинг: 0 / 0
12.10.2006, 16:54:45
| Ответить | Цитировать | Написать  
Отрисовка бинарного дерева.
    #34051605
AlexeyShponarsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AlexeyShponarsky
Гость
Но на нижнем уровне может быть и два лепестка.
...
Рейтинг: 0 / 0
12.10.2006, 17:48:18
| Ответить | Цитировать | Написать  
Отрисовка бинарного дерева.
    #34051647
AlexeyShponarsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AlexeyShponarsky
Гость
А если у нас например в дереве 10 элеметов и каждое следующее будет лувым лепестком предыдущего, тогда у нас получиться ширина 10 лепестков а снизу всего один будет...
...
Рейтинг: 0 / 0
12.10.2006, 17:55:40
| Ответить | Цитировать | Написать  
Отрисовка бинарного дерева.
    #34051914
Leonidv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonidv
Участник
Согласен. Тогда максимальную ширину можно получить по формуле 2 * tree.deep().
Дерево нарисовать можно, но будет не красиво. Интересная задачка :)
...
Рейтинг: 0 / 0
12.10.2006, 19:27:11
| Ответить | Цитировать | Написать  
Отрисовка бинарного дерева.
    #34051920
Leonidv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonidv
Участник
LeonidvСогласен. Тогда максимальную ширину можно получить по формуле 2 * tree.deep().
Дерево нарисовать можно, но будет не красиво. Интересная задачка :)
Блин, почему править сообщения нельзя '(
2^(tree.deep()-1).
...
Рейтинг: 0 / 0
12.10.2006, 19:29:16
| Ответить | Цитировать | Написать  
Отрисовка бинарного дерева.
    #34051968
AlexeyShponarsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AlexeyShponarsky
Гость
Ширина дерева это 2 в степени максимальной глубины дерева.
Сегодня ночью буду что-то еще думать.
Помогайте. :)
...
Рейтинг: 0 / 0
12.10.2006, 19:57:35
| Ответить | Цитировать | Написать  
Отрисовка бинарного дерева.
    #34052023
NotGonnaGetUs
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
NotGonnaGetUs
Участник
AlexeyShponarskyВсем доброго дня!
Есть бинарное дерево заполненное данными. Нужно его отобразить на плоскости что бы ветви не пересекались. Может кто это уже делал, может придумает) Нужен не пример кода а описание алгоритма.
Спасибо.

Как угодно. Н-р, обойти дерево к глубину, параллельно его рисуя.

Грубо это формулируется так:
Код: plaintext
1.
2.
3.
4.
5.
6.
Нарисовать_дерево (дерево) :  //возвращает ширину рисунка
      Нарисовать_узел (дерево),
      Вертикальная_полосочка,
      Нарисовать_дерево(дерево->левое),
      Горизонтальная_полосочка, //в зависимости от ширины левого дерева
      Нарисовать_дерево(дерево->правое);

При таком алгоритме дерево будет выглядеть примерно так (в скобочкам последовательность просмотра вершин):

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
1 (1)---------- 2 (6) -------------3 (10) 
|               |                  |  
2 (2)           3 (7) -----4 (9)   4 (11) -- 5 (13)
|               |                  |
3 (3)--4 (5)    4 (8)              5 (12)
|
4 (4)
...
Рейтинг: 0 / 0
12.10.2006, 20:38:43
| Ответить | Цитировать | Написать  
Отрисовка бинарного дерева.
    #34053116
xxx2
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
xxx2
Гость
http://www.research.att.com/~john/Grappa/
...
Рейтинг: 0 / 0
13.10.2006, 12:03:20
| Ответить | Цитировать | Написать  
Отрисовка бинарного дерева.
    #34053966
AlexeyShponarsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AlexeyShponarsky
Гость
Ура! придумал, вобщем у меня схема такова:
Узел:
Код: plaintext
1.
2.
3.
4.
 1 )указатель на левую ветку;
 2 )указатель на правую ветку;
 3 )указатель на отца;
 4 )уровень глубины (где находится узел)

Схема рисования:
Задача сводится до того что бы найти расстояние ребра от от узла до узла. Верхнее растояние будет равно количеству уровней глубины дерева умноженное на расстояние между узлами самого нижнего уровня(максимального). Записываем это значение в корень. Рисуем первую вершину(корень). Дальше рекурсивно вызываем эту же функцию для всех узлов. Расстояние вычисляем делением предыдущего расстояния на 2. И полусается красивенькое дерево построенное так сказать по шаблону.
Вот и весь алгоритм :)
Спасибо всем)
...
Рейтинг: 0 / 0
13.10.2006, 15:11:29
| Ответить | Цитировать | Написать  
10 сообщений из 10, страница 1 из 1
Форумы / Java [игнор отключен] [закрыт для гостей] / Отрисовка бинарного дерева.
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=59&msg=34051914&tid=2147817]:
 0ms
get settings:
 6ms
get forum list:
 18ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 169ms
get topic data:
 11ms
get forum data:
 2ms
get page messages:
 57ms
get tp. blocked users:
 1ms
others: 203ms
total:  473ms
созд. / загр.: 473ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]