Перечислим другие обозначения, имеющие тот же смысл, что и для линейных структур:
если вершина дерева должна быть создана в программе учащегося, то данная вершина выделяется слева и справа точками, например, .23. (для этого используется процедура SetNewNode); если в дереве, преобразованном программой учащегося, существующие вершины располагаются не на своих местах, то они заключаются в скобки: (23); если в исходном дереве требуется разрушить одну или несколько вершин, то эти вершины выделяются более бледным цветом (а в случае, если программа учащегося не освободит память, занимаемую этими вершинами, они будут выделены красным цветом); если переход по ссылке Left или Right для данной вершины дерева невозможен, то, как и в случае линейных структур, это отмечается красными звездочками, которые, однако, изображаются не рядом с данной вершиной, а ниже вершины (что подчеркивает тот факт, что ошибка возникла при попытке перехода на следующий уровень дерева). Для деревьев, в отличие от линейных структур, нулевые поля связи не отображаются. Если поле Left или Right равно нулевому указателю, то на изображении дерева у соответствующей вершины просто отсутствует левая или правая связь.
Максимальное число вершин в дереве равно 18; это объясняется тем, что каждая вершина занимает 4 позиции экранной строки и, кроме того, 4 начальных позиции отводятся под дополнительную информацию (номера уровней дерева). Поэтому, с учетом того, что ширина экранной строки равна 78, вписать в нее можно только дерево с не более чем 18 вершинами. Впрочем, в заданиях рекомендуется использовать не более 16 вершин, начиная вывод дерева с 11 экранной позиции; это дает возможность использовать левую часть строк для отображения других данных, например, указателей, связанных с данным деревом.
Количество уровней дерева ограничивается только количеством его вершин и, таким образом, может достигать 18. В соответствии с общепринятой практикой, уровни дерева нумеруются от 0. Номер уровня отображается в левой части области, отведенной под изображение дерева; он выделяется цветом и отделяется от изображения дерева двоеточием.
Если количество уровней превышает число экранных строк, выделенных для отображения дерева, то для дерева становится возможной прокрутка, подобная прокрутке файловых данных (точнее, данных из текстовых файлов, поскольку для деревьев, как и для текстовых файлов, прокрутка выполняется в вертикальном направлении). На возможность прокрутки указывают дополнительные символы, которые изображаются слева от номера уровня. Символ стрелка вверх", расположенный на первой экранной строке, отведенной для отображения дерева, означает, что изображение дерева можно пролистать вверх, а символ "стрелка вниз", расположенный на последней экранной строке, отведенной для отображения дерева, означает, что изображение дерева можно пролистать вниз (см. пример 8). В режиме окна с динамической компоновкой все деревья отображаются полностью, поэтому отдельная прокрутка для них не требуется.
Обычно первая строка, отводимая под изображение дерева, содержит его корень и помечается слева числом 0 (нулевой уровень дерева). Единственная ситуация, когда это правило нарушается, связана с ошибочным формированием бинарного дерева с обратной связью в случае, если поле Parent корня не содержит значение nil. В этой ситуации перед строкой с изображением корня дерева помещается еще одна строка, в которой над корнем изображается красная звездочка -- признак ошибки.
Изображение дерева может также содержать строки, расположенные ниже последнего уровня; эти строки могут потребоваться для вывода имен указателей, связанных с вершинами-листьями, расположенными на последнем уровне, а также для вывода звездочек, отмечающих ошибочные ссылки Left или Right для вершин, расположенных на последнем уровне дерева. Заметим, что ссылка считается ошибочной в двух случаях:
если она содержит неверный адрес, если она ссылается на вершину, которую нельзя отобразить, поскольку для этой вершины не предусмотрено экранного места.
В частности, звездочки обязательно будут выведены при попытке отобразить на экране дерево с количеством вершин, превышающим 18.
Приведем примеры изображений линейных списков и деревьев. В этих примерах предполагается, что в качестве текущего языка задачника выбран язык Pascal; для других языков вместо nil используются обозначения нулевых указателей или нулевых объектов -- (см. описание процедуры SetObjectStyle), соответствующие этим языкам.
Пример 1
P1
24 - 23 >nil
Первый элемент данного списка связан с указателем P1; список содержит два элемента и является односвязным: на это указывает символ -" между элементами, означающий, что поле Next первого элемента (со значением 24) указывает на второй элемент (со значением 23). Поле Next второго элемента равно nil.
Пример 2
P1 P2
nil< 14 = 23 = 34 >nil
Данный список является двусвязным (двойная связь, использующая оба поля связи -- Next и Prev, -- обозначается знаком ="), причем в задании с этим списком связаны два указателя: P1 указывает на его первый, а P2 -- на его последний элемент.
Пример 3
P0
<< = 15 - 23 = 34 = >>
Данный список является двусвязным циклическим списком (на его цикличность указывают символы <<" и ">>"), однако одна из его связей отсутствует. А именно, элемент 23 (на который указывает указатель P0) не связан с предыдущим элементом 15, т. е. поле Prev элемента 23 содержит ошибочное значение (например, равно nil). При правильно разработанном задании подобная ситуация может возникнуть только для ошибочных списков, созданных в программе учащегося. Заметим, что связь в другом направлении (от 15 к 23) имеется, т. е. поле Next элемента 15 указывает на элемент 23.
Пример 4
PXPY
95 - 63 -.34.- >>
Данный список является односвязным циклическим списком. Он имеет две особенности. Во-первых, на элемент 95 указывают сразу два указателя (PX и PY), и, во-вторых, элемент 34 должен быть размещен в памяти процедурой New при выполнении задания (на это указывают обрамляющие его точки). Подобные элементы, естественно, могут содержаться только в результирующих списках. Они определяются с помощью процедуры SetNewNode.
Пример 5
Так выглядит на экране бинарное дерево глубины 4. С корнем этого дерева (поле Data которого равно 96) связан указатель P1.
Пример 6
Так выглядит на экране бинарное дерево с обратной связью (номера уровней на данной иллюстрации не указаны).
Пример 7
Так выглядит на экране дерево общего вида (номера уровней и имена связанных с деревом указателей на данной иллюстрации не указаны). В данном случае корень дерева 13 имеет три непосредственных потомка: вершины 71, 73 и 29. Напомним, что в дереве общего вида поле Left определяет первую (левую) дочернюю вершину, а поле Right -- очередную (правую) вершину-сестру.
Пример 8
Так выглядит на экране бинарное дерево с включенным режимом прокрутки. Дополнительной особенностью этого дерева является наличие точек около каждой его вершины. Это означает, что данное дерево является результирующим, причем память для всех его вершин должна быть выделена в программе учащегося.
procedure ShowPointer(NP: integer);
Процедура обеспечивает отображение указателя с номером NP при выводе текущего линейного списка или дерева. Например, ее вызов вида ShowPointer(1) обеспечил отображение указателя P1 в примерах 1, 2 и 5. Если указатель номер NP является нулевым, то вызов процедуры ShowPointer игнорируется без вывода сообщения об ошибке. Если указатель с номером NP не является нулевым и не связан ни с одним из элементов списка, то выводится сообщение об ошибке.