• Choose a category
• All
• Classic-Fiction

By Root 1424 0

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.

Example 9.2. Implementation of the Binary Tree Abstract Datatype

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

* *

* ------------------------------- 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 {

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

*