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

Projects

  1. Devise an algorithm to compute the height of a tree. Write an implementation of your algorithm as the getHeight method of the AbstractTree class introduced in Program gif.
  2. Devise an algorithm to count the number of internal nodes in a tree. Write an implementation of your algorithm as the getCount method of the AbstractTree class introduced in Program gif.
  3. Devise an algorithm to count the number of leaves in a tree. Write an implementation of your algorithm as a method of the AbstractTree class introduced in Program gif.
  4. Devise an abstract (generic) algorithm to compare trees. (See Exercise gif). Write an implementation of your algorithm as the compareTo method of the AbstractTree class introduced in Program gif.
  5. The TreeEnumeration class introduced in Program gif does a preorder traversal of a tree.
    1. Write an enumeration class that does a postorder traversal.
    2. Write an enumeration class that does a breadth-first traversal.
    3. Write an enumeration class that does an inorder traversal. (In this case, assume that the tree is a BinaryTree).
  6.   Complete the GeneralTree class introduced in Program gif by providing suitable definitions for the following methods: isEmpty, isLeaf, getDegree, and compareTo. Write a test program and test your implementation.
  7. Complete the NaryTree class introduced in Program gif by providing suitable definitions for the following methods: purge, isLeaf, getDegree, and compareTo. Write a test program and test your implementation.
  8.   Complete the BinaryTree class introduced in Program gif by providing suitable definitions for the following methods: isEmpty, isLeaf, getDegree, getKey, attachKey, detachKey, getLeft, attachLeft, detachLeft, getRight, attachRight, detachRight, and getSubtree. Write a test program and test your implementation.
  9. Write a visitor that draws a picture of a tree on the screen.
  10. Design and implement an algorithm that constructs an expression tree from an infix expression such as

    displaymath63206

    Hint: See Project gif.


next up previous contents index

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