node.cpp

来自「数据结构与程序设计教材源码 数据结构与程序设计教材源码」· C++ 代码 · 共 175 行

 
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 a subtree of
     a Binary_tree.
Post: The subtree has been 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 &))
/* 
 
Pre:  sub_root is either NULL or points to a subtree of
     a Binary_tree.
Post: The subtree has been been traversed in preorder sequence.
Uses: The function recursive_preorder recursively
 
*/

{
   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 &))
/* 
 
Pre:  sub_root is either NULL or points to a subtree of
     a Binary_tree.
Post: The subtree has been been traversed in postorder sequence.
Uses: The function recursive_postorder recursively
 
*/

{
   if (sub_root != NULL) {
      recursive_postorder(sub_root->left, visit);
      recursive_postorder(sub_root->right, visit);
      (*visit)(sub_root->data);
   }
}
 
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
     a 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> int Binary_tree<Entry>::
   recursive_size(Binary_node<Entry> *sub_root) const
{
   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_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);
   if (l > r) return 1 + l;
   else return 1 + r;
}
 
template <class Entry> void Binary_tree<Entry>::
   recursive_clear(Binary_node<Entry> *&sub_root)
{
   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)
{
   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> void Binary_tree<Entry>::
   recursive_swap(Binary_node<Entry> *sub_root)
{
   if (sub_root == NULL) return;
   Binary_node<Entry> *temp = sub_root->left;
   sub_root->left = sub_root->right;
   sub_root->right = temp;
   recursive_swap(sub_root->left);
   recursive_swap(sub_root->right);
}
 
template <class Entry> Binary_node<Entry> *&Binary_tree<Entry>::
   find_node(Binary_node<Entry> *&sub_root, const Entry &x) const
{
   if (sub_root == NULL || sub_root->data == x) return sub_root;
   else {
      Binary_node<Entry> *&temp = find_node(sub_root->left, x);
      if (temp != NULL) return temp;
      else return find_node(sub_root->right, x);
   }
}
 
template <class Entry> Error_code Binary_tree<Entry>::
   remove_root(Binary_node<Entry> *&sub_root)
/* 
 
Pre:  sub_root is either NULL or points to a subtree of
     a Search_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 parameter sub_root is reset as the root of the modified subtree and
      success is returned.
 
*/

{
   if (sub_root == NULL) return not_present;
   Binary_node<Entry> *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 start finding predecessor.
      Binary_node<Entry> *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 from to_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;
}