getCount
and getHeight
functions.
A binary tree is a structure with two properties: a shape property and a property that relates the keys of the elements in the structure. The shape property, binary tree is a structure in which each node is capable of having two successor nodes, called children. Each of the children, being nodes in the binary tree, can also have two child nodes, and so on, giving the tree its branching structure. The beginning of the tree node is called the root. The level of nodes refers to its distance from the root.
A binary search tree is a binary tree in which the key value in any node is greater than the key value in its left child and any of its children (the nodes in the left subtree) and less than the key value in its right child and any of its children (the nodes in the right subtree).
The data items in a binary search tree are of generic type DataType. Each data item has a key (of generic type KeyType) that uniquely identifies the data item. Data items usually include additional data. The data items must provide a function called getKey that returns a data item's key.
BSTree()
Requirements:
None
Results:
Default constructor. Creates an empty binary search Tree.
BSTree ( const BSTree<DataType,KeyType>& other)
Requirements:
None
Results:
Copy constructor. Initializes the binary search tree to be equivalent to the other BSTree object parameter.
BSTree& operator=( const BSTree<DataType,KeyType>& other)
Requirements:
None
Results:
overloaded assignment operator. Sets the binary search tree to be equivalent to the other BSTree object parameter and returns a reference to this object.
~BSTree ()
Requirements:
None
Results:
Destructor. Deallocates the memory used to store the binary search tree.
void insert( const DataType& newDataItem)
Requirements:
None
Results:
Inserts newDataItem
into the binary search tree. If a data item with the same key as newDataItem
already exists in the tree, then update that data item with newDataItem
.
bool retrieve( const KeyType& searchKey, DataType& newDataItem)const
Requirements:
None
Results:
Searches the binary search tree for the data item with key searchKey
. If this data item is found, then copies the data item to searchDataItem
and returns true
. Otherwise, returns false
with searchDataItem
undefined.
bool remove( const KeyType& deleteKey)
Requirements:
None
Results:
Delete the data item with key deleteKey
from the binary search tree. If this data item is found, then deletes it from the tree and returns true
. Otherwise, returns false
.
void writeKeys() const
Requirements:
None
Results:
Outputs the keys of the data items in the binary search tree. The keys are output in ascending order on one line, separated by spaces.
void showStructure() const
Requirements:
None
Results:
Outputs the keys in the binary search tree. The tree is output with its branches oriented form left (root) to right (leaves) that is, the tree is output rotated counterclockwise ninety degrees from its conventional orientation. If the tree is empty, outputs "Empty tree". Note that this operation is intended for debugging purposes only. It only supports data items with key values that are one of C++'s predefinded data types (int, char, and so forth) or other data structures that have overridden ostream operator<<
.
To define a parameter that is a reference to a pointer, you simply use both & and * in the data type specification for the parameter. For example, the following code declares the helper function (buildHelper
) for the build
function. The function takes a reference to a pointer to an expression tree node so that if a new node should be added to the tree, it can be allocated and added by simply assigning the newly allocated node to the node
parameter.
template<typename DataType>
void ExprTree<DataType>::buildHelper(ExprTreeNode*& node) {
......
}
Note: the order of the * and & operators is significant. "*&" means a reference to a pointer, but "&*" means a pointer to a reference, which is nonsense to the compiler.
You need to implement getCount()
and getHeight()
operations for this lab exercise.
It can be useful to know how many nodes a binary search tree contains. The following Binary Search Tree ADT operation adds the capability to interrogate a tree to find out how many data items it contaions.
int getCount () const
Requirement:
None
Results:
Returns the count of the number of data items in the binary search tree.
Binary search trees containing the same data items can vary widely in shape depending on the order in which the data items were inserted into trees. One measurement of a tree's shape is its heightthat is, the nubmer of nodes on the longest path from the root node to any leaf node. This statistic is singnificant because the amount of time that it can take to search for a date item in a binary search tree is a function of the height of the tree.
You can compute the height of a binary search tree using a postorder traversal and the following recursive definition of height for a tree rooted at a given node p.
int getHeight() const
Requirements:
None
Results:
Returns the height of the binary search tree.
Step0:
Click here To get the zipped files for this exerciseExtract all of the files to the WORKAREA. Open the WORKAREA and double click on binarytree.sln. This will open up the project. There are four files used in this program:
Step1: Implement these two operations and add them to the file
BSTree.cpp.
Prototypes for getCount
and getHeight
are included in the
declaration of the BSTree class in the file BSTree.h.
Step2: Prepare test plan for this operation by including a variety of different binary search trees and the expected results of calling the test plan again.
Step3: Execute the test plan, If you discover mistakes, correct them and execute again.
Your output should looks similar to the following.
This page last modified by Catherine Song:
Thursday, 10November2010 17:20:37 CST 



