Основные операции над деревьями.
6.2.6. Основные операции над деревьями.
Над деревьями определены следующие основные операции, для которых приведены реализующие их программы.
- 1) Поиск узла с заданным ключом ( Find ).
- 2) Добавление нового узла ( Dob ).
- 3) Удаление узла ( поддерева ) ( Udal ).
- 4) Обход дерева в определенном порядке:
- Нисходящий обход ( процедура Preorder , рекурсивная процедура r_Preoder);
- Смешанный обход (процедура Inorder, рекурсивная процедура r_Inorder);
- Восходящий обход ( процедура Postorder, рекурсивная процедура r_Postorder).
Приведенные ниже программы процедур и функций могут быть непосредственно использованы при решении индивидуальных задач. Кроме выше указанных процедур приведены следующие процедуры и функции:
- процедура включения в стек при нисходящем обходе (Push_st);
- функция извлечения из стека при нисходящем обходе (Pop_st);
- процедура включения в стек при восходящем и смешанном обходе (S_Push);
- функция извлечения из стека при восходящем и смешанном обходе (S_Pop).
Для прошитых деревьев:
- функция нахождения сына данного узла ( Inson );
- функция нахождения отца данного узла ( Inp );
- процедура включения в дерево узла слева от данного (leftIn);