btreeexercises.txt

这是本人精心搜集的关于常用图论算法的一套源码

//E7
template <class Record, int order>
void B_tree<Record, order>::recursive_inorder(
           B_node<Record, order> *sub_root, void (*visit)(Record &))
/* 
 
Post: The subtree referenced by
      sub_root is traversed, in order.  The operation
      *visit is applied to all records of the tree.
 
*/
{
   if (sub_root != NULL) {
      recursive_inorder(sub_root->branch[0], visit);
      for (int i = 0; i < sub_root->count; i++) {
          (*visit)(sub_root->data[i]);
          recursive_inorder(sub_root->branch[i + 1], visit);
      }
   }
}

template <class Record, int order>
void B_tree<Record, order>::inorder(void (*visit)(Record &))
/* 
 
Post: The B_tree is traversed, in order, and the operation
      *visit is applied to all records of the tree.
 
*/
{
    recursive_inorder(root, visit);
}

//E8

template <class Record, int order>
void B_tree<Record, order>::recursive_preorder(
           B_node<Record, order> *sub_root, void (*visit)(Record &))
/* 
 
Post: The subtree referenced by
      sub_root is traversed, in prefix order.  The operation
      *visit is applied to all records of the tree.
 
*/
{
   int i;
   if (sub_root != NULL) {
      for (i = 0; i < sub_root->count; i++)
         (*visit)(sub_root->data[i]);
      for (i = 0; i <= sub_root->count; i++)
         recursive_preorder(sub_root->branch[i], visit);
   }
}

template <class Record, int order>
void B_tree<Record, order>::preorder(void (*visit)(Record &))
/* 
 
Post: The B_tree is traversed, in prefix order, and the operation
      *visit is applied to all records of the tree.
 
*/
{
    recursive_preorder(root, visit);
}

//E9

template <class Record, int order>
void B_tree<Record, order>::recursive_postorder(
           B_node<Record, order> *sub_root, void (*visit)(Record &))
/* 
 
Post: The subtree referenced by
      sub_root is traversed, in postfix order.  The operation
      *visit is applied to all records of the tree.
 
*/
{
   int i;
   if (sub_root != NULL) {
      for (i = 0; i <= sub_root->count; i++)
         recursive_postorder(sub_root->branch[i], visit);
      for (i = 0; i < sub_root->count; i++)
         (*visit)(sub_root->data[i]);
   }
}

template <class Record, int order>
void B_tree<Record, order>::postorder(void (*visit)(Record &))
/* 
 
Post: The B_tree is traversed, in postfix order, and the operation
      *visit is applied to all records of the tree.
 
*/
{
    recursive_postorder(root, visit);
}

//E10

template <class Record, int order>
Error_code B_tree<Record, order>::search_tree(Record &target)
/* 
 
Post:
If there is an entry in the B-tree whose key matches that in target,
the parameter target is replaced by the corresponding Record from
the B-tree and a code of success is returned.  Otherwise
a code of not_present is returned.
Uses: recursive_search_tree
 
*/

{
   B_node<Record, order> *sub_root = root;
   while (sub_root != NULL) {
      int position;
      if (search_node(sub_root, target, position) == not_present)
         sub_root = sub_root->branch[position];
      else {
         target = sub_root->data[position];
         return success;
      }
   }
   return not_present;
}
//E11

template <class Record, int order>
Error_code B_tree<Record, order>::search_node(
   B_node<Record, order> *current, const Record &target, int &position)
/* 
 
Pre:  current points to a node of a B_tree.
Post: If the Key of target is found in *current, then a code of
      success is returned, the parameter position is set to the index
      of target, and the corresponding Record is copied to
      target.  Otherwise, a code of not_present is returned, and
      position is set to the branch index on which to continue the search.
Uses: Methods of class Record.
 
*/

{
   if (target < current->data[0]) {
      position = 0;
      return not_present;
   }

   int low = 0, mid, high = current->count;
   while (high > low) {
      mid = (high + low) / 2;
      if (current->data[mid] < target) low = mid + 1;
      else                             high = mid;
   }
   position = high;
   if (position < current->count &&
          target == current->data[high]) return success;
   return not_present;
}