Деревья
Деревомназывается такая ссылочная структура, в которой на каждый объект, кроме одного –корневого(на который нет ссылок в дереве), ссылается только один, другой объект дерева. Из определения следует, что в деревьях не должно быть циклов.
Объекты дерева называются обычно узламииливершинами. Узлы, которые не ссылаются на другие узлы, называютсялистьями. В программировании деревья рисуют, как правило, корнем вверх, а листьями вниз. Принято также говорить, что ссылка ведёт отродительскогоузла кдочернему. В этом смысле узлы могут бытьпотомкамиипредкамидругих узлов, причём у каждого узла (кроме корня) ровно один родительский узел.
Примером простейшего дерева является односвязный нециклический список (у каждого родительского узла только один дочерний узел). Двухсвязный список деревом не является.
Дерево называется бинарным, если у каждого родительского узла не более двух дочерних. Бинарные деревья очень часто используются в программистской практике. Каждый узел бинарного дерева имеет два свойства, содержащих ссылки на дочерние узлы. Если дочернего узла нет, вместо ссылки поле содержит значение, не являющееся ссылкой, напримерnull.
Примером бинарного дерева является генеалогическое дерево человека (дерево предков). Пусть каждый узел представлен объектом типа
{man:сведения_о_человеке, f:его_отец, m:его_мать}
Свойстваfиmсодержат ссылки на узлы родителей человека, имеющие такой же тип. Если какой-то из родителей неизвестен, вместо ссылки в соответствующем свойстве будетnull. Любое дерево может быть записано на языкеJavaScriptв виде литерала объекта. Например:
{man: "Иван",
f: {man: "Пётр",
f: {man: "Павел",
f: {man: "Алексей",
f: null,
m: null},
m: null},
m: {man: "Мария",
f: null,
m: null}},
m: {man: "Ирина",
f: null,
m: {man: "Елена",
f: null,
m: null}}}
Графическое изображение этого дерева может быть таким, как на рис. 2.15. В нём имена ссылочных свойств записаны прямо на стрелках. Если это не приводит к путанице (при определённых соглашениях), имена свойств можно и не приводить.
Рисунок 2.15. Бинарное генеалогическое дерево.
С деревьями удобно выполнять операции по замене узла и поддерева в любом месте, по поиску информации и т.п. Деревья и основанные на них структуры применяются в иерархических базах данных, в поисковых системах и многих других приложениях.
Выводы
Язык объектно-ориентированного программирования высокого уровня JavaScriptпредоставляет большой набор средств для создания самых разнообразных структур данных и манипулирования с ними (ещё более мощные средства манипулирования данными будут рассмотрены в следующих лекциях).
Высокий уровень абстракции семантических понятий языка и жёсткая формальная структура его синтаксиса требует использования при программировании и отладке программ точных, по возможности, формальных и доступных определений синтаксиса и семантики языка.
1Использовать символ «Новая строка» в качестве разделителя операторовне рекомендуется, особенно начинающим, так как это приводит к увеличению количества ошибок в программе.
2Рекурсивные определения можно найти и в быту. Например,предок человека – это его мать, отец или предок его предка. Это пример завершающейся рекурсии (когда о чьих-то родителях уже не осталось сведений), а «масло – это масло» – примеры бесконечной рекурсии. См. также в Википедии статью «Рекурсия».
3Переключение регистров осуществляется клавишамиShiftиCapsLock.
4Эти функции являются методами объектаwindow(англ.окно), принадлежащему браузеру. Их рекомендуется использовать при отладке программ в браузере. В других системах нужно использовать другие функции ввода-вывода.
5Литерал– символьное изображение значения (от лат.littera– буква).
6Согласно стандартуECMAScriptвсе числа вJavaScriptпредставляются 64-разрядными вещественными значениями (с плавающей точкой), формат которых определяется стандартом IEEE 754. Этот формат способен представлять числа от ±1,7976931348623157 × 10308до ±5 × 10–324.
7Встроенные элементы языкаJavaScriptопределены стандартом языка и подлежат реализации в любом интерпретатореJavaScript.
8Функции parseInt и parseFloatявляются методами встроенного объектаGlobal.
9Традиционно в английском и русском языках для программирования использовали соответствияstatement – оператор,operator – операция. Последняя мода:statement – инструкция,operator – оператор.