[Teen Idle.]

Привет
Пишу программу, которая выводит на экран бинарное дерево. Например:
____2___
__3___4_
5__6_7__8
Все бы ничего, написала, работает, но дерево кривовато Не подскажите, по какому принципу расставлять пробелы/отступы, чтобы все было ровно?

@темы: Вопрос, Алгоритм

Comments

Хз, но попробуйте табуляцию вместо пробелов.

[Co0L]

Моноширинный шрифт?

Co0L
ЛОгично

[Teen Idle.]

Допустим, шрифт моноширинный, интересует, по какому принципу определять количество пробелов
То есть если дерево "полное", все более-менее выглядит, а если какой-то "лист" отсутствует, то с кодом, который у меня сейчас - здравствуй, кривизна.

Ния
Если лист отсутсвует, заменяйте, например, его на пробел и действует, как если бы он был.
____2___
__3___4_
5____7__8

А вообще, тогда, напишите, что вы уже сделали, а что хотите доделать/исправить.

[Teen Idle.]

У меня сейчас пробелы расставляются по принципу:
пробел * (высота дерева - текущий уровень) + элемент
И так для всех элементов уровня.
Там, где нет листа, у меня просто пробелы. Видимо, что-то не то, потому что получается не совсем ровно, как я уже сказала.))

[Чи]

С тем же самым на втором курсе мучался

Пусть d - глубина дерева (если есть только корень, то d=0), а l - рассматриваемый уровень (для корня опять же l=0). Нарисуем полностью заполненное дерево глубины 4:

               0



       1               1


   2       2       2       2

 3   3   3   3   3   3   3   3
4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4

КО говорит, что шрифт нужен моноширинный. Также для удобства под каждый элемент дерева выделяем поле фиксированной длины (то есть если есть числа 1, 12 и 123, то пишем их как __1, _12 и 123) и берем наш "пробел" длиной, равной длине самого большого числа. В нашем случае все длиной 1.

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

Таким образом, на уровне l число пробелов до первого элемента равно 2^(d-l) - 1, а между элементами - такое же, как расстояние до первого элемента на уровне l-1.

Ну и чтоб уж совсем выпендриться красиво было, число пустых строк перед уровнем l делаем равным d-l

[Teen Idle.]

Медитируем на наше изображение дерева


Помедитировала, поняла, спасибо большое.))