русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Дерево в информатике

Дерево (англ. tree) - в информатике и программировании одна из самых распространенных структур данных.

Свойства

Из определения следует, что каждая вершина является в свою очередь корнем некоторого поддерева. Количество поддеревьев вершины называется степени (degree) этой вершины. Вершина степени нуль называется конечной (terminal) или письмо (leaf). Неконечная вершина также называется вершиной ветвления (branch node).

Пусть x - произвольная вершина дерева с корнем r. Тогда существует единственный путь из r в x. Все вершины на этом пути называются предками (ancestors) x; если некоторая вершина y является предком x, то x называется потомком (descendant) y. Потомки и предки вершины x, не совпадающие с ней самой, называются собственными потомками и предками. Каждую вершину x, в свою очередь, можно рассматривать как корень некоторого поддерева, элементами которого являются вершины-потомки x.
Если вершины x является предком y и не существует вершин между ними (т.е. x и y соединены одним ребром), а также существуют предки для x (т.е. x не является корнем), то вершина x называется отцом (parent) к y, а y - ребенком (child) x. Корневая вершина единственная не имеет родителей.

Вершины, имеющие общего отца, называются братьями (siblings). Вершины, имеющие детей, длина пути от корня к этой вершине. Максимальная глубина вершин дерева называется высотой.

Если существует относительный порядок на поддеревья T 1 ... T M, то такое дерево называется упорядоченным (ordered tree) или плоским (plane tree).
Лесом (англ. forest) называют множество деревьев, которые не пересекаются.

Зачастую деревья в информатике изображают с корнем, который находится сверху (говорят, что дерево в информатике «растет вниз»).

Важным частным случаем корневых деревьев является бинарные деревья, которые широко применяются в программировании и определяются как множество вершин, у которого выделен корень и два поддерева (правое и левое), не пересекаются, либо является пустой множеством вершин (в отличие от обычного дерева, которое не может быть пустым).

Операции над деревом

Важными операциями на деревьях являются:

  • обход вершин в разном порядке;
  • перенумерация вершин;
  • поиск элемента;
  • добавление элемента в назначенное место в дереве;
  • удаление элемента;
  • удаление целого фрагмента дерева;
  • добавление целого фрагмента дерева;
  • трансформации (повороты) фрагментов дерева;
  • нахождение корня для любой вершины.

Наибольшее распространение эти структуры данных получили в тех задачах, где необходимо манипулирования с иерархическими данными, эффективный поиск в данных, их структурированное хранение и модификация.

Просмотров: 7834

Оглавление: Компьютерная графика и информация в компьютерной сфере


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.