Методы обхода

Пошаговый перебор элементов дерева по связям между узлами-предками и узлами-потомками называется обходом дерева. Зачастую, операция может быть выполнена переходом указателя по отдельным узлам. Обход, при котором каждый узел-предок просматривается прежде его потомков называется предупорядоченным обходом или обходом в прямом порядке (pre-order walk), а когда просматриваются сначала потомки, а потом предки, то обход называется поступорядоченным обходом или обходом в обратном порядке (post-order walk). Существует также симметричный обход, при котором посещается сначала левое поддерево, затем узел, затем — правое поддерево, и обход в ширину, при котором узлы посещаются уровень за уровнем (N-й уровень дерева — множество узлов с высотой N). Каждый уровень обходится слева направо.

Общие операции

· вставка нового элемента в определённую позицию;

· вставка поддерева;

· добавление ветви дерева (называется прививкой);

· нахождение корневого элемента для любого узла;

· нахождение наименьшего общего предка двух вершин;

· перебор всех элементов дерева;

· перебор элементов ветви дерева;

· поиск изоморфного поддерева;

· поиск элемента;

· удаление ветви дерева (называется обрезкой);

· удаление поддерева;

· удаление элемента.