Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Java [игнор отключен] [закрыт для гостей] / Отрисовка бинарного дерева. / 10 сообщений из 10, страница 1 из 1
12.10.2006, 15:16:03
    #34050887
AlexeyShponarsky
AlexeyShponarsky
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Отрисовка бинарного дерева.
Всем доброго дня!
Есть бинарное дерево заполненное данными. Нужно его отобразить на плоскости что бы ветви не пересекались. Может кто это уже делал, может придумает) Нужен не пример кода а описание алгоритма.
Спасибо.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
12.10.2006, 16:54:45
    #34051354
Leonidv
Leonidv
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Отрисовка бинарного дерева.
Высчитываем ширину дерева по количество его листьев нижнего уровня. И рисуем, соответственно, снизу вверх. Понятно, что в бинарном дереве количество элементо в на верхнем уровне (корень сверху) меньше, чем количество элементов на верхнем уровне.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
12.10.2006, 17:48:18
    #34051605
AlexeyShponarsky
AlexeyShponarsky
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Отрисовка бинарного дерева.
Но на нижнем уровне может быть и два лепестка.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
12.10.2006, 17:55:40
    #34051647
AlexeyShponarsky
AlexeyShponarsky
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Отрисовка бинарного дерева.
А если у нас например в дереве 10 элеметов и каждое следующее будет лувым лепестком предыдущего, тогда у нас получиться ширина 10 лепестков а снизу всего один будет...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
12.10.2006, 19:27:11
    #34051914
Leonidv
Leonidv
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Отрисовка бинарного дерева.
Согласен. Тогда максимальную ширину можно получить по формуле 2 * tree.deep().
Дерево нарисовать можно, но будет не красиво. Интересная задачка :)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
12.10.2006, 19:29:16
    #34051920
Leonidv
Leonidv
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Отрисовка бинарного дерева.
LeonidvСогласен. Тогда максимальную ширину можно получить по формуле 2 * tree.deep().
Дерево нарисовать можно, но будет не красиво. Интересная задачка :)
Блин, почему править сообщения нельзя '(
2^(tree.deep()-1).
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
12.10.2006, 19:57:35
    #34051968
AlexeyShponarsky
AlexeyShponarsky
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Отрисовка бинарного дерева.
Ширина дерева это 2 в степени максимальной глубины дерева.
Сегодня ночью буду что-то еще думать.
Помогайте. :)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
12.10.2006, 20:38:43
    #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
| Ответить | Цитировать | Написать  
13.10.2006, 12:03:20
    #34053116
xxx2
xxx2
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Отрисовка бинарного дерева.
http://www.research.att.com/~john/Grappa/
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
13.10.2006, 15:11:29
    #34053966
AlexeyShponarsky
AlexeyShponarsky
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Отрисовка бинарного дерева.
Ура! придумал, вобщем у меня схема такова:
Узел:
Код: plaintext
1.
2.
3.
4.
 1 )указатель на левую ветку;
 2 )указатель на правую ветку;
 3 )указатель на отца;
 4 )уровень глубины (где находится узел)

Схема рисования:
Задача сводится до того что бы найти расстояние ребра от от узла до узла. Верхнее растояние будет равно количеству уровней глубины дерева умноженное на расстояние между узлами самого нижнего уровня(максимального). Записываем это значение в корень. Рисуем первую вершину(корень). Дальше рекурсивно вызываем эту же функцию для всех узлов. Расстояние вычисляем делением предыдущего расстояния на 2. И полусается красивенькое дерево построенное так сказать по шаблону.
Вот и весь алгоритм :)
Спасибо всем)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Форумы / Java [игнор отключен] [закрыт для гостей] / Отрисовка бинарного дерева. / 10 сообщений из 10, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение  
Полит. конфиден.  
созд. / загр.: 1234ms
Закрыть
start [/forum/topic.php?fid=59&mobile=1&tid=2147817]:
 0ms
get settings:
 6ms
get forum list:
 10ms
check forum access:
 2ms
check topic access:
 2ms
track hit:
 950ms
get topic data:
 13ms
get forum data:
 3ms
get page messages:
 50ms
get tp. blocked users:
 2ms
others: 196ms
total:  1234ms
x
x
Закрыть


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