- Question 12 In The Slides And Videos I Went Over Recursive Definitions For Full Binary Trees The Number Of Nodes Of 1 (216.24 KiB) Viewed 17 times
Question 12 . In the slides and videos, I went over recursive definitions for full binary trees, the number of nodes of a full binary tree, and the height of a full binary tree. Recall that full binary trees allow nodes with 0 children and nodes with 2 children, and that is all. In a full binary tree, if a node has 0 children, it is called external. If it has 2 children, it is called internal. (a) Write a recursive definition for the number of external nodes in a full binary tree. Start by determining the number of external nodes in a base case full binary tree. Then consider joining two full binary trees and think about how many external nodes there are in the resulting tree with respect to the number of external nodes in the smaller trees. (b) Write a recursive definition for the number of intemal nodes in a full binary tree. Start by determining the number of internal nodes in a base case full binary tree. Then consider joining two full binary trees and think about how many internal nodes there are in the resulting tree with respect to the number of internal nodes in the smaller trees. (c) Look at several examples of full binary trees. You can either draw these yourself or look at the examples in the textbook/slides. For each one, count up the number of internal nodes and the number of external nodes until you notice a pattern and can fill in the following conjecture: For all full binary trees T,e(T)= (Fill in with something in terms of i(T).) (d) Use structural induction and the definitions you wrote in (a) and (b) to prove the conjecture in (c).