Изображение бинарного дерева

[temp]

Подскажите, как изобразить на экране бинарное дерево (узлы - кружочки), чтобы оно было максимально ужато, но узлы не перекрывались.

[Werwolf]

Если сверху вниз, то посередине рисуем вершину, а потом на следующей строчке рекурсивно левое и правое поддерево на соответствующих половинах.

[temp]

Тогда на третьем, четвертом уровне начинают пересекаться. Может есть алгоритм, чтобы подбирать приращения по x и y, в зависимости от высоты дерева. чтобы, если дерево полное, то листы стоят рядом, а размещение их предков в зависимости от расстояния между листами?

[Werwolf]

Ну можно пробовать танцевать от листов, но я предлагаю несколько по другому. Вывод на всю ширину экрана трудностей не составляет, но тогда невысокое дерево далеко не ужато. Значит в зависимости от высоты дерева считаем при какой ширине дерево ужато и в этой области рисуем.
Попробую на Паскале реализовать эту идею.

[незваный гость]

Самое простое решение -- рекурсивно пройти по дереву и подсчитать ширину поодерева для каждого узла. После чего рисование становится заметно проще.

Остаются, тем не менее, вопросы эстетики, что делать, если негде хранить ширину, и многие другие.

[temp]

Цитата:

Остаются, тем не менее, вопросы эстетики, что делать, если негде хранить ширину, и многие другие.

А сделать ширину членом класса узла - это сильно неэстетично или допустимо?

[maxal]

А почему бы не воспользоваться готовым решением: http://graphviz.org/ ?

[temp]

Цитата:

А почему бы не воспользоваться готовым решением: http://graphviz.org/ ?

Программа-то хорошая, но мне нужен алгоритм для рисования дерева в своей программе.

Кстати оттуда наткнулся на интересную книжку по рисованию графов http://www.cs.brown.edu/~rt/papers/gd-tutorial/gd-constraints.pdf Попробую разобраться

[незваный гость]

temp писал(а):

А сделать ширину членом класса узла - это сильно неэстетично или допустимо?

Разумеется, эстетичо и допустимо. Эстетика, о которой я говорил -- это как дерево "смотрится" на экране, сильно ли оно перекошено -- то есть, чисто вопросы восприятия картинки человеком.