Cout << "tree";

Привет! Сегодня мы рассмотрим важную структуру данных, а именно дерево.

Что такое дерево?

Дерево —  Структура данных эмулирующая древовидную структуру(перевёрнутое дерево) в виде набора связных узлов. Является связным, неориентированным графом, не содержащим циклы.

Термины древовидной структуры данных.

Каждый элемент — это вершина или узел дерева. Узлы, соединенные направленными дугами, называются ветвями. Начальный узел — это корень дерева (корневой узел). Листья — это узлы, в которые входит 1 ветвь, причем не выходит ни одной. Внутренний узел(родительский) — любой узел дерева(кроме корневого узла), имеющий потомков, и таким образом не являющийся листовым узлом. Дочерний узел — узел под родительским узлом. Степенью узла в дереве называется количество дуг, которые из него выходят. Степень дерева равна максимальной степени узла, входящего в дерево(различают двоичные(степень не больше двух) и сильноветвящиеся (степень больше двух)). Глубина узла — количество рёбер от корня до узла. Высота дерева — глубина самого глубокого узла.

Преимущество древовидной структуры.

Одним из его существенных преимуществ перед другими структурами данных является то, что это нелинейная структура данных, обеспечивающая более простой и быстрый доступ к данным. В то время как линейные структуры данных хранят данные последовательно, древовидные структуры обеспечивают доступ к данным в разных направлениях.

Обход дерева.

Чтобы выполнить конкретную операцию над всеми вершинами, надо все эти узлы просмотреть. Данную задачу называют обходом дерева. В процессе обхода все узлы должны посещаться в некотором, заранее определенном порядке. Есть ряд способов обхода, вот три основные:

• Прямой обход (NLR);
• Центрированный обход (LNR);
• Обратный обход (LRN).

Применение древовидных структур.

• Большинство популярных баз данных используют B-деревья и T-деревья для хранения данных.
• Дерево кучи используется для выполнения операции сортировки.
• Древовидные структуры используются для отображения всеx видов информации из области таксономии(учение о классификации информации), как например, генеалогическое древо, филогенетическое дерево.

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

С ув. ваш TechMentor.