Binary Tree in C++ – 2

We continue our discussion of the binary tree toolkit with a couple of other functions.

3. The tree_clear function deallocates and returns to the heap the memory dynamically allocated for the nodes of the tree, and sets the root pointer to null.

We implement this function recursively.

In general, many of the tree functions can be implemented in a recursive fashion, because the problem generally reduces to problems of exactly the same kind but with the original parameter’s left and right children as its new parameters.

——

void tree_clear (Node* node_ptr)

{

if ( ! node_ptr)

// if root is null, we don’t need to do anything.

{

tree_clear (node_ptr -> left_ptr);

tree_clear (node_ptr -> right_ptr);

delete node_ptr;

node_ptr = 0;

}

}

——–

The clearing of the tree is accomplished in O(n) time since O(1) is spent on the non-recursive portion of the code for each of the n nodes of the tree.

——–

4. The tree_copy function takes a pointer to a node as an argument and returns a tree (i.e. the pointer to the root of a tree) which is an exact copy of the tree rooted at the node pointer passed as argument.

This function is also implemented recursively in a straightforward manner:

——

Node* tree_copy ( Node* node_ptr)

{

Node *root, *left, *right;

if ( ! node_ptr)

{

root = 0;

return root;

}


left = tree_copy ( node_ptr -> left_ptr);

right = tree_copy (node_ptr -> right_ptr);

root = create_node ( node_ptr -> data, left, right);

return root;

}

——–

Copying a tree also takes O(n) time.

——–


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: