EECS 268:
Laboratory 8
Due: This is a 2-week lab; it is due before the start of your lab the week of November 12
Introduction
In this lab, you will implement several methods of the BinaryNodeTree class (which implements
the BinaryTreeInterface), using the BinaryNode data structure for the nodes in the tree.
Project Requirements
You must implement at least:
• All four constructors for BinaryNodeTree
• The destructor
• The three traversal methods
• The protected/private methods copyTree and the three “helpers” for the three traversal
types
Once these methods are working, you will write client code in your Executive class that creates a
BinaryNodeTree<std::string> that will be used to hold algebraic expressions. Your code will
be able to generate the tree from either a prefix expression or a postfix expression. Your program will
be launched from the command line like:
./lab8 [prefix | postfix] someFileName
For example:
./lab8 prefix prefixExample1.txt
or:
./lab8 postfix postfixExample1.txt
Here is one sample file for each type. We will test your code with other input files, so be sure your code
does not make any unnecessary assumptions about the expressions in the file. (You may assume that we
will always give you valid prefix or postfix expressions.)
• prefixExample1.txt
• postfixExample1.txt
Your Executive must have among its methods the following three whose prototypes must be exactly
the following:
void printTreePreorder(BinaryNodeTree<std::string> bt);
void printTreeInorder(BinaryNodeTree<std::string> bt);
void printTreePostorder(BinaryNodeTree<std::string> bt);
After your Executive has successfully parsed the input file, it will call each of these functions in
turn to produce a nicely formatted display for the three types. This is specified this way to test your
copy constructor and its interaction with your destructor.
You need not add parentheses to the result of the inorder traversal, although you may want to
experiment with that to see what is required to produce a minimal required set.
Implementation Hints
The tree will be constructed bottom-up using only constructor calls. Reading the prefix expression will
be easiest if you use a recusive method to read the string and build the tree. On the other hand, reading
the postfix expressions will be easiest if you use a non-recursive method which uses a Stack.
Grading Criteria
Grades will be assigned according to the following criteria:
• 20%: Correct implementation of the four constructors and the private/protected copyTree.
• 15%: Correct implementation of the destructor.
• 10%: Correct implementation of the public and private/protected traversal methods.
• 25%: Correct implementation of the prefix parsing and tree construction.
• 25%: Correct implementation of the postfix parsing and tree construction.
• 5%: Output formatting
Submission
Create a tarball with your source code in the usual way.
Email this tarball to your TA. The email subject line must look like “[EECS 268] SubmissionName” as
follows:
[EECS 268] Lab 08
Note that the subject should be exactly like the line above. Do not leave out any of the spaces, or the
bracket characters (“[” and “]”). In the body of your email, include your name and student ID.
#ifndef _BINARY_NODE_TREE
#define _BINARY_NODE_TREE
#include “BinaryTreeInterface.h”
#include “BinaryNode.h”
#include “PrecondViolatedExcep.h”
#include “NotFoundException.h”
template<class ItemType>
class BinaryNodeTree : public BinaryTreeInterface<ItemType>
{
private:
BinaryNode<ItemType>* rootPtr;
protected:
//————————————————————
// Protected Utility Methods Section:
// Recursive helper methods for the public methods.
//————————————————————
int getHeightHelper(BinaryNode<ItemType>* subTreePtr) const;
int getNumberOfNodesHelper(BinaryNode<ItemType>* subTreePtr) const;
// Recursively deletes all nodes from the tree.
void destroyTree(BinaryNode<ItemType>* subTreePtr);
// Copies the tree rooted at treePtr and returns a pointer to
// the copy.
BinaryNode<ItemType>* copyTree(const BinaryNode<ItemType>* treePtr) const;
// Recursive traversal helper methods:
void preorder(void visit(ItemType&), BinaryNode<ItemType>* treePtr) const;
void inorder(void visit(ItemType&), BinaryNode<ItemType>* treePtr) const;
void postorder(void visit(ItemType&), BinaryNode<ItemType>* treePtr) const;
public:
//————————————————————
// Constructor and Destructor Section.
//————————————————————
BinaryNodeTree();
BinaryNodeTree(const ItemType& rootItem);
BinaryNodeTree(const ItemType& rootItem,
const BinaryNodeTree<ItemType>* leftTreePtr,
const BinaryNodeTree<ItemType>* rightTreePtr);
BinaryNodeTree(const BinaryNodeTree<ItemType>& tree);
virtual ~BinaryNodeTree();
//————————————————————
// Public BinaryTreeInterface Methods Section.
//————————————————————
bool isEmpty() const;
int getHeight() const;
int getNumberOfNodes() const;
ItemType getRootData() const throw(PrecondViolatedExcep);
void setRootData(const ItemType& newData);
void clear();
//————————————————————
// Public Traversals Section.
//————————————————————
void preorderTraverse(void visit(ItemType&)) const;
void inorderTraverse(void visit(ItemType&)) const;
void postorderTraverse(void visit(ItemType&)) const;
//————————————————————
// Overloaded Operator Section.
//————————————————————
BinaryNodeTree& operator=(const BinaryNodeTree& rightHandSide);
}; // end BinaryNodeTree
#include “BinaryNodeTree.cpp”
#endif
#ifndef _BINARY_TREE_INTERFACE
#define _BINARY_TREE_INTERFACE
template<class ItemType>
class BinaryTreeInterface
{
public:
/** Virtual destructor allows concrete implementations to clean up
heap memory when the BinaryTree is discarded. */
virtual ~BinaryTreeInterface() {}
/** Tests whether this binary tree is empty.
@return True if the binary tree is empty, or false if not. */
virtual bool isEmpty() const = 0;
/** Gets the height of this binary tree.
@return The height of the binary tree. */
virtual int getHeight() const = 0;
/** Gets the number of nodes in this binary tree.
@return The number of nodes in the binary tree. */
virtual int getNumberOfNodes() const = 0;
/** Gets the data that is in the root of this binary tree.
@pre The binary tree is not empty.
@post The root’s data has been returned, and the binary tree is unchanged.
@return The data in the root of the binary tree. */
virtual ItemType getRootData() const = 0;
/** Replaces the data item in the root of this binary tree
with the given data, if the tree is not empty. However, if
the tree is empty, inserts a new root node containing the
given data into the tree.
@pre None.
@post The data in the root of the binary tree is as given.
@param newData The data for the root. */
virtual void setRootData(const ItemType& newData) = 0;
/** Removes all nodes from this binary tree. */
virtual void clear() = 0;
/** Traverses this binary tree in preorder (inorder, postorder) and
calls the function visit once for each node.
@param visit A client-defined function that performs an operation on
or with the data in each visited node. */
virtual void preorderTraverse(void visit(ItemType&)) const = 0;
virtual void inorderTraverse(void visit(ItemType&)) const = 0;
virtual void postorderTraverse(void visit(ItemType&)) const = 0;
};
#endif
// Created by Frank M. Carrano and Tim Henry.
// Copyright (c) 2013 __Pearson Education__. All rights reserved.
/** A class of nodes for a link-based binary tree.
Listing 16-2.
@file BinaryNode.h */
#ifndef _BINARY_NODE
#define _BINARY_NODE
template<class ItemType>
class BinaryNode
{
private:
ItemType item; // Data portion
BinaryNode<ItemType>* leftChildPtr; // Pointer to left child
BinaryNode<ItemType>* rightChildPtr; // Pointer to right child
public:
BinaryNode(const ItemType& anItem);
BinaryNode(const ItemType& anItem,
BinaryNode<ItemType>* leftPtr,
BinaryNode<ItemType>* rightPtr);
void setItem(const ItemType& anItem);
ItemType getItem() const;
bool isLeaf() const;
BinaryNode<ItemType>* getLeftChildPtr() const;
BinaryNode<ItemType>* getRightChildPtr() const;
void setLeftChildPtr(BinaryNode<ItemType>* leftPtr);
void setRightChildPtr(BinaryNode<ItemType>* rightPtr);
}; // end BinaryNode
#include “BinaryNode.cpp”
#endif
prefixExample1.txt
– +
* alpha beta /
count value
xFactor
postfixExample1.txt
fac1 fac2 *
fac3 rate
/ + delta
mult – /
