The following types are suitable for representing a tree that has an integer stored at each node. Note that type Tree is identical to type Node*. An empty tree is represented by a NULL pointer.
struct Node { int item; // Information at this node Node* left; // The left subtree Node* right; // The right subtree Node(int it, Node* lft, Node* rgt) { item = it; left = lft; right = rgt; } }; typedef Node* Tree;
As for linked lists, we can separate functions on trees into nondestructive functions, which do not alter a tree, and destructive ones, which do.
A simple nondestructive function is numNodes(T), which yields the number of nodes in a tree. The algorithm breaks down naturally into two cases: an empty tree (NULL) and a nonempty tree.
If T is empty then T has 0 nodes.
If T is nonempty then T has its root (one node) plus all of the nodes in the left subtree plus all of the nodes in the right subtree.
int numNodes(const Tree T) { if(T == NULL) { return 0; } else { return 1 + numNodes(T->left) + numNodes(T->right); } }
Another example of a nondestructive function on trees is cubes(T), which returns a tree that looks like T except that each number is replaced by its cube.
int cube(int x) { return x*x*x; } Tree cubes(const Tree T) { if(T == NULL) { return NULL; } else { return new Node(cube(T-> item), cubes(T->left), cubes(T->right)); } }
A destructive function modifies a tree. For example, the following function replaces each item in a tree by its cube.
void cubeAll(Tree T) { if(T != NULL) { T->item = cube(T->item); cubeAll(T->left); cubeAll(T->right); } }Note that T does not need to be passed by reference because cubeAll does not need to change the pointer T. It only changes the node to which T points (and other nodes in subtrees). So cubeAll uses call by pointer. But some functions do need to use call by reference, since they need to store a different pointer into a variable. We will see some examples of that shortly.
Write a definition of function numLeaves(T), which returns the number of leaves in tree T. Answer
Write a definition of a function sum(T) that returns the sum of all of the numbers in a given tree. If T is empty then sum(T) is 0. Answer
Write a definition of function nonneg(T), which produces the tree that results by replacing each negative number in T by 0, and leaves nonnegative numbers as they were. For example, if T is the left-hand tree below then nonneg(T) is the right-hand tree.
20 20 / \ / \ / \ / \ -10 30 0 30 / \ / \ / \ / \ 2 -5 -7 9 2 0 0 9This function must not modify T. The result tree should be made out of new nodes. Answer
Write a definition of function mirror(T), which produces a mirror image of tree T. To get the mirror image, imagine picking the tree up with a spatula and flipping it over. For example, the following two trees are mirror images of one another.
50 50 / \ / \ / \ / \ 20 80 80 20 / \ / \ / \ / \ 2 5 7 9 9 7 5 2This function must not modify T. The result tree should be made out of new nodes. Answer
Read the definition of the height of a tree. Write a function height(T) that returns the height of tree T. Answer
The mirror image of a tree is defined in question 4. Write a definition of function flip(T) that changes T into its mirror image. This is a destructive function. Answer
Why doesn't the parameter of flip in the preceding question need to be passed by reference? Answer
Write a definition of function destroy(T), which deletes every node in tree T. Answer