Константы 7 страница

— другие операции со стеком не определены.

Диаграмма, представляющая работу стека (LIFO) изображена на рис. 6.11.

Рисунок 6.11 — Диаграмма работы стека (LIFO)

6.5.3. Очередь

Очередь — это частный случай односвязного (однонаправленного) списка, добавление элементов в который выполняется в конец, а выборка производится из начала списка.

Примечания:

— при чтении элемента он исключается из очереди;

— работает очередь по принципу «первым вошел, первым вышел» (FIFO);

— другие операции с очередью не определены.

Диаграмма, представляющая работу очереди (FIFO) изображена на рис. 6.12.

Рисунок 6.12 — Диаграмма работы очереди (FIFO)

6.5.4. Бинарные деревья

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

Примечания:

— на каждый узел имеется ровно одна ссылка;

— узел, не имеющий поддеревьев, называется листом;

— исходящие узлы называются предками, входящие — потомками;

— высота дерева определяется количеством уровней, на которых располагаются его узлы;

— если дерево организовано таким образом, что для каждого узла все ключи его левого поддерева меньше ключа этого узла, оно называется деревом поиска;

— одинаковые ключи не допускаются;

— в дереве поиска можно найти элемент по ключу, двигаясь от корня и переходя на левое или правое поддерево, в зависимости от значения ключа в каждом узле;

— дерево является рекурсивной структурой данных, поскольку каждое поддерево также является деревом; действия с такими структурами удобнее всего описывать с помощью рекурсивных алгоритмов, однако можно применять и нерекурсивные алгоритмы.

Примеры:

1. Элемент бинарного дерева:

struct node

{

int data;

node *left;

node *right;

}

2. Функция обхода дерева:

function tree_walk (дерево)

{

tree_walk (левое поддерево) ;

посещение корня ;

tree_walk (правое поддерево) ;

}

Диаграмма обхода бинарного дерева представлена на рис. 6.13.

Рисунок 6.13 — Диаграмма обхода бинарного дерева

Примечания:

При обходе данного дерева по рекурсивному алгоритму «левое дерево→корень→правое дерево» получим результат 1, 6, 8, 10, 20, 21, 25, 30.

При обходе данного дерева по рекурсивному алгоритму «правое дерево→корень→левое дерево» получим результат: 30, 25, 21, 20, 10, 8, 6, 1.

С бинарными деревьями можно выполнять следующие операции:

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

— поиск по дереву;

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

— удаление узла.