Обход в прямом направлении

Формулировка задания

Реализовать следующие операции с двоичными деревьями поиска:

- Добавление новой вершины;

- Обход (прямой, симметричный, обратный);

- Удаление заданной вершины;

- Поиск заданной вершины;

- Вывод дерева на экран.

Главная программа должна:

- Создать пустое дерево;

- Организовать цикл для добавления вершины с вызовом соответствующей подпрограммы с последующим построчным выводом дерева (должна быть реализована двумя способами: заполнение случайными числами и заполнение заданными пользователем);

- Предоставить возможность в любой момент вызвать подпрограмму удаления дерева с фактическим параметром;

- Предоставить возможность в любой момент вызвать подпрограмму обхода дерева с фактическим параметром.

Основные операции с двоичными деревьями поиска

Вставка новой вершины в двоичное дерево поиска

Алгоритм:

а) Проверяем чтобы корень не был равен нулю;

б) Если значение элемента меньше корня, тогда;

в) Проверяем значение корня в левом поддереве, если пусто, то вставляем;

г) Если значение элемента больше корня, тогда;

д) Проверяем значение корня в правом поддереве, если пусто, то вставляем;

е) Связываем полученные корни;

if R< > Nil then begin

if R^.Data< N then begin

if R^.Left=nil then R^.Left: =NewElement(N) else AddElement(R^.Left, N);

end

else begin

if R^.Right=nil then R^.Right: =NewElement(N) else AddElement(R^.Right, N);

end;

end

else begin

R: =NewElement(N);

end;

2) Обходы деревьев:

Обход в прямом направлении

Алгоритм:

а) Проверить чтобы корень не был равен нулю;

б) Обработать корневую вершину текущего поддерева;

в) Перейти к обработке левого поддерева таким же образом;

г) Обработать правое поддерево таким же образом;

if root < > nil then

begin

write (root^.data, ' ');

preorder (root^.left);

preorder (root^.right);

end;