Реферат: Двоичные деревья поиска
End
Поиск вершины с минимальным и максимальным значением ключа
Вершины с минимальным и максимальным значением ключа можно найти, пройдясь по левым (правым) указателям от корня (пока не достигнем NIL). Возвращаемое значение – это указатель на вершину с минимальным (максимальным) значением ключа.
|
TreeMinimum(node) Begin While (node.left != NIL) Do // Пока есть левый потомок Node = node.left; // Перейти к нему Return node; End TreeMaximum(node) Begin While (node.right != NIL) Do // Пока есть правый потомок node = node.right; // Перейти к нему Return node; End |
Нахождение следующей и предыдущей вершины в ДДП
Чтобы найти предыдущую и следующую вершину, надо снова вспомнить свойство упорядоченности. Рассмотрим это на примере функции TreeNext. Она учитывает два случая. Если правое поддерево не пусто, то вершина из правого поддерева с минимальным значением ключа и будет следующей. Если же правое поддерево пусто, тогда мы идём вверх, пока не найдём вершину, являющуюся левым потомком своего родителя. Этот родитель (если он есть) и будет следующей вершиной. Возвращаемое значение – это указатель на вершину с следующим (предыдущим) значеним ключа или NIL, если такой вершины нет.
|
TreeNext(node) Begin // Если правое поддерево не пусто, то возвратить // вершину с минимальным значением ключа из правого поддерева If (node.right != NIL) Then Return TreeMinimum(node.right); nodeParent = node.nodeParent; // Перебирать родителей, пока не найдена вершина, // являющаяся левым потомком своего родителя // или пока не закончатся родители. While (nodeParent != NIL) and (node == nodeParent.right) Do Begin К-во Просмотров: 886
Бесплатно скачать Реферат: Двоичные деревья поиска
|