bst_nr.h

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

#include "bt.h"
#include "Record.h"
#define NULL 0
enum Error_code{ success, duplicate_error, not_present};

template <class Record>
class Search_tree:public Binary_tree <Record> 
{  public:
    Error_code insert(const Record&);
    Error_code remove(const Record&);
    Error_code tree_search(Record& ) const;
     
   protected:
         // Add auxiliary function prototypes here.
     Binary_node<Record>* search_for_node
               ( Binary_node<Record> *sub_root, const Record &target ) const;
};

template<class Record> 
Error_code Search_tree<Record>::tree_search(Record &target) const
{Error_code result = success;
 Binary_node<Record> *found = search_for_node(root,target);
 if(found==NULL) result = not_present; else target = found->data;
 return result;
}
template <class Record> Binary_node<Record>* 
 Search_tree<Record>::search_for_node(Binary_node<Record> *sub_root, const Record &target) const
{ while(sub_root!=NULL && sub_root->data!=target)
     if(sub_root->data<target) sub_root=sub_root->right; else sub_root=sub_root->left;
  return sub_root;
}

//Insertion into a Binary Search Tree       
template <class Record>
Error_code Search_tree<Record>::insert(const Record &new_data)
{ if(root==NULL) 
    { root=new Binary_node<Record>(new_data);
      return success;
   }
 Binary_node<Record> *sub_root=root, *parent;
 do{ parent=sub_root;
     if(new_data<sub_root->data) sub_root=sub_root->left;
      else if(new_data>sub_root->data) sub_root=sub_root->right;
            else return duplicate_error;
   }while(sub_root!=NULL);
 sub_root=new Binary_node<Record>(new_data);
 if(new_data<parent->data) parent->left=sub_root;
   else parent->right = sub_root;
 return success;
}
// Removal from a Binary Search Tree    脱离循环sub_root指向被删结点   
template <class Record>
Error_code Search_tree<Record>::remove(const Record &target)
/* Post: If a Record with a key matching that of target belongs to the Search_tree a
         code of success is returned and the corresponding node is removed from the
         tree. Otherwise, a code of not_present is returned. */
{ Binary_node<Record> *sub_root=root, *parent=NULL;
  while(sub_root!=NULL && sub_root->data!=target) 
     if(target<sub_root->data) parent=sub_root, sub_root=sub_root->left;  // Move left to find  
      else parent=sub_root, sub_root=sub_root->right;
  if(sub_root==NULL) return not_present;
  if(sub_root->right==NULL)                     // 只有左子树
    { if(parent==NULL)root=sub_root->left;      // 删除根结点
       else if(parent->left==sub_root) parent->left=sub_root->left; 
             else parent->right=sub_root->left; 
      delete sub_root;
      return success; 
    }
  if(sub_root->left==NULL)                      // 只有右子树
    { if(parent==NULL)root=sub_root->right;      // remove root
       else if(parent->left==sub_root) parent->left=sub_root->right; 
              else parent->right=sub_root->right;
      delete sub_root; 
      return success;
    }
   // Neither subtree is empty.
  Binary_node<Record> *to_delete=sub_root->left; // Move left to find predecessor.
  parent=sub_root;                               // parent of to_delete
  while(to_delete->right!=NULL)                  // to_delete is not the predecessor.
    { parent=to_delete;  to_delete=to_delete->right;  }
  sub_root->data=to_delete->data;                // Move fromto_delete to root.
  if(parent==sub_root) sub_root->left=to_delete->left;
    else parent->right=to_delete->left;
  delete to_delete;          //Removeto_delete from tree.
  return success;
}