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 9
This 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 2
This 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