CS 211
Data Structures

Stonehill College                    CS 211


Assignment 5

Due November 9
 

Downloads:

BinaryTree.h
BST.h
Queue (array implementation)
Queue( dynamic implementation)

Note: The BST class might need some adjusting in Visual Studio. It compiles in Codewarrior but there may be a problem when you use the .net compiler.  If you have a problem and you want to use visual studio, take out all the methods that pertain to search and delete.  You really only need

prog5a.cpp

For this assignment, you will add three new methods to the binary tree package:

1. Our Binary Tree class includes three methods for traversing a tree: inorder, preorder, and postorder.
For this assignment, you will add another traversal method to the class, levelorder. A leverorder traversal visits the nodes, level by level, left to right.

For example  the following tree

has level order traversal 9 5 13 3 7 11 15 2 4 6 8 12 14 16 1

The method for doing this is not particularly intuitive.  You use a queue as an auxilary data structure.
In general terms the algorithm is:

LevelOrder Traversal
insert the root into the queue
while the queue is not empty
        remove the front element, X, from queue
        visit X
        insert non-empty children of X into queue

2.  The structure of a binary tree can be easily displayed without explicitly drawing the tree.    Start with the root.  If there are any children, list them in parentheses.  Use  - (a dash) for a child that is missing; however do not display a - or parenthese for a leaf.  For example, the tree

is represented as 9(5 13).  The tree

is 9(5(3(2 4)7(6 -)13)
since the root has 2 children B and C, the node b has children D and E, E has one child F.

Hint: Use recursion

Call this method, displaytree.

3.    The third method, printtree, should display a tree on the screen. The function should display the tree with its root at the left of the screen.  In other words, the tree should be " on its side."

Example

is printed with the root in the left margin :

i.e. as

To space out the tree properly, let each column start 5 space to the right of the previous one. Thus the method printtree should have a parameter called numspaces.  Num spaces is initially 0 , so numspaces+5 is what is actually passed to the method. The function should be recursive and use a "baackward" inorder traversal (right-root-left) to output the tree.

Include a main program which inserts ints into a Binary Search Tree until the user enters 0.
The program should then do a level order traversal, parenthesizes the tree, and finally prints the tree.

Prog5b.cpp

Below are the declarations for an AVL class which creates a balanced binary search tree:

template <class T>
class AVL
{
    private:
        struct node
        {
            T data;
            int BF;
            node * left;
            node * right;
        };
        typedef node * ptr;
        ptr root;
        void recurTraverse(ptr root);  // inorder traversal

        public:
            AVL();
            void insert (const T& x);
            void LeftLeft(ptr & pivot);
            void RightRight(ptr & pivot);
            void LeftRight(ptr & pivot);
            void RightLeft(ptr & pivot); 
            void traverse(); // inorder traversal
};

a.

Implement the class.  You have the code for insert as well as LeftLeft, so you must implement the other three rotations and the traversal.

In main

   1. build a tree with the integers 1 to 25 and traverse the tree

   2. build a tree with the integers 25 down to 1 and traverse the tree

   3. build a tree with the 25 random integers and traverse the tree

b. Add a printtree function to the AVL class ( as described in the last problem)

    1. build a tree with the integers 1 to 25 and print the tree

   2. build a tree with the integers 25 down to 1 and print  the tree

   3. build a tree with the 25 random integers and print  the tree