Если вы знаете глубину дерева, то есть количество уровней , вы можете рассчитать максимальное количество узлов на последнем уровне (которое равно n 2 для n = количество уровней - 1, 1 элемент, если у вас есть только рут). Если вы также знаете ширину элементов (например, если у вас не более двухзначных чисел, каждый элемент будет иметь ширину 2), вы можете рассчитать ширину последнего уровня:
((number of elements - 1) * (element width + spacing) + element width).
На самом деле вышеприведенный абзац не имеет значения. Все, что вам нужно, это глубина дерева, то есть максимальный уровень, который должен отображаться. Однако, если дерево разреженное, то есть присутствуют не все элементы последнего уровня и, возможно, выше, вам необходимо получить позицию отображаемого узла, чтобы соответствующим образом адаптировать отступ / интервал для этого случая.
В ходе итерации предварительного заказа вы можете рассчитать отступы и интервалы между элементами на каждом уровне. Формула для отступа будет выглядеть следующим образом: 2 (максимальный уровень - уровень) - 1 и интервал: 2 (максимальный уровень - уровень + 1) - 1 (уровень основан на 1)
Пример:
1
2 3
4 5 6 7
8 9 A B C D E F
В этом дереве количество уровней равно 4. Интервал на последнем уровне равен 1, тогда как отступ равен 0. Вы получите следующие значения:
- уровень 1:
indent = 7: (2 (4-1) - 1 = 2 3 - 1 = 8 - 1 = 7) - первый уровень, поэтому расстояние не имеет значения
- уровень 2:
indent = 3: (2 (4-2) - 1 = 2 2 - 1 = 4 - 1 = 3) spacing = 7 (2 (4-1) - 1 = 2 3 - 1 = 8 - 1 = 7)
- уровень 3:
indent = 1: (2 (4-3) - 1 = 2 1 - 1 = 2 - 1 = 1) spacing = 3 (2 (4-2) - 1 = 2 2 - 1 = 4 - 1 = 3)
- уровень 4:
indent = 0: (2 (4-4) - 1 = 2 0 - 1 = 1 - 1 = 0) spacing = 1: (2 (4-3) - 1 = 2 1 - 1 = 2 - 1 = 1)
Обратите внимание, что на последнем уровне у вас всегда будет интервал 1 * ширины элемента. Таким образом, для максимальной ширины элемента 3 (например, 3-значных чисел) у вас будет интервал 3 на последнем уровне, чтобы получить некоторое выравнивание верхних уровней.
Редактировать : Для вашего красивого отпечатка вам просто нужно рассчитать отступ как width element * level, где уровень будет начинаться с нуля. Затем, если узел не является листом, нарисуйте его с открывающим паратезом впереди и закрывающим парантезом после рисования потомков, если это лист, просто нарисуйте его, а если лист отсутствует, нарисуйте двойной парантхис.
Таким образом, вы получите что-то вроде этого:
public void printSubtree( int indent, node ) {
for( int i = 0; i < indent; ++i) {
System.out.print(" ");
}
if( inner node) {
System.out.println("(" + value);
printSubtree(indent + elem width, left child); //this is a recursive call, alternatively use the indent formula above if you don't use recursion
printSubtree(indent + elem width, right child);
//we have a new line so print the indent again
for( int i = 0; i < indent; ++i) {
System.out.print(" ");
}
System.out.println(")");
} else if( not empty) {
System.out.println(value);
} else { //empty/non existing node
System.out.println("()");
}
}