Mastering Algorithms With C - Kyle Loudon [83]
Figure 9.4. A left-balanced binary tree
Interface for Binary Trees
This interface provides basic operations for manipulating binary trees. However, it does not provide operations for inserting and removing individual nodes that are not leaves, because these operations require adjusting other nodes in the tree in some application-specific way to accommodate the node that is inserted or removed.
Name
bitree_init
Synopsis
void bitree_init(BiTree *tree, void (*destroy)(void *data));
Return Value
None.
Description
Initializes the binary tree specified by tree. This operation must be called for a binary tree before the tree can be used with any other operation. The destroy argument provides a way to free dynamically allocated data when bitree_destroy is called. For example, if the tree contains data dynamically allocated using malloc, destroy should be set to free to free the data as the binary tree is destroyed. For structured data containing several dynamically allocated members, destroy should be set to a user-defined function that calls free for each dynamically allocated member as well as for the structure itself. For a binary tree containing data that should not be freed, destroy should be set to NULL.
Complexity
O (1)
Name
bitree_destroy
Synopsis
void bitree_destroy(BiTree *tree);
Return Value
None.
Description
Destroys the binary tree specified by tree. No other operations are permitted after calling bitree_destroy unless bitree_init is called again. The bitree_destroy operation removes all nodes from a binary tree and calls the function passed as destroy to bitree_init once for each node as it is removed, provided destroy was not set to NULL.
Complexity
O (n), where n is the number of nodes in the binary tree.
Name
bitree_ins_left
Synopsis
int bitree_ins_left(BiTree *tree, BiTreeNode *node, const void *data);
Return Value
0if inserting the node is successful, or -1 otherwise.
Description
Inserts a node as the left child of node in the binary tree specified by tree. If node already has a left child, bitree_ins_left returns -1. If node is NULL, the new node is inserted as the root node. The tree must be empty to insert a node as the root node; otherwise, bitree_ins_left returns -1. When successful, the new node contains a pointer to data, so the memory referenced by data should remain valid as long as the node remains in the binary tree. It is the responsibility of the caller to manage the storage associated with data.
Complexity
O (1)
Name
bitree_ins_right
Synopsis
int bitree_ins_right(BiTree *tree, BiTreeNode *node, const void *data);
Return Value
0if inserting the node is successful, or -1 otherwise.
Description
This operation is similar to bitree_ins_left, except that it inserts a node as the right child of node in the binary tree specified by tree.
Complexity
O (1)
Name
bitree_rem_left
Synopsis
void bitree_rem_left(BiTree *tree, BiTreeNode *node);
Return Value
None.
Description
Removes the subtree rooted at the left child of node from the binary tree specified by tree. If node is NULL, all nodes in the tree are removed. The function passed as destroy to bitree_init is called once for each node as it is removed, provided destroy was not set to NULL.
Complexity
O (n), where n is the number of nodes in the subtree.
Name
bitree_rem_right
Synopsis
void bitree_rem_right(BiTree *tree, BiTreeNode *node);
Return Value
None.
Description
This operation is similar to bitree_rem_left, except that it removes the subtree rooted at the right child of node from the binary tree specified by tree.
Complexity
O (n), where n is the number of nodes in the subtree.
Name
bitree_merge
Synopsis
int bitree_merge(BiTree *merge, BiTree *left, BiTree *right, const void *data);
Return Value
0if merging the trees is successful, or -1 otherwise.
Description
Merges the two binary trees specified by left and right into the single binary tree merge. After merging is complete,