9.14 Let t be a nonempty binary tree. Use the Strong Form of the Principle of Mathematical Induction to prove each of the following parts of the Binary Tree Theorem: a. If leaves(t ) = n(t ) + 1 / 2.0 then t is a two-tree. b. If n(t ) + 1 2.0 = 2height(t ) then t is a full tree. Hint: The proof for both parts has the same outline. For example, here is the outline for part a: For h = 0, 1, 2, . . . , let Sh be the statement If t is a binary tree of height h and leaves(t ) = n(t ) + 1 / 2.0 then t is a two-tree. In the inductive case, let h be any nonnegative integer and assume that S0, S1, . . ., Sh are all true. To show that Sh+1 is true, let t be a binary tree of height h + 1 such that leaves(t ) = n(t ) + 1 / 2.0 First, show that leaves(leftTree(t )) + leaves(rightTree(t )) = n(leftTree(t )) + 1 / 2.0 + n(rightTree(t )) + 1 / 2.0 For any non-negative integers a, b, c, and d, if a + b = c + d and a ≤ c and b ≥ d, then a = c and b = d. Then, using Exercise 8.10, show that leftTree(t) and rightTree(t) are two-trees. Then, using Exercise 8.8, show that both leftTree(t) and rightTree(t) are nonempty. Conclude, from the definition of a two-tree, that t must be a two-tree. | |
| View Solution | |
| << Back | Next >> |