bst.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;
     Error_code remove_root(Binary_node<Record>* &);
     Error_code search_and_destroy(Binary_node<Record>* &, const Record &);
};

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        
template <class Record>
Error_code Search_tree<Record>::remove(const Record &target)
/* Post: If a Record with a key matching that oftarget belongs to theSearch_tree a
         code ofsuccess is returned and the corresponding node is removed from the
         tree. Otherwise, a code ofnot_present is returned.
   Uses: Function search_and_destroy */
{ return search_and_destroy(root, target); }

template <class Record>Error_code Search_tree<Record>::
  search_and_destroy(Binary_node<Record>* &sub_root, const Record &target)
/* Pre: sub_root is either NULL or points to a subtree of theSearch_tree .
  Post: If the key of target is not in the subtree, a code of not_present is returned.
        Otherwise, a code of success is returned and the subtree node containing
        target has been removed in such a way that the properties of a binary search
        tree have been preserved.
  Uses: Functions search_and_destroy recursively andremove_root */
{ if(sub_root==NULL || sub_root->data==target)   
     return remove_root(sub_root);
   else if(target<sub_root->data)
         return search_and_destroy(sub_root->left, target);
         else return search_and_destroy(sub_root->right, target);
}

template <class Record>Error_code Search_tree<Record>::
  remove_root(Binary_node<Record>* &sub_root)
/* Pre: sub_root is eitherNULL or points to a subtree of theSearch_tree .
  Post: If sub_root is NULL, a code of not_present is returned. 
        Otherwise, the root of the subtree is removed in such a way 
        that the properties of a binary search tree are preserved. 
        The parametersub_root is reset as the root of the modified subtree, and success is returned. */
{ if(sub_root==NULL) return not_present;
  Binary_node<Record> *to_delete=sub_root;
   // Remember node to_delete at end.
  if(sub_root->right==NULL) sub_root=sub_root->left;
   else if(sub_root->left==NULL) sub_root=sub_root->right;
    else{ // Neither subtree is empty.
         to_delete=sub_root->left;             // Move left to find predecessor.
         Binary_node<Record> *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;          //Remove to_delete from tree.
  return success;
}