• Choose a category
• All
• Classic-Fiction

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)

#endif

bitree_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