CS 2420-20 Homework 9

Due: Thursday, February 16th, 2012 9:10am

Start with traverse.c from traverse.zip.

Part 1 – Tree Sum

Implement sum_tree(), which takes a tree and returns the sum of all numbers in the tree. (Does it matter which traversal strategy you choose?)

Part 2 – Tree to Container

Implement tree_to_container(), which takes a tree and generates a container that has all of the tree’s numbers based on an inorder traversal (i.e., in sorted order if the tree is a binary search tree).

Part 3 – Indenting

Change print_inorder() and print_postorder() to indent each node’s value by 2 times the depth of the node, where a node’s depth is its number of ancestors.

The print_tree() function shows a straight recursive version with indenting. To change print_inorder() and print_postorder(), you’ll need to expand the todo record to carry depth information.

Part 4 – Challenge: Add to Tree

Implement a tree_add() function that takes a tree and a number. It should create a new tree that is like the given tree, but with each number increased by the given amount. (Don’t modify the given tree).

Hint: A pre-order traversal can work if you pass each subtree a new parent (and side) to own the new subtree.