Узел (информатика)
Узел — это базовая единица структуры данных , например связанного списка или древовидной структуры данных. Узлы содержат данные , а также могут быть связаны с другими узлами. Ссылки между узлами часто реализуются указателями .
Узлы и деревья [ править ]
Узлы часто имеют древовидную структуру. Узел представляет информацию, содержащуюся в одной структуре данных. Эти узлы могут содержать значение или условие или, возможно, служить другой независимой структурой данных. Узлы представлены одним родительским узлом. Самая высокая точка древовидной структуры называется корневым узлом, который не имеет родительского узла, но служит родительским или «прародительским» для всех узлов ниже него в дереве. Высота узла определяется общим количеством ребер на пути от этого узла до самого дальнего листового узла, а высота дерева равна высоте корневого узла. [1] Глубина узла определяется расстоянием между этим конкретным узлом и корневым узлом. Говорят, что корневой узел имеет нулевую глубину. [2] Данные можно обнаружить по этим сетевым путям. [3] IP-адрес использует такую систему узлов для определения своего местоположения в сети.
Определения [ править ]
- Дочерний узел : дочерний узел — это узел, выходящий из другого узла. Например, компьютер с доступом в Интернет можно считать дочерним узлом узла, представляющего Интернет. Обратная связь — это связь родительского узла . Если узел C является дочерним по отношению к узлу A , то A родительским узлом C. является
- Степень : степень узла — это количество дочерних элементов узла.
- Глубина : глубина узла A — это длина пути от A до корневого узла. Говорят, что корневой узел имеет глубину 0.
- Край : соединение между узлами.
- Лес : набор деревьев.
- Высота : высота узла A — это длина самого длинного пути через дочерние элементы к листовому узлу.
- Внутренний узел : узел, имеющий хотя бы один дочерний элемент.
- Листовой узел : узел без дочерних элементов.
- Корневой узел : узел, отличающийся от остальных узлов дерева. Обычно его изображают как самый высокий узел дерева.
- Родственные узлы : это узлы, подключенные к одному и тому же родительскому узлу.
Языки разметки [ править ]
Другое распространенное использование деревьев узлов — веб-разработка . В программировании XML используется для передачи информации между программистами и компьютерами. По этой причине XML используется для создания общих протоколов связи, используемых в офисном программном обеспечении , и служит основой для разработки современных языков веб-разметки , таких как XHTML . Несмотря на то, что подходы программиста схожи, HTML и CSS обычно являются языками, используемыми для разработки текста и дизайна веб-сайта. В то время как XML, HTML и XHTML обеспечивают язык и выражение, DOM служит переводчиком. [4]
Тип узла [ править ]
Различные типы узлов в дереве представлены определенными интерфейсами. Другими словами, тип узла определяется тем, как он взаимодействует с другими узлами. Каждый узел имеет свойство типа узла, которое определяет тип узла, например одноуровневый или листовой.Например, если свойство типа узла является постоянным свойством узла, это свойство определяет тип узла. Таким образом, если свойством типа узла является постоянный узел ELEMENT_NODE, можно знать, что этот объект узла является объектом Element. Этот объект использует интерфейс Element для определения всех методов и свойств этого конкретного узла.
Различные типы и описания узлов Консорциума W3C World Wide Web :
- Документ представляет весь документ (корневой узел дерева DOM).
- DocumentFragment представляет собой «легкий» объект Document, который может содержать часть документа.
- DocumentType предоставляет интерфейс для объектов, определенных для документа.
- ProcessingInstruction представляет инструкцию обработки.
- EntityReference представляет ссылку на сущность.
- Элемент представляет элемент
- Attr представляет атрибут
- Текст представляет собой текстовое содержимое в элементе или атрибуте.
- CDATASection представляет раздел CDATA в документе (текст, который НЕ будет анализироваться синтаксическим анализатором).
- Комментарий представляет собой комментарий
- Сущность представляет сущность
- Нотация представляет собой нотацию, объявленную в DTD.
| Тип узла | Именованная константа |
|---|---|
| 1 | ELEMENT_NODE |
| 2 | ATTRIBUTE_NODE |
| 3 | TEXT_NODE |
| 4 | CDATA_SECTION_NODE |
| 5 | ENTITY_REFERENCE_NODE |
| 6 | ENTITY_NODE |
| 7 | PROCESSING_INSTRUCTION_NODE |
| 8 | КОММЕНТАРИЙ_НОДЕ |
| 9 | ДОКУМЕНТ_НОД |
| 10 | ДОКУМЕНТ_TYPE_NODE |
| 11 | DOCUMENT_FRAGMENT_NODE |
| 12 | НОТАЦИЯ_НОДЕ |
Объект узла [ править ]
Объект узла представлен одним узлом в дереве. Это может быть узел элемента, узел атрибута, текстовый узел или любой тип, описанный в разделе «Тип узла». Все объекты могут наследовать свойства и методы для работы с родительскими и дочерними узлами, но не все объекты имеют родительские или дочерние узлы. Например, для текстовых узлов, которые не могут иметь дочерних узлов, попытка добавить дочерние узлы приводит к ошибке DOM .
К объектам в дереве DOM можно обращаться и манипулировать ими с помощью методов объектов. Открытый интерфейс DOM указан в его интерфейсе прикладного программирования (API). История объектной модели документа переплетается с историей « войн браузеров » конца 1990-х годов между Netscape Navigator и Microsoft Internet Explorer , а также с историей JavaScript и JScript , первых языков сценариев , широко реализованных в мире. Механизмы компоновки браузеров веб- .
См. также [ править ]
Ссылки [ править ]
- ^ «дерево (структура данных)» . Национальный институт стандартов и технологий . Архивировано из оригинала 24 ноября 2014 г.
- ^ Теукольский, Розелин (2013). Barron's AP Информатика А. Бэрронс . ISBN 978-1-4380-0152-4 .
- ^ «Просто схема: Введение в информатику, глава 18: Деревья» . Инженерный колледж Калифорнийского университета в Беркли . Архивировано из оригинала 22 декабря 2013 г.
- ^ «Введение в XML DOM» . W3Школы . Архивировано из оригинала 11 июня 2014 г. Проверено 7 апреля 2018 г.
Внешние ссылки [ править ]
- Деревья данных как средство представления сложного анализа данных Салли Найп
- STL-подобный древовидный класс C++. Архивировано 26 ноября 2020 г. на Wayback Machine.
- Описание древовидных структур данных с сайта ideainfo.8m.com
- WormWeb.org: Интерактивная визуализация C. elegans клеточного дерева - Визуализация всего дерева клеточных линий нематоды C. elegans (javascript)