Data Structures and Algorithms with Object-Oriented Design Patterns in Ruby

Projects

1. Devise an algorithm to compute the height of a tree. Write an implementation of your algorithm as the height method of the abstract Tree class introduced in Program .
2. Devise an algorithm to count the number of internal nodes in a tree. Write an implementation of your algorithm as the count method of the Tree class introduced in Program .
3. Devise an algorithm to count the number of leaves in a tree. Write an implementation of your algorithm as a method of the Tree class introduced in Program .
4. Devise an abstract (generic) algorithm to compare trees. (See Exercise ). Write an implementation of your algorithm as the compareTo method of the abstract Tree class introduced in Program .
5. The Iterator class introduced in Program  does a preorder traversal of a tree.
   1. Write an iterator class that does a postorder traversal.
   2. Write an iterator class that does a breadth-first traversal.
   3. Write an iterator class that does an inorder traversal. (In this case, assume that the tree is a BinaryTree).
6.   Complete the GeneralTree class introduced in Program  by providing suitable definitions for the following operations: empty?, leaf?, degree, and compareTo. Write a test program and test your implementation.
7. Complete the NaryTree class introduced in Program  by providing suitable definitions for the following operations: leaf?, degree, and compareTo. Write a test program and test your implementation.
8.   Complete the BinaryTree class introduced in Program  by providing suitable definitions for the following operations: empty?, leaf?, degree, key, attachKey, detachKey, attachLeft, detachLeft, 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

    

    Hint: See Project .

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