1(18 points)
For each of the three trees shown here, list the order in which the nodes are visited
in:
a.
preorder
b.
postorder
c.
inorder
d.
level order
2.
Define the height of an empty tree as 0 and the height
of a nonempty tree as the number of nodes on the longest root-to-leaf path.
a. (1 point)
What is the minimum
height of a binary tree that contains 31 nodes?
height = 5
b. (1 point) What is the maximum height of a binary tree that contains 31 nodes?
height = 31, all in a line
c. (5 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 height of the tree.
int height (Node* t){
if (!t) return 0;
int l = height(t->left);
int r = height(t->right);
if (l > r) return l+1; else return r+1;
}
Last Updated: May 115, 1997, 1997 7:52 pm by