Двоичные деревья поиска
| Категория реферата: Рефераты по информатике, программированию
| Теги реферата: отчет о прохождении практики, шпоры на экзамен
| Добавил(а) на сайт: Dvoreckov.
Предыдущая страница реферата | 1 2 3 4 5 6 7 8 9 10 11 | Следующая страница реферата
Наиболее часто употребляется поперечный обход, так как во всех других способах обхода следующие друг за другом вершины не связаны никакими условиями отношения.
Поиск вершины в ДДП
Идея поиска проста. Алгоритм поиска в ДДП по своей природе рекурсивен. При его описании проще всего использовать понятие поддерева. Поиск начинается с корня дерева, который принимается за корень текущего поддерева, и его ключ сравнивается с искомым. Если они равны, то, очевидно, поиск закончен. Если ключ, который мы ищем, оказался больше текущего, то, очевидно, что нужная вершина находится в правом поддереве, иначе – в левом. Далее эта операция повторяется для правого или левого поддерева. В условном коде это можно описать так:
Рекурсивно:
|
TreeSearch(node, key) Begin // Если вершина равна NIL, то нечего в ней искать. Так же и возвращаем. // Это нужно для поиска по не существующим потомкам If (node == NIL) Then Return node; // Если нашли, то возвращаем указатель на найденную вершину. If (node.key == key) Then Return node; // Если ключ найденной вершины больше того, который мы ищем If (node.key > key) Then // То искать в левом поддереве Return TreeSearch(node.left, key); Else // Иначе в правом поддереве Return TreeSearch(node.right, key); End |
|
ПРИМЕЧАНИЕ В прилагаемом исходном коде, написанном на паскале-подобном языке, все параметры передаются по значению. nodeParent, nodeTemp и node – это указатели на вершины, а Tree – само дерево, имеющее поле root, указатель на корень дерева. |
Итеративно:
|
TreeSearch(node,key) Begin Рекомендуем скачать другие рефераты по теме: шпаргалки по математике, шпаргалки по гражданскому. Категории:Предыдущая страница реферата | 1 2 3 4 5 6 7 8 9 10 11 | Следующая страница реферата Поделитесь этой записью или добавьте в закладки |
|
Главная