bt.h

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

#include <iostream.h>
#define NULL 0
enum Error_code { entry_found, entry_inserted, fail  };

template <class Entry>
struct Binary_node 
{ // data members:
  Entry data;
  Binary_node<Entry> *left;
  Binary_node<Entry> *right;
  // constructors:
  Binary_node( ){ left=right=NULL; }
  Binary_node(const Entry &x):data(x){ left=right=NULL; }
};

template <class Entry>
class Binary_tree 
{  public:
     Binary_tree():root(NULL){}  
     Binary_tree(Entry mark):root(NULL),endmark(mark){}   
     bool empty( ) const
       { return root == NULL; }
    void preorder(void (*visit)(Entry &))
      { recursive_preorder(root, visit);  }
    void inorder(void (*visit)(Entry &))
      { recursive_inorder(root, visit);  }
    void postorder(void (*visit)(Entry &))
      { recursive_postorder(root, visit);  }
    int size() const 
      { return recursive_size(root); }
    void clear( )
      { if(root!=NULL) recursive_clear(root);   }
    int height( ) const
      { return recursive_height(root); }
    int leaf_count()
      { return recursive_leaf_count(root); }
    void insert(const Entry &x)
      { recursive_insert(root, x);  }  
    Binary_tree(const Binary_tree<Entry> &original)
      {  root=recursive_copy(original.root); }
    Binary_tree& operator=(const Binary_tree<Entry> &original); 
    ~Binary_tree() {   clear(); }
    Binary_node<Entry>* GetRoot(){ return root; }
    void CreatBinary_tree(){ CreatBinary_tree(root);  }  // 建立二叉链表表示的二叉树

   protected:
     Binary_node<Entry> *root;
     Entry x, endmark;
         // auxiliary function 
     void recursive_preorder(Binary_node<Entry> *sub_root,void (*visit)(Entry &));
     void recursive_inorder(Binary_node<Entry> *sub_root,void (*visit)(Entry &));         
     void recursive_postorder(Binary_node<Entry> *sub_root,void (*visit)(Entry &));
     int recursive_size(Binary_node<Entry> *sub_root) const;
     int recursive_height(Binary_node<Entry> *sub_root) const;
     int recursive_leaf_count(Binary_node<Entry> *sub_root) const;
     void recursive_clear(Binary_node<Entry> *&sub_root); 
     void recursive_insert(Binary_node<Entry> *&sub_root, const Entry &x);
     Binary_node<Entry>* recursive_copy(Binary_node<Entry> *sub_root);
     void CreatBinary_tree(Binary_node<Entry>* &r);     // 建立以r为根结点指针的二叉链表表示的二叉树
};

template<class Entry> void Binary_tree<Entry>::CreatBinary_tree(Binary_node<Entry>* &r) 
{ cin>>x;
  if(x==endmark)r=NULL;                         // 建立”空”二叉树
   else{ r=new Binary_node<Entry>(x);            // 建立根结点
         CreatBinary_tree(r->left);           // 建立根结点的左子树
         CreatBinary_tree(r->right);           // 建立根结点的右子树
       }
}
template <class Entry> void Binary_tree<Entry>::
recursive_inorder(Binary_node<Entry> *sub_root,void (*visit)(Entry &))
/* Pre: sub_root is either NULL or points to a subtree of the Binary_tree.
  Post: The subtree has been traversed in inorder sequence.
  Uses: The function recursive inorder recursively */
{ if(sub_root != NULL) 
    { recursive_inorder(sub_root->left, visit);
      (*visit)(sub_root->data);
      recursive_inorder(sub_root->right, visit);
    }
}
template <class Entry> void Binary_tree<Entry>::
recursive_preorder(Binary_node<Entry> *sub_root,void (*visit)(Entry &))
{ if(sub_root != NULL) 
    { (*visit)(sub_root->data);
      recursive_preorder(sub_root->left, visit);      
      recursive_preorder(sub_root->right, visit);
    }
}
template <class Entry> void Binary_tree<Entry>::
recursive_postorder(Binary_node<Entry> *sub_root,void (*visit)(Entry &))
{ if(sub_root != NULL) 
    { recursive_postorder(sub_root->left, visit);
      recursive_postorder(sub_root->right, visit);
      (*visit)(sub_root->data);      
    }
}
template <class Entry>
int Binary_tree<Entry>::recursive_size(Binary_node<Entry> *sub_root) const
// Post: The number of entries in the subtree rooted at sub_root is returned.
{  if(sub_root==NULL) return 0;
   return 1+recursive_size(sub_root->left) + recursive_size(sub_root->right);
}
template <class Entry>
int Binary_tree<Entry>::recursive_leaf_count(Binary_node<Entry> *sub_root) const
// Post: The number of leaves in the subtree rooted at sub_root is returned.
{  if (sub_root == NULL) return 0;
   if (sub_root->left == NULL && sub_root->right == NULL) return 1;
   return recursive_leaf_count(sub_root->left)
             + recursive_leaf_count(sub_root->right);
}

template <class Entry>
int Binary_tree<Entry>::recursive_height(Binary_node<Entry> *sub_root) const
{  if (sub_root == NULL) return 0;
   int l = recursive_height(sub_root->left);
   int r = recursive_height(sub_root->right);
   return (l>r? l+1: r+1);
}
template <class Entry>
void Binary_tree<Entry>::recursive_insert(Binary_node<Entry> *&sub_root, const Entry &x)
/* Pre: sub_root is either NULL or points to a subtree of      the Binary_tree.
  Post: The Entry  has been inserted into the subtree in such a way
        that the properties of a binary search tree have been preserved.
   Uses: The functions recursive_insert, recursive_height
*/
{ if(sub_root==NULL) sub_root=new Binary_node<Entry>(x);
   else
     if (recursive_height(sub_root->right) < recursive_height(sub_root->left))
        recursive_insert(sub_root->right, x);
      else recursive_insert(sub_root->left, x);
}
template <class Entry> void Binary_tree<Entry>::
recursive_clear(Binary_node<Entry> *&sub_root)
// Post: The subtree rooted at sub_root is cleared.
{  Binary_node<Entry> *temp = sub_root;
   if (sub_root == NULL) return;
   recursive_clear(sub_root->left);
   recursive_clear(sub_root->right);
   sub_root = NULL;
   delete temp;
}
template <class Entry>
Binary_node<Entry> *Binary_tree<Entry>::recursive_copy( Binary_node<Entry> *sub_root)
// Post: The subtree rooted at sub_root is copied, and a pointer to the root of the new copy is returned.
{  if(sub_root==NULL) return NULL;
   Binary_node<Entry> *temp=new Binary_node<Entry>(sub_root->data);
   temp->left=recursive_copy(sub_root->left);
   temp->right=recursive_copy(sub_root->right);
   return temp;
}
template <class Entry>
Binary_tree<Entry> &Binary_tree<Entry>::operator=(const Binary_tree<Entry> &original)
// Post: The binary tree is reset to copy original.
{  Binary_tree<Entry> new_copy(original);
   clear();
   root = new_copy.root;
   new_copy.root = NULL;
   return *this;
}