Projects

1. Devise an algorithm to compute the height of a tree. Write an implementation of your algorithm as the Height member function of the abstract class Tree declared 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 member function of the abstract class Tree declared in Program .
3. Devise an algorithm to count the number of leaves in a tree. Write an implementation of your algorithm as a member function of the abstract class Tree declared in Program .
4. Devise an abstract (generic) algorithm to compare trees. (See Exercise ). Write an implementation of your algorithm as the CompareTo member function of the abstract class Tree declared in Program .
5. The Tree::Iter class defined in Programs , and  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 declared in Program  by providing suitable definitions for the following member functions: IsEmpty, IsLeaf, Degree and CompareTo. Write a test program and test your implementation.
7. Complete the NaryTree class declared in Program  by providing suitable definitions for the following member functions: NaryTree (destructor), Purge, IsLeaf, Degree and CompareTo. Write a test program and test your implementation.
8.   Complete the BinaryTree class declared in Program  by providing suitable definitions for the following member functions: IsEmpty, IsLeaf, Degree, Key, AttachKey, DetachKey, Left, AttachLeft, DetachLeft, Right, AttachRight, DetachRight and Subtree. 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 © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.