Рефераты | Рефераты по информатике, программированию | Двоичные деревья поиска | страница реферата 4 | Большая Энциклопедия Рефератов от А до Я
Большая Энциклопедия Рефератов от А до Я
  • Рефераты, курсовые, шпаргалки, сочинения, изложения
  • Дипломы, диссертации, решебники, рассказы, тезисы
  • Конспекты, отчеты, доклады, контрольные работы

  • Нахождение следующей и предыдущей вершины в ДДП

    Чтобы найти предыдущую и следующую вершину, надо снова вспомнить свойство упорядоченности. Рассмотрим это на примере функции 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

        // Если левое поддерево не пусто, то возвратить


    Рекомендуем скачать другие рефераты по теме: шпаргалки по математике, шпаргалки по гражданскому.



    Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 |




    Поделитесь этой записью или добавьте в закладки

       




    Категории:



    Разделы сайта




    •