Cover Data Structures and Algorithms with Object-Oriented Design Patterns in Java
next up previous contents index

Exercises

  1.   For each tree shown in Figure gif show the order in which the nodes are visited during the following tree traversals:
    1. preorder traversal,
    2. inorder traversal (if defined),
    3. postorder traversal, and
    4. breadth-first traversal.

       figure17083
    Figure: Sample trees for Exercise gif.

  2. Write a visitor that prints the nodes of a general tree in the format of Equation gif.
  3. Derive an expression for the total space needed to represent a tree of n internal nodes using each of the following classes:
    1. GeneralTree introduced in Program gif,
    2. NaryTree introduced in Program gif, and
    3. BinaryTree introduced in Program gif.
  4.   A full node in a binary tree is a node with two non-empty subtrees. Let l be the number of leaf nodes in a binary tree. Show that the number of full nodes is l-1.
  5. The generic depthFirstTraversal method defined in Program gif is a recursive method. Write a non-recursive depth-first traversal method that has exactly the same effect as the recursive version.
  6.   Program gif defines a visitor that prints using infix notation the expression represented by an expression tree. Write a visitor that prints the same expression in prefix notation with the following format:

    displaymath63170

  7. Repeat Exercise gif, but this time write a visitor that the expression in postfix notation with the following format:

    displaymath63171

  8. The visitor defined in Program gif prints many redundant parentheses because it does not take into consideration the precedence of the operators. Rewrite the visitor so that it prints

    displaymath63172

    rather than

    displaymath63144

  9.   Consider postfix expressions involving only binary operators. Show that if such an expression contains n symbols, it always has (n-1)/2 operators and (n+1)/2 operands.
  10.   Prove Theorem gif.
  11.   Generalize Theorem gif so that it applies to N-ary trees.
  12. Consider two binary trees, tex2html_wrap_inline62974 and tex2html_wrap_inline62976 and the relation tex2html_wrap_inline63202 given by

    equation17612

    If tex2html_wrap_inline63204, the trees are said to be isomorphic . Devise an algorithm to test whether two binary trees are isomorphic. What is the running time of your algorithm?


next up previous contents index

Bruno Copyright © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.