1( 8 points ) For the tree shown below, list the order in which the nodes are visited in:

a. preorder               A B D C E G F H I b. postorder   C D B H F I G E A c. inorder   B C D A E F H G I d. level order   A B E D G C F I H

2. (6 points) Write a recursive C++ function that inputs, as an argument, a binary tree (i.e. a pointer to the root node) and outputs the number of nodes in the tree that are right children. (In the tree above, D, E, G, H, I are right children.)

int Rights(Node * t){
	if (!t) return 0;	// no right children in an empty tree
	// Now we know t != Null.
	int count = 0;
	if (t->left) count += Rights(t->left);
	if (t->right) count += 1 + Rights(t->right); // the right child is counted
	return count;
}

Each operator node has the value of its subtree written next to it. Total = 35.


b. (postorder expression) 7 5 - 6 + 5 2 * 9 4 - * +

Each operator node has the value of its subtree written next to it. Total = 58.

Last Updated: May 18, 1997 2:40 pm by