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

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);