bitree.c

掌握如何用C来实现各种算法

*****************************************************************************/

tree->size++;

return 0;

}

/*****************************************************************************
*                                                                            *
*  ---------------------------- bitree_rem_left ---------------------------  *
*                                                                            *
*****************************************************************************/

void bitree_rem_left(BiTree *tree, BiTreeNode *node) {

BiTreeNode         **position;

/*****************************************************************************
*                                                                            *
*  Do not allow removal from an empty tree.                                  *
*                                                                            *
*****************************************************************************/

if (bitree_size(tree) == 0)
   return;

/*****************************************************************************
*                                                                            *
*  Determine where to remove nodes.                                          *
*                                                                            *
*****************************************************************************/

if (node == NULL)
   position = &tree->root;
else
   position = &node->left;

/*****************************************************************************
*                                                                            *
*  Remove the nodes.                                                         *
*                                                                            *
*****************************************************************************/

if (*position != NULL) {

   bitree_rem_left(tree, *position);
   bitree_rem_right(tree, *position);

   if (tree->destroy != NULL) {

      /***********************************************************************
      *                                                                      *
      *  Call a user-defined function to free dynamically allocated data.    *
      *                                                                      *
      ***********************************************************************/

      tree->destroy((*position)->data);

   }

   free(*position);
   *position = NULL;

   /**************************************************************************
   *                                                                         *
   *  Adjust the size of the tree to account for the removed node.           *
   *                                                                         *
   **************************************************************************/

   tree->size--;

}

return;

}

/*****************************************************************************
*                                                                            *
*  --------------------------- bitree_rem_right ---------------------------  *
*                                                                            *
*****************************************************************************/

void bitree_rem_right(BiTree *tree, BiTreeNode *node) {

BiTreeNode         **position;

/*****************************************************************************
*                                                                            *
*  Do not allow removal from an empty tree.                                  *
*                                                                            *
*****************************************************************************/

if (bitree_size(tree) == 0)
   return;

/*****************************************************************************
*                                                                            *
*  Determine where to remove nodes.                                          *
*                                                                            *
*****************************************************************************/

if (node == NULL)
   position = &tree->root;
else
   position = &node->right;

/*****************************************************************************
*                                                                            *
*  Remove the nodes.                                                         *
*                                                                            *
*****************************************************************************/

if (*position != NULL) {

   bitree_rem_left(tree, *position);
   bitree_rem_right(tree, *position);

   if (tree->destroy != NULL) {

      /***********************************************************************
      *                                                                      *
      *  Call a user-defined function to free dynamically allocated data.    *
      *                                                                      *
      ***********************************************************************/

      tree->destroy((*position)->data);

   }

   free(*position);
   *position = NULL;

   /**************************************************************************
   *                                                                         *
   *  Adjust the size of the tree to account for the removed node.           *
   *                                                                         *
   **************************************************************************/

   tree->size--;

}

return;

}

/*****************************************************************************
*                                                                            *
*  ----------------------------- bitree_merge -----------------------------  *
*                                                                            *
*****************************************************************************/

int bitree_merge(BiTree *merge, BiTree *left, BiTree *right, const void
   *data) {

/*****************************************************************************
*                                                                            *
*  Initialize the merged tree.                                               *
*                                                                            *
*****************************************************************************/

bitree_init(merge, left->destroy);

/*****************************************************************************
*                                                                            *
*  Insert the data for the root node of the merged tree.                     *
*                                                                            *
*****************************************************************************/

if (bitree_ins_left(merge, NULL, data) != 0) {

   bitree_destroy(merge);
   return -1;

}

/*****************************************************************************
*                                                                            *
*  Merge the two binary trees into a single binary tree.                     *
*                                                                            *
*****************************************************************************/

bitree_root(merge)->left = bitree_root(left);
bitree_root(merge)->right = bitree_root(right);

/*****************************************************************************
*                                                                            *
*  Adjust the size of the new binary tree.                                   *
*                                                                            *
*****************************************************************************/

merge->size = merge->size + bitree_size(left) + bitree_size(right);

/*****************************************************************************
*                                                                            *
*  Do not let the original trees access the merged nodes.                    *
*                                                                            *
*****************************************************************************/

left->root = NULL;
left->size = 0;
right->root = NULL;
right->size = 0;

return 0;

}