Представление - дерево
Cтраница 1
 |
Дерево и его представление нумерацией связей. [1] |
Представление дерева с помощью метода нумерации связей компактно и основано на массиве, что облетает запись и чтение деревьев, представленных таким образом, из файлов. Операции над массивами выполняются быстрее, чем операции с указателями, необходимые при некоторых других представлениях. [2]
Представление дерева ( или леса) с использованием указателей, ведущих от предков к потомкам, довольно сложно, поскольку узел, имея не более чем одного отца, может в то же время иметь произвольно много сыновей. Другими словами, при таком представлении узлы должны различаться по размеру, что является определенным неудобством. [3]
Фамильный порядок представления дерева при последовательном распределении памяти отличается от прямого порядка представления тем, что при фамильном порядке опускаются RLINK, a LLINK. Узлы дерева при этом располагаются в порядке, реверсивном к концевому. [4]
Далее приведем определение расширенного представления дерева, которое является более удобным для реализации алгоритма унификации. [5]
Определение 4 - - Расширенное представление дерева терма есть дерево, в котором имя каждой вершины расширено целым числом, представляющим порядковый номер потомка для заданного родителя. [6]
Прежде чем приступать к рассмотрению примера, необходимо объяснить представление дерева анализа, которое используется этим фрагментом. Деревьям анализа сопоставляются скобочные записи, в которых узел представлен списком, где первый элемент есть имя узла, а остальные элементы суть представления составляющих этого узла. [7]
Программа, в которой реализованы идеи предыдущего раздела, показана на рис. 13.12. Прежде, чем мы перейдем к объяснению отдельных деталей этой программы, давайте рассмотрим тот способ представления дерева поиска, который в ней используется. [8]
Преимущество прошитого дерева заключается в том, что при тех же затратах памяти упрощаются алгоритмы его прохождения. На рис. 2.4 приведено представление дерева, показанного на рис. 2.3 в виде прошитого списка. [9]
Возьмем, говорит один из психологов, пример - понятие дерева. Оно получается из ряда сходных представлений дерева. Понятие возникает из представлений единичных сходных предметов. Далее идет схема, которая поясняет процесс образования понятия и которая представляет его в следующем виде. Положим, я имел случай наблюдать три различных дерева. Представления этих трех деревьев могут быть разложены на свои составные части, из которых каждая обозначает форму, цвет или величин отдельных деревьев. Остальные составные части этих представлений оказываются сходными. [10]
Ответ на вопрос, что эффективнее: только что описанная процедура или использование явных связей, зависит от подробностей кодирования таких, как относительная стоимость проверки пригодности ячейки по сравнению с определением состояния полей левого и правого преемников. В общем случае, однако, область, необходимая для представления дерева, непредсказуема и будет, как правило, больше области, необходимой для построения явного дерева. Необходимое количество памяти зависит от формы дерева. [11]
Однако наиболее важным улучшением является предоставление программисту возможности определить класс узловых ( в представлении дерева) пунктов. Наличие настраиваемых узловых пунктов предполагает возможность подключения данных к узлам простым, объектно-ориентированным способом. [12]
Существует много способов представления деревьев. Полные деревья, сохраненные в массивах, используют наиболее эффективное и компактное представление. Представление дерева в виде коллекций дочерних узлов упрощает работу с ними, но при этом программа выполняется медленнее итребует большего объема памяти. Формат нумерации связей позволяет быстро выполнять обход дерева и расходует меньше памяти, чем коллекции потомков, но в таком случае алгоритм сложно модифицировать. [13]
Дерево целей представляет собой неориентированный граф, вершинами которого являются цели, а ребрами - отношения между целями. Этот граф имеет иерархическую структуру с начальной вершиной, соответствующей генеральной цели и называемой корнем дерева. Представление дерева целей в виде графа является его геометрической интерпретацией. Возможна и аналитическая форма описания дерева целей в виде системы с отношением Ц Я, где Ц - множество целей; R - отношение древесного порядка. [14]
 |
Корневое дерево с тремя поддеревьями.| Регулярная связанная структура представления дерева. [15] |
Страницы: 1 2