Лабораторная работа № 20. Тема: «Обработка динамических структур данных»

Тема: «Обработка динамических структур данных»

Рассмотрим работу с бинарным деревом (в котором у каждого узла может быть только два приемника - левый и правый сын). Необходимо уметь:

построить дерево;

выполнить поиск элемента с указанным значением в узле;

удалить заданный элемент;

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

Обычно бинарное дерево строится сразу упорядоченным, т.е. узел левого сына имеет значение меньшее, чем значение родителя, а узел правого сына - большее. Например, если приходят числа 17, 18, 6, 5, 9, 23, 12, 7, 8, то построенное по ним дерево будет выглядеть так (рис. 15.6).

Для того, чтобы вставить новый элемент в дерево, надо найти для него место. Для этого, начиная с корня, будем сравнивать значения узлов (Y) со значением нового элемента (NEW). Если NEW < Y, то пойдем по левой ветви; в противном случае - по правой. Когда дойдем до узла, из которого не выходит нужная ветвь для дальнейшего поиска, это означает, что место под новый элемент найдено.

Путь поиска места для числа 11 в построенном выше дереве показан на рис. 15.7.

При удалении узла из дерева возможны три ситуации:

а) исключаемый узел - лист (в этом случае надо просто удалить ссылку на данный узел);

б) из исключаемого узла выходит только одна ветвь;

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

Рассмотрим задачу обхода дерева. Существуют три способа обхода, которые естественно следуют из самой структуры дерева.

1) Обход слева направо: A, R, В (сначала посещаем левое поддерево, затем - корень и, наконец, правое поддерево).

2) Обход сверху вниз: R, А, В (посещаем корень до поддеревьев).

3) Обход снизу вверх: А, В, R (посещаем корень после поддеревьев).

Интересно проследить результаты этих трех обходов на примере записи формул в виде дерева.