Project 03 – Trees, Trees, and more Trees

Introduction

You are required to implement three tree data structures: a general tree, a heap

tree, and an AVL tree. No tree should contain duplicate values. You are also

required to create UML diagrams for each of the classes that you implement.

Finally, you have to provide the means to test your system by developing a

menu program that allows the user to manipulate your structures.

It is strictly prohibited to use the structures and/or algorithms defined in

the C++ standard library (STL). So, if your design requires a list, queue, stack,

or a hash table, you can only use your own implementations.

Underflow exceptions might be generated in some of the functions you implement. Make sure exceptions are thrown and caught where appropriate.

Deliverables

• A 1 page report with your UML diagrams that explains the design of your

data structures. Please include what each teammate did and approximate

hours spent on the project.

• An implementation of a general tree.

• An implementation of a heap tree.

• An implementation of an AVL tree.

• A menu program to test the implemented data structures.

1 General Tree

In this part of the project, you need to implement two classes, a TreeNode Class

and a LinkedTree Class; create their respective UML diagrams. Your TreeNode

class can be used for all trees (not all trees will use all data members). If you

would like to include further data members you may although it is not necessary.

Some of the methods are the same but have different names, you may feel free

to rename them as you see fit as long as they are descriptive. Calculate the

running time of your functions and include them in your report.

1

1.1 Description Trees, Trees, and more Trees

1.1 Description

A tree is a structure that is formed by Nodes (vertices) and Edges (arcs). Edges

connect nodes together. Any two nodes in the tree are connected by one and

only one path.

1.2 Data Members

Specify all the data members your implementation needs. You are required to

instantiate a TreeNode object for each of the nodes in the tree. Each node has a

key(int) – for Heap tree only, value (Type), balanceFactor (short int: -1 for

right high, 0 for balanced, 1 for left high) – for AVL tree only, and a parent,

left and right child (pointers for General and AVL tree, unused for Heap tree

because it is an array implementation).

1.3 Member Functions

Constructors

defines constructor.

Destructor

defines destructor.

Accessors

getRoot() returns the root of the tree.

getSize() returns number of elements in the tree.

getHeight() returns the height of the three.

getHeight(node) returns the height of the node in the argument (from

the root).

empty() returns true if the tree is empty, false otherwise.

leaves() returns the number of leaves in the tree.

siblings(node) returns the number of siblings of the node in the argument.

findNode(data) returns a pointer to a node that holds the data in the

argument.

2

1.3 Member Functions Trees, Trees, and more Trees

preorder() performs preorder traversal.

postorder() performs postorder traversal.

inorder() performs in order traversal.

Mutators

clear() removes all the elements in the tree

insert(data) inserts data in the tree.

del(data) removes data from the tree.

Friends

no friends for this class.

3

Trees, Trees, and more Trees

2 Heap

In this part of the project, you need to implement an additional MaxHeapTree

Class; create the UML diagram. Calculate the running time of your functions

and include them in your report.

2.1 Description

A priority queue is like a dictionary in the sense that it stores entries (key,value).

However, a dictionary is used when you want to look up a particular key. A

priority queue is used when you want to prioritize entries. There is a total order

defined on the keys. The main operations that a priority key allows to do are:

• Identify or remove the entry that has the smallest (largest) key. It is the

only one that could be removed quickly.

• Insert anything you want in any time.

A binary heap is a particular implementation of the priority queue abstract

data type. ‘A heap data structure should not be confused with the

heap which is a common name for the pool of memory from which

dynamically allocated memory is allocated’. Its definition encompasses

several things:

• Identify or remove the entry that has the smallest (or largest) key. It is

the only one that can be removed quickly.

• Insert anything you want at a more specific location in the tree.

For this part of the project you will implement a max heap and all of its

operations. Entries are stored in a dynamic array. If an entry is being inserted,

and the array is already full, the capacity of the array is doubled. If, after

removing an entry from the heap, and the number of entries is one-quarter

(1/4) the capacity of the array, then the capacity of the array is halved. The

capacity of the array may not be reduced below the initially specified (by you)

capacity.

2.2 Data Members

Specify all the data members your implementation needs. You are required to

instantiate a TreeNode object for each of the nodes in the tree. Your nodes have

a key (integer) and a value (Type), and they are stored in a dynamic array.

2.3 Member Functions

Constructors

defines constructor.

4

2.3 Member Functions Trees, Trees, and more Trees

Destructor

defines destructor.

Accessors

getMax() returns the root of the tree.

getSize() returns number of elements in the tree.

getHeight() returns the height of the tree.

empty() returns true if the tree is empty, false otherwise.

leaves() returns the number of leaves in the tree.

print() prints the heap.

Mutators

clear() removes all the elements in the tree

insert(key,data) inserts data in the tree. This operation must satisfied

the heap property.

delMax() removes the entry specified by maximum key in the tree. This

operation must satisfied the heap property.

Friends

defines friends for this class.

5

Trees, Trees, and more Trees

3 AVL Tree

In this part of the project, you need to implement an additional AVL Class;

create the UML diagram. Calculate the running time of your functions and

include them in your report.

3.1 Description

A binary search tree (BST) is a powerful tool to quickly search values in a tree.

However, if the BST is not balanced its operations can degenerate to linear

behavior, which makes them no faster than lists.

An AVL tree is a BST that includes complicated updating rules to keep

the tree balanced. An AVL tree requires that the height of the left and right

children of every node to differ by at most ± 1. Simple and double rotation are

executed when inserting or deleting an entry to/from the tree.

3.2 Data Members

Specify all the data members your implementation needs. You are required to

instantiate a TreeNode object for each of the nodes in the tree. Each node has

a value (Type), and access to its parent, left and right child.

3.3 Member Functions

Constructors

defines constructor.

Destructor

defines destructor.

Accessors

getRoot() returns the root of the tree.

getSize() returns number of elements in the tree.

getHeight() returns the height of the tree.

getHeight(node) returns the height of the node in the argument (from

the root).

empty() returns true if the tree is empty, false otherwise.

leaves() returns the number of leaves in the tree.

6

3.3 Member Functions Trees, Trees, and more Trees

siblings(node) returns the number of siblings of the node in the argument.

find(data) returns a pointer to a node that holds the data in the argument.

preorder() performs preorder traversal.

postorder() performs postorder traversal.

inorder() performs inorder traversal.

inorder() performs inorder traversal.

Mutators

clear() removes all the elements in the tree

insert(data) inserts data in the tree. Tree must be kept balanced after

the insertion.

del(data) removes data from the tree. Tree must be kept balanced after

the deletion.

Friends

defines friends for this class.

7

Trees, Trees, and more Trees

4 The Menu Program

In order to test your program, you are required to implement a menu program

that provides the means to run each of the functions in your classes (name your

executable proj3). Please choose the string data type for the values (or ’data’)

of your entries. The TA will choose one group to demo the project.

Format for the Menu Program

First, take a character, ’g’, ’h’, or ’a’ (lowercase) that specifies whether we will

be working with a general tree, a heap, or an AVL tree, respectively, and creates

an instance of the tree. Next, give the options for each specific tree (please have

them in this EXACT order for grading purposes):

General Tree or AVL Tree

1. Return root

2. Return size

3. Return height

4. Return height (node)

5. Is tree empty?

6. Return number of leaves

7. Return number of siblings (node)

8. Find node (data)

9. Print preorder

10. Print postorder

11. Print inorder

12. Clear tree

13. Insert (data)

14. Delete (data)

15. Exit

Max Heap

1. Return root

2. Return size

3. Return height

4. Is tree empty?

5. Return number of leaves

6. Print

7. Clear tree

8. Insert (key, data)

9. Delete

10. Exit

8

Trees, Trees, and more Trees

Submit the following files to Canvas (named EXACTLY as shown below

without zipping for grading purposes: (you may also include implementation

files with the header files if you would like)

1. menu.cpp

2. treeNode.h

3. linkedTree.h

4. maxHeapTree.h

5. avlTree.h

6. makefile (name your executable ’proj3’)

7. project3.pdf

The rubric is as follows:

1. A program that does not compile will result in a zero

2. Runtime error and compilation warning 5%

3. Commenting and style 15%

4. Report 10%

5. Functionality 70% (functions were declared and implemented as required)

9