/***************************************************************************** * * * ------------------------------- bitree.c ------------------------------- * * * *****************************************************************************/ #include #include #include "bitree.h" /***************************************************************************** * * * ------------------------------ bitree_init ----------------------------- * * * *****************************************************************************/ void bitree_init(BiTree *tree, void (*destroy)(void *data)) { /***************************************************************************** * * * Initialize the binary tree. * * * *****************************************************************************/ tree->size = 0; tree->destroy = destroy; tree->root = NULL; return; } /***************************************************************************** * * * ---------------------------- bitree_destroy ---------------------------- * * * *****************************************************************************/ void bitree_destroy(BiTree *tree) { /***************************************************************************** * * * Remove all the nodes from the tree. * * * *****************************************************************************/ bitree_rem_left(tree, NULL); /***************************************************************************** * * * No operations are allowed now, but clear the structure as a precaution. * * * *****************************************************************************/ memset(tree, 0, sizeof(BiTree)); return; } /***************************************************************************** * * * ---------------------------- bitree_ins_left --------------------------- * * * *****************************************************************************/ int bitree_ins_left(BiTree *tree, BiTreeNode *node, const void *data) { BiTreeNode *new_node, **position; /***************************************************************************** * * * Determine where to insert the node. * * * *****************************************************************************/ if (node == NULL) { /************************************************************************** * * * Allow insertion at the root only in an empty tree. * * * **************************************************************************/ if (bitree_size(tree) > 0) return -1; position = &tree->root; } else { /************************************************************************** * * * Normally allow insertion only at the end of a branch. * * * **************************************************************************/ if (bitree_left(node) != NULL) return -1; position = &node->left; } /***************************************************************************** * * * Allocate storage for the node. * * * *****************************************************************************/ if ((new_node = (BiTreeNode *)malloc(sizeof(BiTreeNode))) == NULL) return -1; /***************************************************************************** * * * Insert the node into the tree. * * * *****************************************************************************/ new_node->data = (void *)data; new_node->left = NULL; new_node->right = NULL; *position = new_node; /***************************************************************************** * * * Adjust the size of the tree to account for the inserted node. * * * *****************************************************************************/ tree->size++; return 0; } /***************************************************************************** * * * --------------------------- bitree_ins_right --------------------------- * * * *****************************************************************************/ int bitree_ins_right(BiTree *tree, BiTreeNode *node, const void *data) { BiTreeNode *new_node, **position; /***************************************************************************** * * * Determine where to insert the node. * * * *****************************************************************************/ if (node == NULL) { /************************************************************************** * * * Allow insertion at the root only in an empty tree. * * * **************************************************************************/ if (bitree_size(tree) > 0) return -1; position = &tree->root; } else { /************************************************************************** * * * Normally allow insertion only at the end of a branch. * * * **************************************************************************/ if (bitree_right(node) != NULL) return -1; position = &node->right; } /***************************************************************************** * * * Allocate storage for the node. * * * *****************************************************************************/ if ((new_node = (BiTreeNode *)malloc(sizeof(BiTreeNode))) == NULL) return -1; /***************************************************************************** * * * Insert the node into the tree. * * * *****************************************************************************/ new_node->data = (void *)data; new_node->left = NULL; new_node->right = NULL; *position = new_node; /***************************************************************************** * * * Adjust the size of the tree to account for the inserted node. * * * *****************************************************************************/ 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; }