tree.cpp

数据结构与程序设计教材源码 数据结构与程序设计教材源码

 
template <class Entry>
Binary_tree<Entry>::Binary_tree()
/* 
 
Post: An empty binary tree has been created.
 
*/
{
   root = NULL;
}
 
template <class Entry>
bool Binary_tree<Entry>::empty() const
/* 
 
Post: A result of true is returned if the binary tree is empty.
      Otherwise, false is returned.
 
*/
{
   return root == NULL;
}
 
template <class Entry>
void Binary_tree<Entry>::inorder(void (*visit)(Entry &))
/* 
 
Post: The tree has been been traversed in infix
      order sequence.
Uses: The function recursive_inorder
 
*/
{
   recursive_inorder(root, visit);
}
 
template <class Entry>
Error_code Binary_tree<Entry>::remove(Entry &x)
/* 
 
Post: An entry of the binary tree with Key matching x is
      removed.  If there is no such entry a code of not_present
      is returned.
 
*/
{
   Binary_node<Entry> *&found = find_node(root, x);
   return remove_root(found);
}
 
template <class Entry>
void Binary_tree<Entry>::insert(const Entry &x)
/* 
 
Post: The Entry x is added to the binary tree.
 
*/
{
   recursive_insert(root, x);
}
 
template <class Entry>
void Binary_tree<Entry>::preorder(void (*visit)(Entry &))
/* 
 
Post: The binary tree is traversed in prefix order,
      applying the operation *visit at each entry.
 
*/
{
   recursive_preorder(root, visit);
}
 
template <class Entry>
void Binary_tree<Entry>::postorder(void (*visit)(Entry &))
/* 
 
Post: The binary tree is traversed in postfix order,
      applying the operation *visit at each entry.
 
*/
{
   recursive_postorder(root, visit);
}
 
template <class Entry>
int Binary_tree<Entry>::size() const
/* 
 
Post: The number of entries in the binary tree is returned.
 
*/
{
   return recursive_size(root);
}
 
template <class Entry>
int Binary_tree<Entry>::height() const
/* 
 
Post: The height of the binary tree is returned.
 
*/
{
   return recursive_height(root);
}
 
template <class Entry>
void Binary_tree<Entry>::clear()
/* 
 
Post: All entries of the binary tree are removed.
 
*/
{
   recursive_clear(root);
}
 
template <class Entry>
Binary_tree<Entry>::~Binary_tree()
/* 
 
Post: All entries of the binary tree are removed.
      All dynamically allocated memory in the structure
      is deleted.
 
*/
{
   clear();
}
 
template <class Entry>
Binary_tree<Entry>::Binary_tree (const Binary_tree<Entry> &original)
/* 
 
Post: A new binary tree is initialized to copy original.
 
*/
{
   root = recursive_copy(original.root);
}
 
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;
}
 
template <class Entry>
void Binary_tree<Entry>::swap()
/* 
 
Post: All left and right subtrees are switched
      in the binary tree.
 
*/
{
   recursive_swap(root);
}