Нелинейные структуры данных

Нелинейные структуры данных – иерархические структуры деревья.

Бинарное дерево — это динамическая структура данных, состоящая из узлов, каждый из которых содержит данные и не более двух ссылок на узлы. На каждый узел имеется ровно одна ссылка. Начальный узел называется корнем дерева.

На рисунке 2.2 приведен пример бинарного дерева.

Рисунок 2.2 – Бинарное дерево

Лист - узел, не имеющий поддеревьев.

Предок - исходящий узел. Входящий узел - потомок.

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

Для бинарных деревьев определены операции:

• включения узла в дерево;

• поиска по дереву;

• обхода дерева;

• удаления узла.

Не нашли, что искали? Воспользуйтесь поиском: