Конструктор учебных заданий для электронного задачника Programming Taskbook - 28 стр.

UptoLike

ВУЗ: 

ЮФУ | Ростов-на-Дону

Составители: 

Рубрика: 

28
Для деревьев, в отличие от линейных структур, нулевые поля связи не отобра-
жаются. Если поле Left или Right равно nil, то на изображении дерева у соответству-
ющей вершины просто отсутствует левая или правая связь.
Максимальное число вершин в дереве равно 18; это объясняется тем, что каждая
вершина занимает 4 позиции экранной строки и, кроме того, 4 начальных позиции от-
водятся под дополнительную информацию (номера уровней). Поэтому, с учетом того,
что ширина экранной строки в окне задачника равна 78, вписать в нее можно только
дерево с не более чем 18 вершинами. Впрочем, в заданиях рекомендуется использо-
вать не более 16 вершин, начиная вывод дерева с 11 экранной позиции; это дает воз-
можность использовать левую часть строк для отображения других данных, напри-
мер, указателей, связанных с данным деревом.
Количество уровней дерева ограничивается только количеством его вершин и,
таким образом, может достигать 18. В соответствии с общепринятой практикой уров-
ни дерева нумеруются от 0. Номер уровня отображается в левой части области, отве-
денной под изображение дерева; он выделяется цветом и отделяется от изображения
дерева двоеточием.
Если количество уровней превышает число экранных строк, выделенных для
отображения дерева, то для дерева становится возможной прокрутка, подобная про-
крутке файловых данных (точнее, данных из текстовых файлов, поскольку для де-
ревьев, как и для текстовых файлов, прокрутка выполняется в вертикальном направ-
лении). На возможность прокрутки указывают дополнительные символы, которые
изображаются слева от номера уровня. Символ «стрелка вверх», расположенный на
первой экранной строке, отведенной для отображения дерева, означает, что изобра-
жение дерева можно пролистать вверх, а символ «стрелка вниз», расположенный на
последней экранной строке, отведенной для отображения дерева, означает, что изо-
бражение дерева можно пролистать вниз (см. пример 8).
Обычно первая строка, отводимая под изображение дерева, содержит его корень
и помечается слева числом 0 (нулевой уровень дерева). Единственная ситуация, когда
это правило нарушается, связана с ошибочным формированием бинарного дерева с
обратной связью в случае, если поле Parent корня не содержит значение nil. В этой
ситуации перед строкой с изображением корня дерева помещается еще одна строка, в
которой над корнем изображается красная звездочка — признак ошибки.
Изображение дерева может также содержать строки, расположенные ниже по-
следнего уровня; эти строки могут потребоваться для вывода имен указателей, свя-
занных с вершинами-листьями, расположенными на последнем уровне, а также для
вывода звездочек, отмечающих ошибочные ссылки Left или Right для вершин, распо-
ложенных на последнем уровне дерева. Заметим, что ссылка считается ошибочной в
двух случаях:
• если она содержит неверный адрес,
• если она ссылается на вершину, которую нельзя отобразить, поскольку для
этой вершины не предусмотрено экранного места.
В частности, звездочки обязательно будут выведены при попытке отобразить на
экране дерево с количеством вершин, превышающим 18.
Приведем примеры изображений линейных списков и деревьев. В этих примерах
предполагается, что текущим языком программирования является Паскаль; для дру-
гих языков вместо nil используются обозначения нулевых указателей (или нулевых

Страницы