Print bookPrint book

Try It Now

Site: Saylor Academy
Course: CS202: Discrete Structures
Book: Try It Now
Printed by: Guest user
Date: Friday, April 19, 2024, 9:18 PM

Description

Work these exercises to see how well you understand this material.

Table of contents

Exercises

  1. Draw the expression trees for the following expressions:
    1. a(b + c)
    2. ab + c
    3. ab + ac
    4. bb − 4ac
    5. ((a3x + a2)x + a1)x + a0


  2. Write out the preorder, inorder, and postorder traversals of the trees in Exercise 1 above.

    1. Draw a binary tree with seven vertices and only one leaf.
    2. Draw a binary tree with seven vertices and as many leaves as possible.

  4. Prove that if T is a full binary tree, then the number of leaves of T is one more than the number of internal vertices (non-leaves).

 

Source: Al Doerr and Ken Levasseur, http://faculty.uml.edu/klevasseur/ads-latex/ads.pdf
Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.

Solutions

  1. Answer:




  2. Answer:

    \begin{matrix} & \mathrm{Preorder} & \mathrm{Inorder} & \mathrm{Postorder} \\ (a) & \cdot a + bc & a \cdot b+c & abc + \cdot\\ (b) & + \cdot abc & a\cdot b+c & ab \cdot c+\\ (c) & + \cdot ab \cdot ac & a \cdot b + a \cdot c & ab \cdot ac \cdot + \end{matrix}

  3. Answer:


  4. Answer:

    1. Solution 1:

      Basis: A binary tree consisting of a single vertex, which is a leaf, satisfies the equation leaves = internal vertices + 1

      Induction: Assume that for some k ≥ 1, all full binary trees with k or fewer vertices have one more leaf than internal vertices. Now consider any full binary tree with k + 1 vertices. Let TA and TB be the left and right subtrees of the tree which, by the definition of a full binary tree, must both be full. If iA and iB are the numbers of internal vertices in TA and TB, and jA and jB are the numbers of leaves, then jA = iA+ 1 and jB = iB+ 1.

      Therefore, in the whole tree, the number of leaves = jA + jB
      = (iA + 1) + (iB + 1)
      = (iA + iB + 1) + 1
      = (number of internal vertices) + 1

    2. Solution 2:

      Imagine building a full binary tree starting with a single vertex. By continuing to add leaves in pairs so that the tree stays full, we can build any full binary tree. Our starting tree satisfies the condition that the number of leaves is one more than the number of internal vertices. By adding a pair of leaves to a full binary tree, an old leaf becomes an internal vertex, increasing the number of internal vertices by one. Although we lose a leaf, the two added leaves create a net increase of one leaf. Therefore, the desired equality is maintained.