Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

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



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

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

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

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

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

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

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

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

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

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

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

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

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

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





Дата публикования: 2015-01-24; Прочитано: 267 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.006 с)...