Implementation and Analysis of Binary Trees
Recall that each node of a binary tree consists of three
parts: a data member and two pointers to its children. The structure BiTreeNode
represents an individual node of a binary tree (see Example 9.1). As you would expect, this
structure has three members that correspond to those just mentioned.
The structure BiTree is the binary tree
data structure (see Example 9.1).
This structure consists of four members:
size is the number of nodes in the tree,
compare is a member not used by binary
trees but by datatypes that will be derived later from binary trees,
destroy is the encapsulated destroy
function passed to bitree_init, and
root is a pointer to the top of the node
hierarchy.
/*****************************************************************************
* *
* ------------------------------- bitree.h ------------------------------- *
* *
*****************************************************************************/
#ifndef BITREE_H
#define BITREE_H
#include <stdlib.h>
/*****************************************************************************
* *
* Define a structure for binary tree nodes. *
* *
*****************************************************************************/
typedef struct BiTreeNode_ {
void *data;
struct BiTreeNode_ *left;
struct BiTreeNode_ *right;
} BiTreeNode;
/*****************************************************************************
* *
* Define a structure for binary trees. *
* *
*****************************************************************************/
typedef struct BiTree_ {
int size;
int (*compare)(const void *key1, const void *key2);
void (*destroy)(void *data);
BiTreeNode *root;
} BiTree;
/*****************************************************************************
* *
* --------------------------- Public Interface --------------------------- *
* *
*****************************************************************************/
void bitree_init(BiTree *tree, void (*destroy)(void *data));
void bitree_destroy(BiTree *tree);
int bitree_ins_left(BiTree *tree, BiTreeNode *node, const void *data);
int bitree_ins_right(BiTree *tree, BiTreeNode *node, const void *data);
void bitree_rem_left(BiTree *tree, BiTreeNode *node);
void bitree_rem_right(BiTree *tree, BiTreeNode *node);
int bitree_merge(BiTree *merge, BiTree *left, BiTree *right, const void *data);
#define bitree_size(tree) ((tree)->size)
#define bitree_root(tree) ((tree)->root)
#define bitree_is_eob(node) ((node) == NULL)
#define bitree_is_leaf(node) ((node)->left == NULL && (node)->right == NULL)
#define bitree_data(node) ((node)->data)
#define bitree_left(node) ((node)->left)
#define bitree_right(node) ((node)->right)
#endifbitree_init
The bitree_init operation
initializes a binary tree so that it can be used in other operations
(see Example 9.2). Initializing a
binary tree is a simple operation in which we set the
size member of the tree to 0, the
destroy member to
destroy, and the
root pointer to NULL.
The runtime complexity of bitree_init is O (1) because all of the steps in initializing a binary tree run in a constant amount of time.
bitree_destroy
The bitree_destroy operation
destroys a binary tree (see Example
9.2). Primarily this means removing all nodes from the tree.
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.
The runtime complexity of bitree_destroy is O (n), where n is the number of nodes in the binary tree. This is because bitree_destroy simply calls bitree_rem_left, which runs in O (n) time, where n is the number of nodes in the tree.
bitree_ins_left
The bitree_ins_left operation
inserts a node into a binary tree as the left child of a specified
node (see Example 9.2). The call
sets the new node to point to the data passed by the caller. Linking
the new node into the tree is accomplished by setting the
left pointer of
node to point to the new node. If
node is NULL and the tree is empty, we
set the root member of the tree data
structure to the new node. We update the size of the tree by
incrementing the size member.
The runtime complexity of bitree_ins_left is O (1) because all of the steps in inserting a node into a binary tree run in a constant amount of time.
bitree_ins_right
The bitree_ins_right operation
inserts a node into a binary tree as the right child of a specified
node (see Example 9.2). This
operation works similarly to bitree_ins_left,
except that linking the new node into the tree is accomplished by
setting the right pointer of
node to point to the new node.
The runtime complexity of bitree_ins_right is O (1) because all of the steps in inserting a node into a binary tree run in a constant amount of time.
bitree_rem_left
The bitree_rem_left operation
removes the subtree rooted at the left child of a specified node
(see Example 9.2). Nodes are
removed by performing a postorder traversal beginning at the left
child of node. If
node is NULL, we begin the traversal at
the root node. 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. As each node is removed, we update the
size member of the tree data structure as
well.
The runtime complexity of bitree_rem_left
is O (n), where
n is the number of nodes in the subtree rooted
at the left child of node. This is
because bitree_rem_left performs a postorder
traversal to visit each of the nodes in the subtree while all other
parts of the operation run in a constant amount of time.
bitree_rem_right
The bitree_rem_right operation
removes the subtree rooted at the right child of a specified node
(see Example 9.2). This operation
works much like bitree_rem_left, except that
nodes are removed by performing a postorder traversal beginning at
the right child of node.
The runtime complexity of
bitree_rem_right is O
(n), where n is the number
of nodes in the subtree rooted at the right child of
node. This is because
bitree_rem_right performs a postorder traversal
to visit each of the nodes in the subtree while all other parts of
the operation run in a constant amount of time.
bitree_merge
The bitree_merge operation merges
two binary trees into a single binary tree (see Example 9.2). First, we initialize
merge by calling
bitree_init. Next, we insert
data into the merged tree at its root.
The merged tree’s left and right children are then set to be the
root nodes of left and
right, and the size of the tree is
adjusted to reflect the sizes of the subtrees. Last, we detach the
nodes now in the merged tree from the original trees and set the
size of each tree to 0.
The runtime complexity of bitree_merge is O (1) because all of the steps in merging two binary trees run in a constant amount of time.
bitree_size, bitree_root, bitree_is_eob, bitree_is_leaf, bitree_data, bitree_left, bitree_right
These macros implement some of the simpler binary tree
operations (see Example 9.1).
Generally, they provide an interface for accessing and testing
members of the BiTree and
BiTreeNode structures.
The runtime complexity of these operations is O (1) because accessing and testing members of a structure are simple tasks that run in a constant amount of time.
/***************************************************************************** * * * ------------------------------- bitree.c ------------------------------- * * * *****************************************************************************/ #include <stdlib.h> #include <string.h> #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; }