Рефераты | Рефераты по информатике, программированию | Двоичные деревья поиска
Двоичные деревья поиска
Категория реферата: Рефераты по информатике, программированию
Теги реферата: отчет о прохождении практики, шпоры на экзамен
Добавил(а) на сайт: Dvoreckov.
Чтобы найти предыдущую и следующую вершину, надо снова
вспомнить свойство упорядоченности. Рассмотрим это на примере функции 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
node = nodeParent;
nodeParent =
nodeParent.nodeParent;
End
// Возвратить родителя вершины, являющегося
левым потомком своего родителя
Return nodeParent;
End
TreePrevious(node)
Begin
If (node.left != NIL) Then
// Если левое поддерево не пусто, то возвратить
Рекомендуем скачать другие рефераты по теме: шпаргалки по математике, шпаргалки по гражданскому.