|
You traverse a tree walking through all of the nodes of the tree, doing something at each node. But there is more than one way to traverse a tree. For example, you can traverse tree
20
/ \
/ \
10 30
in any of the following orders.
r
/ \
/ \
A B
where A and B are subtrees, depending on where the root is
visited in relation to the subtrees, and whether the subtrees
are visited from left to right or from right to left. In all
cases, the subtrees are visited in the same order as the tree.
| (preorder) | r A B |
| (inorder) | A r B |
| (postorder) | A B r |
| (reverse preorder) | r B A |
| (reverse inorder) | B r A |
| (reverse postorder) | B A r |
For example, a preorder traversal of tree
50
/ \
/ \
14 36
/ \ / \
61 72 81 12
hits the nodes in the order 50, 14, 61, 72, 36, 81, 12.
A function that traverses a tree is easy to write. For example, let's write the values in a tree in preorder, with a space before each value.
void printPreorder(const Tree T)
{
if(T != NULL)
{
printf(" %i", T->item);
printPreorder(T->left);
printPreorder(T->right);
}
}
Changing the traversal order is just a matter of reordering the three statements inside the if-statement (and changing the function name). For example, the following prints the values in a tree in inorder.
void printInorder(const Tree T)
{
if(T != NULL)
{
printInorder(T->left);
printf(" %i", T->item);
printInorder(T->right);
}
}
Define a function that prints the values in a given tree in reverse-postorder, all on one line, with a space in front of each. Answer
If you print the values in a tree in postorder, do you get the reversal of what you get by printing the values in postorder? Answer
One way to add up the values in a tree is to pass a variable (by reference) along with the tree and to add each value in the tree to that variable. Write two functions, sum(T) and addup(T, v), with the following contracts.
Define a definition of function mems(T, L), which returns a linked list of all members of tree T in preorder followed by all members of linked list L. For example, if L is [4, 5, 6] and T is tree
9
/ \
/ \
2 7
/ / \
0 1 8
then mems(T, L) should return list [9, 2, 0, 7, 1, 8, 4, 5, 6].
You can use
memory sharing.
This might at first appear to be difficult, but it is not. Look at some examples and work out what the function should produce. What if T is empty? What if T is not empty? Look at the result list in the examples and see how you can break it down so that recursive calls to mems will help produce the result.
Answer
|