Основные элементы языка С алфавит языка, идентификаторы, константы. Использование комментари (стр. 8 из 8)

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

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

Можно обходить дерево и в другом порядке, например, сначала корень, потом поддеревья, но приведенная функция позволяет получить на выходе отсортированную последовательность ключей, поскольку сначала посещаются вершины с меньшими ключами, расположенные в левом поддереве. Результат обхода дерева, изображенного на рис. 1: 1, 6, 8, 10, 20, 21, 25, 30.

Если в функции обхода первое обращение идет к правому поддереву, результат обхода будет другим: 30, 25, 21, 20, 10, 8, 6, 1.

Таким образом, деревья поиска можно применять для сортировки значений. При обходе дерева узлы не удаляются. Для бинарных деревьев определены операции: включения узла в дерево; поиска по дереву; обхода дерева; удаления узла. Для каждого рекурсивного алгоритма можно создать его не рекурсивный эквивалент.